公正な賽子を六面すべてが出るまで振ります。投擲回数の期待値は 14.7 です(一つ目と二つ目のリンク、同じ和を因数分解したものと展開したもの)。考え方は一行です:まだ k 面が欠けている間、各投擲が新しい面である確率は k/6 なので、次の新しい面を待つのは期待値 6/k の幾何試行であり、和は 6/1 + 6/2 + 6/3 + 6/4 + 6/5 + 6/6 です。三つ目のリンクは五つのクーポンで問題を実行し、11.416666666667 を得ます。四つ目 6⁶ = 46656 は六回の投擲の可能な列の数——この問いには間違った道具ですが、関連する問いには正しい分母です:最初の六回の投擲ですでに六面すべてが出る確率は 6!/46 656 で、1.5 パーセントをわずかに超えます。
答えの形は数より重要です:n·H_n は n ln n のように増えるので、費用はほぼすべて最後の数枚のクーポンにあります。百個の何かは 100·H₁₀₀ = 518.7 回の試行を要し、そのうち最後だけで百を占めます。最初はたった一回です。この非対称性が、無料トークン制度が終盤で詰まるように感じられる理由、コレクションカードの最後の一枚が高価な理由、そしてあらゆる値を見ねばならないランダム化アルゴリズムが同じ調和的代価を払う理由です。散らばりも同じ方向へ行きます——再尺度化された待ち時間の分布はガンベル則に近づき、それは長い右の尾を持つので、不運な収集者は大きく予測可能な量だけ不運なのです。
答え
14.7
読み方
六番目の調和数の六倍。二つ目のリンクは同じ和を項ごとに、三つ目は六つではなく五つのクーポン、四つ目は六回の投擲のすべての列です。
出典
the coupon collector's problem in Feller, 'An Introduction to Probability Theory and Its Applications', volume 1 (1950), where it is posed as the baseball-card question; the expectation n·H_n and the Gumbel limit of the rescaled waiting time are standard
電卓で解いてみる
これらのリンクは、この問題の数値が入力済みの状態で適切な電卓を開きます。上の行は画面に表示されるはずの内容です。ぜひ自分で確認してください。