2015/03/18

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

分野: データの分析,確率  レベル: マニアック

コンプガチャの期待値:
$n$ 種類,等確率のコンプガチャで全ての景品を集めるのに必要な回数の期待値は $n(1+\dfrac{1}{2}+\dfrac{1}{3}+\cdots +\dfrac{1}{n})$ である。

コンプガチャについて。確率の練習問題として上式を二通りの方法で証明してみます。

コンプリートガチャとは

まず,今回考える問題の設定をきちんと説明します。

  • 1回ガチャを行うと,$n$ 種類の景品のうち1種類の景品がもらえる。
  • どの景品が当たる確率も等確率,つまり $\dfrac{1}{n}$ である。同じ景品が何回も連続することもある。
  • $n$ 種類の景品を全て集める(コンプリートする)のに必要な回数の期待値はいくらか?

※実際のコンプガチャでは等確率でない場合が多いです(レアなものがあったりする)。

必要な回数の期待値を求める

ここからガチ数学ゾーンなので証明に興味がない方は最後の「考察」まで飛んで下さい。

では,冒頭の主張を証明します。期待値の線形性→和の期待値は期待値の和を使う方法です。

証明

$k$ 種類持っている状態から新たに1種類ゲットするまでにかかる回数を $X_k$(確率変数)とおく。
もとめる期待値は $N=E[X_0+X_1+\cdots +X_{n-1}]$
ここで期待値の線形性より $N=\displaystyle\sum_{k=0}^{n-1}E[X_k]$

あとは $E[X_k]$ を求めればよい。
$X_k=m$ となる確率は,$m-1$ 回失敗して次に成功する確率なので,$\left(\dfrac{k}{n}\right)^{m-1}\left(1-\dfrac{k}{n}\right)$

よって,$E[X_k]=\displaystyle\sum_{m=1}^{\infty}m\left(\dfrac{k}{n}\right)^{m-1}\left(1-\dfrac{k}{n}\right)$

頑張って計算すると(注),$E[X_k]=\dfrac{1}{1-\frac{k}{n}}=\dfrac{n}{n-k}$
よって,$N=\displaystyle\sum_{k=0}^{n-1}\dfrac{n}{n-k}=n(1+\dfrac{1}{2}+\cdots +\dfrac{1}{n})$ を得る。

注:等比×等差の和を求める2通りの方法を用いて得られる式:
$1+2r+3r^2+4r^3+\cdots =\dfrac{1}{(1-r)^2}$
において $r=\dfrac{k}{n}$ とおくと,$\displaystyle\sum_{m=1}^{\infty}m\left(\dfrac{k}{n}\right)^{m-1}=\dfrac{1}{(1-\frac{k}{n})^2}$

別の証明方法

次は,期待値の漸化式を立てることで証明する方法です。こちらの方が考え方がやや難しいですが計算は楽です。

証明

$k$ 種類持っている状態からスタートしてコンプするまでにかかる回数の期待値を $E_k$ とおく。求めたいのは $E_0$ である。

$k$ 種類持っている状態で新しい景品が手に入る確率は $\dfrac{n-k}{n}$,失敗する確率は $\dfrac{k}{n}$ なので,
$E_k=1+\dfrac{n-k}{n}E_{k+1}+\dfrac{k}{n}E_k\:(k=0,1,\cdots ,n-1)$
である(ただし,$k=n-1$ でも漸化式が成り立つように $E_n=0$ とする)。

これを変形すると,
$E_k=E_{k+1}+\dfrac{1}{1-\frac{k}{n}}$

よって,$E_0=\displaystyle\sum_{k=0}^{n-1}\dfrac{1}{1-\frac{k}{n}}=n(1+\dfrac{1}{2}+\cdots +\dfrac{1}{n})$

考察

以下,$a_n=1+\dfrac{1}{2}+\dfrac{1}{3}+\cdots +\dfrac{1}{n}$ と書きます。
$n$ 種類コンプリートするのに必要な回数の期待値は $na_n$ 回であることが分かりました。

$n$ が十分大きいとき $a_n\simeq \log n$ である(→調和級数1+1/2+1/3…が発散することの証明)のでコンプガチャの回数の期待値はおよそ $n\log n$ 回であると言えます。

つまり,$n$ 種類コンプするためには平均して種類数の $\log n$ 倍の回数くらいガチャを行う必要があるのです。

$\log 10\simeq 2.3,\log 100\simeq 4.6$ なので,
10種類だとコンプするのにだいたい23回,
100種類だとコンプするのにだいたい460回かかる

注:より精密に計算するには $1+\dfrac{1}{2}+\cdots +\dfrac{1}{n}\simeq\log n+\gamma$($\gamma$ はオイラー定数)を使った方がよいです。

なお,この記事の議論はあくまで期待値,平均の話です。当然ですが,期待値よりずっと少ない回数でコンプできる場合も,なかなかコンプできない場合もあります。

期待値の二倍頑張ればかなりの確率でコンプできます。→ブールの不等式の証明と応用例

先日,おジャ魔女どれみのガチャをやってみたのですが,いきなり2回連続で同じのが出てきたのですぐにやめました。

Tag: 難しめの数学雑学・ネタまとめ

分野: データの分析,確率  レベル: マニアック