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

$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\left(1+\dfrac{1}{2}+\cdots +\dfrac{1}{n}\right)$$ を得る。

$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$ 種類持っている状態から，必ず1回は試行する（第1項），さらに確率 $\dfrac{n-k}{n}$ で追加で平均 $E_{k+1}$ 回試行する（第2項），確率 $\dfrac{k}{n}$ で追加で平均 $E_k$ 回試行する（第3項））。

ただし，$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\left(1+\dfrac{1}{2}+\cdots +\dfrac{1}{n}\right)$