「N枚コンプリートの確率(2009/10/15)」

よく話題に出るので「全n種類の○○コンプリート確率」をここにまとめておきます。
この問題は例えば「全100種類あるトレカを何枚買うと全種類コンプリートできるか」の平均枚数を求める問題です。

さっそく計算してみましょう。

まず、一枚目を買うときは100%新規カードが出るので最初の一枚は1回で手に入ります。

次の一枚を買うと1/nですでに手持ちのカードと重複、(n-1)/nで手持ちにない新規カード。
 よって次の新規カードが出るまでには確率をひっくりかえして期待値としてn/(n-1)枚のカードを買う必要があります。
次の一枚を買うと2/nですでに手持ちのカードと重複、(n-2)/nで手持ちにない新規カード。
 よって次の新規カードが出るまでには確率をひっくりかえして期待値としてn/(n-2)枚のカードを買う必要があります。
次の一枚・・・

で計算していくと
全種類コンプリート、すなわちこれがn種類まで増えるまでには

期待値総枚数=n/n + n/(n-1) + n/(n-2) + n/(n-3) + ・・・ + n。
      =n(1/(n) + 1/(n-1) + 1/(n-2) + 1/(n-3) + ・・・・ + 1/1)
の枚数が必要です。

(1/(n) + 1/(n-1) + 1/(n-2) + 1/(n-3) + ・・・・ + 1/1)
の部分にはあいにく簡単な式がありませんのがこれはlog(n)で近似できます。

どういう事かと言うと(1/(n) + 1/(n-1) + 1/(n-2) + 1/(n-3) + ・・・・ + 1/1)
=(1/1 + 1/2 + 1/3 + ・・・・ + 1/(n-2) + 1/(n-1) + 1/(n))
=下図の赤い面積

これをy=1/xグラフ

の緑の面積で近似しようと言うのです。

緑の面積は積分して∫n1(1/x) = log(x)|n1=log(n)-log1 = log(n)-0 = log(n)

と言うわけです。
もちろん近似なので実際は誤差が出ますし緑面積<赤面積なので
本当はもっと多く必要ですが
目安としてのおおまかな値は算出できます。

計算式に戻りますが
期待値総枚数=n(1/(n) + 1/(n-1) + 1/(n-2) + 1/(n-3) + ・・・・ + 1/1)
      =約n(log(n))

よって「全n種類の○○をコンプリートするまでに必要な期待値枚数は約n×log(n)」。

詳細は省きますが赤面積が1/x緑面積で完全に覆い被さるよう多めに見積もるならn×log(n) + nと思えばいいでしょう。

例えば全100枚のトレカがあってそれを普通に買いながらコンプリートしたいならおおよそ
100×log(100)≒100×.4.61=461枚必要と言うわけです。


(ここのlogと書かれてる物は一部の関数電卓では「ln (自然対数ログ)」と書かれているボタンが正解でして
「log(10対数ログ)」ボタンの方ではありません。
100のログを求めて4.605170186が出てくる方です。
なお数学では常にログ=自然対数ログなのでログを取ると言われれば必ずlnボタンです・・・)


最新の日記へ