全種類集める

Q

TEOという紅茶に広末涼子の12種類のバッジがおまけでついていましたが、全種類集めるまでに、平均して何本のTEOを買わなければならないのでしょう?

A

1本買って1種類目が手に入る確率は1、2種類目は11/12…最後の12種類目は1/12とだんだん減っていきます。一般に確率pの事象を独立に試行して発生するまでの期待回数は1/pですから、求める期待値は12/12 + 12/11 + ... + 12/1 = 37.24... となります。目的のバッジの数の約3.1倍のTEOを買わなくてはいけません。

さて、12種類のときは本数の期待値はその3.1倍となりましたが(この比を広末係数と名付けます)、種類の数が増えるに従って広末係数はどのように変化していくでしょうか。一般に、種類の数が n のとき、全部揃うまでの期待本数は以下の式で表せます。

$$ n \sum_{i=1}^{n}\frac{1}{i} $$
したがって広末係数は
$$ H(n) = \sum_{i=1}^{n}\frac{1}{i} $$

になります。これは調和級数と呼ばれていて、 n が大きければほぼ \(\gamma + \log n\)(\(\gamma\) はオイラー定数で0.5772…、logは自然対数)に等しくなります。対数関数なので、なだらかですがnとともに無限に大きくなっていきます。たとえば n が10000のときは約 9.8 になり平均して10万本近く買わなくてはいけないことになります。