期待値計算｜ガチャコンプに必要な回数

すでにいろいろなサイトに書かれている内容ですが、毎回忘れて、毎回探すので、自分で記事にしました。証明とか入れていますが、基本的に上の式だけ知っていれば大体の場合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)
$$

となります。