その1の続きです。数式表示のためMathJaxを使用。古いブラウザでは見えないかもしれません。
コレクター問題において、複数人が協力した場合にどの程度購入枚数が減るのか。問題を次のように定式化しよう。
CD1枚に、$n$種類からランダムに選ばれた1枚のカードが付属することになっている。それぞれの種類のカードが少なくとも$m$枚ずつ揃うまでに必要な、平均CD購入枚数$E_m(n)$は何枚か。
複数人で購入という書き方にはなっていないが、$m$人グループで購入した場合と本質的には同じ問題である。もっとも、各人の平均購入枚数を求めるには、最後にこの結果を$m$で割らなければならない（※これ厳密には間違っていました。追記参照）。これまでに考察したのは、この問題において$m=1$とした特殊ケースである。
一見、この問題も同じように包含と排除の原理で考えれば解けそうである。しかしこれが上手く行かない。$m=1$以外の場合は、同じ手法では破綻してしまうのである。この問題は、NewmanとSheppが巧妙な方法により解決している。さっそくその論文を見てみよう。
まず$p_i$を定義する。$p_i$とは、CDを$i$枚購入したときに条件を満たさない（$m$枚揃っていないカードが1種類以上ある）確率である。最初に彼らが主張するのは、平均のCD購入枚数が$\sum_{i=0}^\infty p_i$となることである。直感的に正しいような気がするが、一応証明してみたい。
$i$枚目を購入した瞬間に条件が満たされる確率は、$i-1$枚目で条件を満たさず$i$枚目で条件を満たす場合を考えれば良いので、$p_{i-1}$から$p_i$までに、どの程度揃わない確率が減ったかを見れば良い。これは$p_{i-1}-p_i$となり、何枚目で条件を満たすかの平均値は次のようになる。
\begin{eqnarray}
\sum_{i=1}^{\infty} i (p_{i-1}-p_i)&=&1(p_0-p_1)+2(p_1-p_2)+3(p_2-p_3)+\cdots \\
&=&p_0+p_1+p_2+\cdots\\
&=&\sum_{i=0}^\infty p_i
\end{eqnarray}
求めたいのは、この式の値である。
さて、CDを$i$枚購入するまでに、$n$種類の選択機会が$i$回発生するわけだから、起こりうる全ての場合の数は$n^i$である。従って、CDを$i$枚購入したときに条件を満たさない場合の数を$N_i$とすると、$p_i=\frac{N_i}{n^i}$となる。ここで、$(x_1+x_2+\cdots +x_n)^i$という式を考える。全ケース数$n^i$はこれに$x_1=x_2=\cdots =x_n=1$を代入した値に等しい。$N_i$は、この中から問題の条件を満たす場合を取り除いて数えれば良いことになる。条件を満たすとは、$n$種類のカード全てが$m$枚以上揃っている場合だから、その組み合わせ数は$(x_1+x_2+\cdots +x_n)^i$を展開して、$x_1,x_2,x_3,\cdots ,x_n$の次数全てが$m$乗以上であるような項の数と等しくなる。それに相当する項を除外するわけだが、この除外する操作を$\left\{\right\}$で表す。すなわち、
\begin{eqnarray}
N_i=\left\{(x_1+x_2+\cdots +x_n)^i\right\}\\ （但しx_1=x_2=\cdots =x_n=1）
\end{eqnarray}
である。すると我々が知りたい値は、
\begin{eqnarray}
E_m (n)&=& \sum_{i=0}^\infty p_i \\
&=&\sum_{i=0}^\infty \frac{\left\{(x_1+x_2+\cdots +x_n)^i\right\}}{n^i}\\
&（&x_1=x_2=\cdots =x_n=1）
\end{eqnarray}
と表せる。
問題はここからである。話がだんだん難しくなる。まず関数$S_m (t)$を次のように定義しよう。
\[S_m (t)=\sum_{k=0}^{m-1}\frac{t^k}{k!}\]
そして次式$F$を考える。
\begin{eqnarray}
F&=&\exp(x_1+x_2+\cdots +x_n)\\
&-&(e^{x_1}-S_m (x_1))(e^{x_2}-S_m (x_2))\cdots (e^{x_n}-S_m (x_n))
\end{eqnarray}
ところで、$e^x$を$x=0$においてテイラー展開すると、次のようになる。
\[e^x=1+x+\frac{x^2}{2!}+\frac{x^3}{3!}\cdots \]
従って$F$の第1項は次のように変形できる。
\begin{eqnarray}Fの第1項&=&\exp(x_1+x_2+\cdots +x_n)\\
&=&e^{x_1} e^{x_2} e^{x_3}\cdots e^{x_n}\\
&=&(1+x_1+\frac{x_1^2}{2!}+\cdots )\\
& \times &(1+x_2+\frac{x_2^2}{2!}+\cdots )\\
& \times& (1+x_3+\frac{x_3^2}{2!}+\cdots )\\
&\cdots\\
& \times&(1+x_n+\frac{x_n^2}{2!}+.\cdots)
\end{eqnarray}
次に、$F$の第2項に現れる各$e^{x_i}(i=1,2,\cdots,n)$にもテイラー展開を適用してみよう。それぞれ$e^{x_i}$から$S_m (x_i)$を引いているので、結局$m$乗以上の項が残ることになる。
\begin{eqnarray}
Fの第2項&=&(\frac{x_1^m}{m!}+\frac{x_1^{m+1}}{(m+1)!}+\cdots)\\
&\times& (\frac{x_2^m}{m!}+\frac{x_2^{m+1}}{(m+1)!}+\cdots) \\
&\times& (\frac{x_3^m}{m!}+\frac{x_3^{m+1}}{(m+1)!}+\cdots)\\
&\cdots& \\
&\times& (\frac{x_n^m}{m!}+\frac{x_n^{m+1}}{(m+1)!}+\cdots)
\end{eqnarray}
ここでFの第1項と第2項を展開して前者から後者を引くと、「$x_1,x_2,\cdots,x_n$の全ての次数が$m$を超える項」は消えるから、「$x_1,x_2,\cdots,x_n$について、それらの次数のうち一つ以上が$m$以下であるような項」だけが残り、かつその条件に当てはまる項は全て含まれている。これは第2項を引くことと$\left\{\right\}$の操作をすることが等しいということを意味していて、つまり
\[F=\left\{\exp(x_1+x_2+\cdots+x_n)\right\}\]
となる。
ところで、$\exp(x_1+x_2+\cdots +x_n)$を別のやり方でテイラー展開してみよう。$x_1+x_2+\cdots +x_n$を一つの変数として見れば、
\[\exp(x_1+x_2+\cdots +x_n)
=\sum_{i=0}^\infty \frac{(x_1+x_2+\cdots +x_n)^i}{i!}\]
とも表せられる。従って
\begin{eqnarray}
F&=&\left\{\exp(x_1+x_2+\cdots +x_n)\right\}\\
&=&\left\{\sum_{i=0}^\infty \frac{(x_1+x_2+\cdots +x_n)^i}{i!} \right\}\\
&=&\sum_{i=0}^\infty \frac{\left\{(x_1+x_2+\cdots +x_n)^i \right\}}{i!} \\
\end{eqnarray}
が成立する。
さて、我々が求めるべき$E_m (n)$は
\[\sum_{i=0}^\infty \frac{\left\{(x_1+x_2+\cdots +x_n)^i\right\}}{n^i}\]に$x_1=x_2=\cdots =x_n=1$を代入した値であった。上に導いた$F$の式と似ているが係数が微妙に違うので、それを調整しなければならない。そこで利用するのが次の公式である。
\[n \int_0^\infty \frac{t^i}{i!} e^{-nt} dt = \frac{1}{n^i}\]
この公式の証明は$i$に関する帰納法と部分積分を利用して行えるが、省略する。
公式の右辺を$E_m(n)$の式に代入してみよう。次のようになる。
\begin{eqnarray}
E_m(n)&=&\sum_{i=0}^\infty \frac{\left\{(x_1+x_2+\cdots +x_n)^i\right\}}{n^i}\\
&=& \sum_{i=0}^\infty (\left\{(x_1+x_2+\cdots +x_n)^i\right\}
n \int_0^\infty \frac{t^i}{i!}e^{-nt} dt) \\
&=& n \int_0^\infty \sum_{i=0}^{\infty}
\frac{\left\{(x_1+x_2+\cdots +x_n)^i\right\}}{i!}t^ie^{-nt} dt\\
&=& n \int_0^\infty \sum_{i=0}^{\infty}
\frac{\left\{(t x_1+t x_2+\cdots +t x_n)^i\right\}}{i!}e^{-nt} dt\\
&（&x_1=x_2=\cdots =x_n=1）
\end{eqnarray}
積分と総和を交換して良いかという疑問があるが……、一様収束のようだから大丈夫だろうと思われる。本来ならば厳密な証明が必要であろう。ここで最後の式の$\sum_{i=0}^\infty\frac{\left\{(t x_1+t x_2+\cdots +t x_n)^i\right\}}{i!}$は、$F$式中の$x_1,x_2,\cdots,x_n$についてそれぞれを$t x_1,t x_2,\cdots,xt _n$に置き換えたものに等しい。従って上式は次のように変換できる。
\begin{eqnarray}
E_m(n)&=&n \int_0^\infty (\exp(t x_1+t x_2+\cdots +t x_n)\\
&-&(e^{t x_1}-S_m (t x_1)) \\
&\times& (e^{t x_2}-S_m (t x_2))\\
&\cdots &\\
&\times& (e^{t x_n}-S_m (t x_n)))e^{-nt} dt\\
&（&x_1=x_2=\cdots =x_n=1）
\end{eqnarray}
さらに$x_1=x_2=\cdots =x_n=1$を代入すると次式が得られる。
\begin{eqnarray}
E_m (n)&=&n \int_0^\infty(e^{nt}-(e^t-S_m(t))^n)e^{-nt}dt\\
&=&n \int_0^\infty(1-(1-S_m(t)e^{-t})^n)dt
\end{eqnarray}
これで、ようやく答えが得られた。想像よりも手間がかかる導出過程であった。
この式を利用して、カードが5種類ある場合にm人グループの全員がコンプリートするまでの、一人当たりの平均CD購入枚数を見てみよう。
やはり、複数人で購入することの効果が現れている。友達って大事だなという結果であるが、$m$が大きくなるに連れて友達を一人増やす効果は少なくなっていることもわかる。
これで、コンプリートするまでの平均購入枚数は求まった。だが、$m=1$の場合で求めたように、ある特定の枚数を購入した場合のコンプリート確率も求めたい。NewmanとSheppの論文にその方法は書かれていない。これ以上の理解を深めるためには、母関数に関する理解が必要である。つづく。（数日後）
追記
$E_m(n)$を$m$で割ると、$m$人で協力した場合の一人当たりのCD購入枚数を求める問題に変換できるという前提で計算しましたが、解は微妙に違うかもしれません。例えば、1人が購入する枚数は整数なので、2人($m=2$)で協力している時にCDを計奇数枚買うということはあり得ません。しかし$E_m(n)$はそのような場合も含めて平均を計算してしまっています。本来ならば
\[\sum_{i=0}^\infty im(p_{(i-1)m}-p_{im})\]
のように飛び飛びで足さなければならないはずです。時間がかかると思いますが、これの分析も行おうと思っています。
最近のコメント