複数人で協力するクーポンコレクター問題（その1）

　こういう話題でも、極まれながら必要とする人に発見されて感想をもらえることがあります。今回は私にとって長年疑問だったことが、ある論文を読んで解決できたので、それを私なりの理解で書き下してみました。数式が多いのでMathJaxを使用しています。IEの古いバージョンなどでは読めないかもしれません。スマートファンの方は、PC版のページでご覧下さい。なお、順列組み合わせの記号として$_x C_y$の代わりに$\binom{x}{y}$を使用します。

　確率論の世界に「クーポンコレクター問題」というものがある。これは「トレーディングカード問題」とも呼ばれ、その見かけの単純さと内容の深さとのギャップから、しばしば話題になる問題である。

　どのような問題か。例えば

　CDにカードが1枚付属して売られている。カードは5種類あり、その中からランダムで選ばれたものが入っている。この時、カード5種類全てを揃えるにはCDを平均で何枚買えば良いか

というようなものである。実世界で良くある設定なので、実用性が高い問題と言えるだろう。実は、これに答えるだけならば簡単である。まずどれか1種類のカードが揃うまでには、当然CDを1枚買えば良い。2種類目のカードが揃うためには、1枚目に出たカード以外のものが出れば良い。その確率は$\frac{4}{5}$だから、揃うまでの平均CD購入枚数は$1+\frac{5}{4}$である。以下同様に考えると、全てのカードが揃うまでの平均CD購入枚数は
\[1+\frac{5}{4}+\frac{5}{3}+\frac{5}{2}+\frac{5}{1}=\frac{137}{12}\cong 11.42\]
となる。カードが$n$種類ある場合、平均で$\sum_{i=1}^n \frac{n}{i}$枚のCDを購入すると全種類が揃う。

　ここまでは簡単。

　しかし、実用上はもう少し詳しい情報が欲しい。例えば

• CDを買うチャンスは1度しかないとする。確率90%で全部揃えたいのだが、CDは何枚買えば良いか
• CDを10枚買うと何%の確率でコンプリートに成功するのか

といったことを知りたいのである。そこで、問題を一般化してみよう。

カードが$n$種類ある場合にCDを$i$枚買ったとして、カードが全て揃う確率はいくらか

こうなると、確率問題の中でも難しい部類に入る。

　まず、確率ではなく場合の数を求めてみよう。これには包含と排除の原理（包除の原理）というものを使うことになる。起こりうる全ての場合の数は、$n$種類の選択が$i$回行われるわけだから$n^i$となる。この式から、1種類以上のカードが欠けている場合の数を引けば良い。1種類以上が欠けている場合の数は、カードの種類それぞれについてそのカード以外の$n-1$種類が$i$回選択される場合の数を計算し、それを足し合わせれば求まるので、次のようになる。
\begin{eqnarray}&1種類&以上のカードが欠けている場合の数(仮)\\
&=&1番目の種類のカードが欠けている場合の数\\
&+&2番目の種類のカードが欠けている場合の数\\
&+&3番目の種類のカードが欠けている場合の数\\
&\cdots& \\
&+&n番目の種類のカードが欠けている場合の数\\
&=&n (n-1)^i
\end{eqnarray}
　ところがこの数には、2種類以上のカードが欠けている場合が重複して数えられている。（仮）としたのはそのためである。従って重複した分を引かなければならず、具体的には次の数を引き算することになる。
\begin{eqnarray} &2種類&以上のカードが欠けている場合の数(仮)\\
&=&1番目と2番目の種類のカードが欠けている場合の数\\
&+&1番目と3番目の種類のカードが欠けている場合の数\\
&+&1番目と4番目の種類のカードが欠けている場合の数\\
&\cdots& \\
&+&n-1番目とn番目の種類のカードが欠けている場合の数\\
&=&\binom{n}{2} (n-2)^i \end{eqnarray}
次はもう想像が付くかと思う。この数は3種類以上のカードが欠けている場合を重複して数えているので、それをまた引かなければならないのである。そしてこのプロセスを最後($n$種類)まで実行して式を展開すると、＋、－の項が交互に出てくる式が構成される。
\begin{eqnarray}
&n^i&-\Bigg (n(n-1)^i-\Bigg (\binom{n}{2} (n-2)^i-\Bigg (\cdots \\
&-&\Bigg (\binom{n}{n-1}1^i-\binom{n}{n}0^i\Bigg )\cdots\Bigg )\Bigg )\Bigg )\\
&=&\sum_{j=0}^{n} (-1)^j \binom{n}{j}(n-j)^i \\
&=&\sum_{j=0}^{n} (-1)^{n-j} \binom{n}{j}j^i
\end{eqnarray}
最後の行は、$j\rightarrow n-j$の置き換えを行った。実は、これを$n!$で割ると第２種スターリング数と呼ばれるものになる。調べ物をする時には、このキーワードで検索すると良いだろう。第2種スターリング数を上の式で計算するのは大変であるが、漸化式が存在するのでそれを利用して数値を求めるのが一般的だと思われる。その方法は、ここでは省略する。

　さて、求めたいのは確率である。これは、CDを$i$枚購入した時のカードの組み合わせ数$n^i$で上の式を割れば良い。すなわち次の式となる。
\[ \frac{1}{n^i} \sum_{j=0}^{n} (-1)^{n-j} \binom{n}{j}j^i\]
カードが5種類あるとして、CDを$i$枚購入した場合に全種類をコンプリートしている確率を求めると、次のグラフのようになる。



上に出した例で言えば、90%の確率でコンプリートを成功させるには18枚買えば良いことになる。また10枚買った時の成功率は52%である。

　これで問題は解決したが、もう一段階だけ一般化した式も示しておきたい。

$n$種類のカードのうち1枚がランダムで選ばれて入っているCDを$i$枚買ったとして、カードが$p$種類揃っている確率はいくらか

というものを考える。今までの理論に少し手を加えれば、これは容易に解ける。$n$種類から$p$種類を選ぶ方法は$\binom{n}{p}$通りで、$p$種類を全て揃える場合の数は
\[\sum_{j=0}^{p} (-1)^{p-j} \binom{p}{j}j^i\]通り
だから、それを掛けて全ての場合の数$n^i$で割れば良い。
\[\frac{1}{n^i}\binom{n}{p} \sum_{j=0}^{p} (-1)^{p-j} \binom{p}{j}j^i\]
この式があれば大抵のことはわかるはずである。例えば

ある会社では、社員の誰かが誕生日ならばその日はパーティーを開く。n人の社員がいる場合に、年間100日以上パーティーが開かれる確率を求めよ

というような問題も計算で求められる。



　さて、ここまでは良い。実際の値を計算するのは大変だが、考え方自体は高校生でも何とか理解できる範疇だと思う。私が長年疑問だったのは「では$n$人が協力したらどうなるのか」である。複数人がCDを購入する場合、余った種類のカードを交換し合うことによって、コンプリートするまでのハードルを下げることが可能なはずである。具体的にはどれぐらい下がるのか。これが難しい。相当に難しい問題なのである。

その2へとつづく。