期待値計算|ガチャコンプに必要な回数
n種類のうち1つが等確率で出現する場合に全種類コンプするまでに必要な回数の期待値は
$$
n(1+\frac{1}{2}+\frac{1}{3}+…+\frac{1}{n})
$$
すでにいろいろなサイトに書かれている内容ですが、毎回忘れて、毎回探すので、自分で記事にしました。証明とか入れていますが、基本的に上の式だけ知っていれば大体の場合OKです。
ガチャコンプってなに?
「n種類の景品が当確率で出る場合に、1回500円のガチャを回すとすると、全部集めるまで平均いくら必要か?」という問題です。回す回数の期待値がわかれば、必要な額は「$回数\times1回の額$」で計算できます。
この「回す回数」は上記の式で求めることができます。
コンプまでの期待値の数式について
導出は結構面倒ですが、最終的には、
$$
n(1+\frac{1}{2}+\frac{1}{3}+…+\frac{1}{n})
$$
と、結構シンプルな形になります。
$1+\frac{1}{2}+\frac{1}{3}+…+\frac{1}{n}$の部分は、調和級数と呼ばれています。
$1+\frac{1}{2}+\frac{1}{3}+…+\frac{1}{n}\fallingdotseq log(n)$となることが知られていますので、$n$この景品をコンプするには$n\ log\ n$回程度回せば良いことになります。
プログラミングなどで使う場合は、$n\ log\ n$回が計算量見積もりの参考になります。
期待値は、期待値でしかないので、実際に引くと全然コンプできなかったり、すぐコンプできたりするのが世の中です。
証明
$k$種類持っている状態から、持っていない種類の景品をひくまでにかかる回数を$X_k$とします。
すでに$k$種類保有している状態で新しい景品をひく確率は$\frac{n-k}{n}$、すでに持っているものをひく確率は$\frac{k}{n}$です。
ここで、$X_k=m$、すなわちm-1回ダブった後に新しい景品をひく確率は以下になります。
$$
\biggl (\frac{k}{n}\biggr)^{m-1}\biggl (\frac{n-k}{n}\biggr)
$$
なので、期待値$E(X_k)$は、以下の通り
$$\begin{eqnarray}
E(X_k)&=&\sum_{m=1}^{\infty}m\biggl (\frac{k}{n}\biggr)^{m-1}\biggl (\frac{n-k}{n}\biggr)\\
&=&\biggl (\frac{n-k}{n}\biggr)\sum_{m=1}^{\infty}m\biggl (\frac{k}{n}\biggr)^{m-1}
\end{eqnarray}$$
ここは、ちょっと面倒なので省略しますが、以下の式が成り立ちます。
$$
\sum_{m=1}^{\infty}m\biggl (\frac{k}{n}\biggr)^{m-1} = \frac{1}{(1-\frac{k}{n})^2}
$$
ここの展開、かなり面倒です。数式を書くのが厳しいので割愛します。
なので、期待値$E(X_k)$は以下の式で表すことができます。
$$
E(X_k)=\frac{n}{n-k}
$$
全体の期待値は、$E[X_0]+E[X_1]+…+E[X_{n-1}]$なので、
$$
E = \sum_{k=0}^{n-1}\frac{n}{n-k} = n\biggl(1+\frac{1}{2}+\frac{1}{3}+…+\frac{1}{n}\biggr)
$$
となります。