1. 高校数学の美しい物語
  2. コンプガチャに必要な回数の期待値の計算

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

更新日時 2021/03/07
コンプガチャの回数の期待値

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

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

目次
  • コンプリートガチャとは

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

  • 別の証明方法

  • 考察

コンプリートガチャとは

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

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

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

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

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

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

証明

kk 種類持っている状態から新たに1種類ゲットするまでにかかる回数を XkX_k(確率変数)とおく。

求める期待値は N=E[X0+X1++Xn1]N=E[X_0+X_1+\cdots +X_{n-1}]

ここで期待値の線形性より N=k=0n1E[Xk]N=\displaystyle\sum_{k=0}^{n-1}E[X_k]

あとは E[Xk]E[X_k] を求めればよい。

Xk=mX_k=m となる確率は,m1m-1 回失敗して次に成功する確率なので,(kn)m1(1kn)\left(\dfrac{k}{n}\right)^{m-1}\left(1-\dfrac{k}{n}\right)

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

頑張って計算すると(注),E[Xk]=11kn=nnkE[X_k]=\dfrac{1}{1-\frac{k}{n}}=\dfrac{n}{n-k}

よって,N=k=0n1nnk=n(1+12++1n)N=\displaystyle\sum_{k=0}^{n-1}\dfrac{n}{n-k}=n\left(1+\dfrac{1}{2}+\cdots +\dfrac{1}{n}\right) を得る。

注:等比×等差の和を求める2通りの方法を用いて得られる式:

1+2r+3r2+4r3+=1(1r)21+2r+3r^2+4r^3+\cdots =\dfrac{1}{(1-r)^2}

において r=knr=\dfrac{k}{n} とおくと,m=1m(kn)m1=1(1kn)2\displaystyle\sum_{m=1}^{\infty}m\left(\dfrac{k}{n}\right)^{m-1}=\dfrac{1}{(1-\frac{k}{n})^2}

別の証明方法

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

証明

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

kk 種類持っている状態で新しい景品が手に入る確率は nkn\dfrac{n-k}{n},失敗する確率は kn\dfrac{k}{n} なので,

Ek=1+nknEk+1+knEk(k=0,1,,n1)E_k=1+\dfrac{n-k}{n}E_{k+1}+\dfrac{k}{n}E_k\:(k=0,1,\cdots ,n-1)

である(ただし,k=n1k=n-1 でも漸化式が成り立つように En=0E_n=0 とする)。

これを変形すると,

Ek=Ek+1+11knE_k=E_{k+1}+\dfrac{1}{1-\frac{k}{n}}

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

考察

以下,an=1+12+13++1na_n=1+\dfrac{1}{2}+\dfrac{1}{3}+\cdots +\dfrac{1}{n} と書きます。

nn 種類コンプリートするのに必要な回数の期待値は nanna_n 回であることが分かりました。

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

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

  • log102.3\log 10\fallingdotseq 2.3 なので,10種類だとコンプするのにだいたい23回かかる
  • log1004.6\log 100\fallingdotseq 4.6 なので,100種類だとコンプするのにだいたい460回かかる

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

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

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

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

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

人気記事
  1. 高校数学の美しい物語
  2. コンプガチャに必要な回数の期待値の計算