「なぜ不偏分散はn-1で割るのか？」を確認する
Aru
Aru's テクログ（Aruaru0）
ガチャの期待値｜ガチャコンプに必要な回数を求める
Aru
この記事では、ガチャでアイテムをコンプリートするために必要な回数を計算する方法を解説します。既に多くのサイトで取り上げられている内容ですが、何度も忘れて検索していたので自分のサイトでもまとめることにしました。
全種類コンプするまでに必要な回数の期待値
n種類のうち1つが等確率で出現する場合
$$
n(1+\frac{1}{2}+\frac{1}{3}+…+\frac{1}{n})
$$
Contents
ガチャコンプってなに？
「ガチャコンプ」とは、ガチャで提供されているすべての景品をコンプリートする（全種類集める）ことです。
たとえば、n種類の景品が等しい確率で出るガチャがあったとします。ここで、1回500円でガチャを回すと、「すべての景品を揃えるのにいくら必要になるか」という問題を考えます。
必要な額を求めるためには、まず「すべての景品を集めるまでに何回ガチャを回す必要があるのか」という回す回数の期待値を計算する必要があります。この期待値がわかれば、最終的な金額は「回数 × 1回あたりのガチャの金額」で簡単に計算できます。
この「回す回数」は、記事で紹介する式を使って求めることができます。
コンプまでの期待値
最終的な式
導出は結構面倒ですが、最終的には、
$$
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)
$$
となります。
まとめ
とりあえず、ガチャコンプに必要な回数の期待値を求める式と、導出方法について簡単に解説しました。プログラミングでも使える知識ですので、覚えておいて損はないかと思います。
ABOUT ME
専門分野は並列処理・画像処理・機械学習・ディープラーニング。プログラミング言語はC, C++, Go, Pythonを中心として色々利用。現在は、Kaggle, 競プロなどをしながら悠々自適に活動中