その1
その2
の続きです。数式表示のためMathJaxを使用。古いブラウザでは見えないかもしれません。
今回は、思いもよらず長大な解説となってしまった。この問題は何年も前にある方から質問されたものだが、当時は知識不足で全く答えられなかった。その後ずっと頭の隅には残っていたのだが、論文で解かれていたことを最近になって発見し、ようやく他人に解説できる程度には理解したという次第である。私に質問したその方とはもう会う機会がなくなり、結果をお聞かせできないことが残念である。だがこうしてブログにまとめを載せておくことにより、少しでも必要としている人の役に立てば幸いである。
以降の式は自力で導き出したものなので多少不安だが、検算で間違いが見つからなかったので、多分問題ないと思う。
さて、複数人で協力するクーポンコレクター問題における、コンプリート確率を求めたい。つまり次のような値を計算したいわけである。
CD1枚に、$n$種類からランダムに選ばれた1枚のカードが付属することになっている。CDを$i$枚購入した時に、それぞれの種類のカードが少なくとも$m$枚ずつ揃う確率はいくらか。
これを$m$人で共同購入する問題とみなす場合には、$i$を一人当たりの購入枚数と人数$m$との積に置き換えれば良い。（今回は、前回の追記部分に書いた問題は発生しない。）
問題を解くには、前回登場した$p_i$をまた使用する。この変数は、CDを$i$枚購入したときに条件を満たさない（$m$枚揃っていないカードが1種類以上ある）確率であった。従って$1-p_i$が今回の答えとなる。
$p_i$に対して、次のような式を考える。名前の混乱を避ける都合上、変数を$i$から$j$に変更した。
\[\sum_{j=0}^\infty p_j u^j \]
$u$という変数が突然現れたが、$u$が何を意味するのかということはあまり考えずに、ともかくこういう形の式だと思って欲しい。確率論を習った人ならばピンと来るだろうが、要するに母関数を考えようというわけである。この関数により、確率変数のさまざまな性質を取り出しやすくなる。例えばこれに$u=1$を代入することによって、コンプリートまでの平均購入枚数を計算可能である。
この式は前回の式と似ているため、計算の過程もほとんど同じで、次のように変形できる。
\begin{eqnarray}
\sum_{j=0}^\infty p_j u^j&=&\sum_{j=0}^\infty \frac{\left\{(x_1+x_2+\cdots +x_n)^j\right\}}{n^j}u^j\\
&=& \sum_{j=0}^\infty (\left\{(x_1+x_2+\cdots +x_n)^j\right\} u^j
n \int_0^\infty \frac{t^j}{j!}e^{-nt} dt) \\
&=& n \int_0^\infty \sum_{j=0}^{\infty}
\frac{\left\{(x_1+x_2+\cdots +x_n)^j\right\}}{j!}t^j u^j e^{-nt} dt\\
&=& n \int_0^\infty \sum_{j=0}^{\infty}
\frac{\left\{(t u x_1+t u x_2+\cdots +t u x_n)^j\right\}}{j!}e^{-nt} dt\\
&=&n \int_0^\infty (\exp(t u x_1+t u x_2+\cdots +t u x_n)\\
&-&(e^{t u x_1}-S_m (t u x_1)) \\
&\times& (e^{t u x_2}-S_m (t u x_2))\\
&\cdots &\\
&\times& (e^{t u x_n}-S_m (t u x_n)))e^{-n t} dt\\
&（&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!}\]
である。
$x_1=x_2=\cdots =x_n=1$を代入すると次のようになる。ただし最後の行の変形は、$u\neq 1$の場合にのみ有効である。
\begin{eqnarray}
\sum_{j=0}^\infty p_j u^j&=&n \int_0^\infty(e^{ntu}-(e^{tu}-S_m(tu))^n)e^{-nt}dt\\
&=&n \int_0^\infty (e^{nt(u-1)}-(e^{t(u-1)}-S_m(tu)e^{-t})^n)dt\\
&=&\frac{1}{1-u}-n \int_0^\infty (e^{t(u-1)}-S_m(tu)e^{-t})^ndt \hspace{0.8cm}(u\neq 1)
\end{eqnarray}
この式から$p_i$を求めてみたい。まず左辺を$u$で$i$回微分してみる。すると$j$が$i$未満の項が消え去り、$j$が$i$と等しい項は$u$に寄らない定数$i!p_i$となる。
\begin{eqnarray}
\frac{d \sum_{j=0}^{\infty} p_j u^j}{du^i}
&=&i!p_i + \sum_{j=i+1}^{\infty} \frac{j!}{(j-i)!} p_j u^{j-i}
\end{eqnarray}
これに$u=0$を代入すると、$i!p_i$のみが残る。従って、$\sum_{j=0}^\infty p_j u^j$を$u$で$i$回微分して$u=0$を代入し、$i!$で割れば、$p_i$が求まることがわかる。つまり、求める$1-p_i$は次式のようになる。
\begin{eqnarray}
1-p_i&=&1-\frac{1}{i!}\frac{d}{du^i}\sum_{j=0}^\infty p_j u^j \Bigg|_{u=0}\\
&=&1-\frac{1}{i!}\frac{d}{du^i}\left ( \frac{1}{1-u}-n \int_0^\infty (e^{t(u-1)}-S_m(tu)e^{-t})^ndt \right)\Bigg|_{u=0}\\
&=&1-\frac{1}{i!}\left ( i! – n \frac{d}{du^i} \int_0^\infty (e^{t(u-1)}-S_m(tu)e^{-t})^ndt \right)\Bigg|_{u=0}\\
&=&\frac{n}{i!} \frac{d}{du^i} \int_0^\infty (e^{t(u-1)}-S_m(tu)e^{-t})^ndt \Bigg|_{u=0}\\
&=&\frac{n}{i!} \frac{d}{du^i} \int_0^\infty \left(\frac{e^{tu}-S_m(tu)}{e^t}\right)^{n}dt \Bigg|_{u=0}
\end{eqnarray}
これが解である。といっても、これを解析解と言ってしまうことには、かなり躊躇わざるを得ない。この式を計算すること自体がかなり難しいからである。手計算ではまず不可能なので数値計算で求めようとすると、数値積分と数値微分を組み合わせて近似解を得ることになる。だが$i$階の数値微分や無限区間の積分を行う必要があり、精度がかなり不安である。Mathematicaなどの数式処理ソフトならば厳密解を求められるが、被積分関数が複雑で、積分にかなりの時間がかかる。$n$が3桁になるような問題は数多く存在するが、その規模になると時間もメモリも莫大に必要で、数式処理ではほとんど不可能である。他に良い方法があるかどうかは不明で、もしかしたらシミュレーションを実行して、モンテカルロ法で計算した方が速いかもしれない。
もっとも、n=5,m=5程度ならば何とか計算できて、結果はこうなる。
従って、90%以上の確率でコンプリートしたいと思ったら、1人で購入する場合は18枚買わなければならないが、2人の場合は14枚、3人の場合は12枚、4人の場合は11枚、5人の場合は10枚で済むことになる。予想通り、多人数で組むほどコンプリートしやすくなるようだ。ただ面白いことに、グラフの左端に注目すると、カードの種類と同じ枚数だけCDを購入する場合、つまり5枚だけ購入する場合のコンプリート確率では、逆転現象が起きている。
参加者全てが無駄なくCDを購入できるような状況は、人数が多くなるほど困難になるということなのだろう。ちなみにこの場合の確率は特殊なケースだから、場合の数から次のように計算できる。
\[\frac{1}{n^{nm}}\frac{(nm)!}{(m!)^n}=\frac{(nm)!}{(n^m m!)^n}\]
$m$が大きいほどこの値が小さくなるのは、明らかである。
$m=1$の時に、$1-p_i$の式がその1で求めた式と一致することは、$n$乗の部分を二項展開して微分と積分を入れ替えれば確認できる。また多少の知識を要するが、全てをコンプリートするまでのCD購入枚数の分散が
\[V_1(n)=n\left ( \frac{n \pi^2}{6}-n \psi^{(1)}(n+1)-\sum_{j=1}^{n}\frac{1}{j}\right )\]
（$\psi^{(1)}$はディガンマ関数の微分＝トリガンマ関数）
となることも、わかる。
それにしても今回の問題、取っつきやすさに対してこの難しさは何なのだろうかと思う。特に$m>1$の場合は尋常ではない難易度で、解が得られても計算がまた困難であるという状況になる。だが式の形は面白い。関連する研究に関して最近もいろいろな論文が出ているようで、本当に奥が深い問題だと思う。
この問題は、ネットワークにおける輻輳の分析などにも使用されるなど、応用範囲が広いようだ。始めに書いたように、日常生活でも役立つ理論である。もっといろいろな場所で取り上げられることを期待したい。
最近のコメント