破産確定！コンプガチャって確率的に何回ガチャる必要があるのか知ってますか？

さて、今日はコンプガチャにまつわる確率について書いていきたいと思います。

まずそもそもコンプガチャとは、

「有料ガチャアイテムを含む特定の2つ以上の異なるアイテム等を全部揃えることを条件として、ソーシャルゲーム等で使用することができる景品類たる別のアイテム等を利用者に提供する方式」

とのことらしく、複数のレアアイテムを揃えるとさらにレアなやつが手に入るってやつです。

実はこの方式は確率的に考えてもなかなかに重課金方式だということでその仕組みを確認していきましょ〜

クーポンコレクター問題

本題のコンプガチャに入る前に、よく知られたクーポンコレクター問題を眺めてみましょう

$X_{i}$ を $1$ から $n$ までの値を等確率で取る確率変数とする。このとき、全種類集まるまでに何回かかるかを $T_{n}=\inf \left\{m |\left\{ X_{1},X_{2},...,X_{m} \right\}=\left\{ 1,2,...,n \right\} \right\}$ とする。
すると、 $\displaystyle \lim_{n \to \infty}\frac{T_{n}}{n\ln{n}}=1$ と確率収束する。

これが物語っているのは、

ガチャが100種類( $n=100$ )くらいあったら全種類集めるには460回( $n\ln{n}$ )くらいガチャを回さないといけない

ということを意味しています。

証明

この照明は2段階に分けて証明していきます。

step.1

まず、 $\tau^{n}_{k}=\inf \left\{m |\left\{ X_{1},X_{2},...,X_{m} \right\}は異なる物がk種類 \right\}$ を導入し、

$\tau^{n}_{k}-\tau^{n}_{k-1}$ が、幾何分布になることを確認します。

$\tau^{n}_{k}-\tau^{n}_{k-1}$ は、時刻 $\tau^{n}_{k-1}$ からみて、まだ保有していないアイテムを入手するまでにかかる時間を示す確率変数なので、

$\displaystyle Pr(\tau^{n}_{k}-\tau^{n}_{k-1}=x)=(\frac{k-1}{n})^{x-1}(1-(\frac{k-1}{n}))$

となり、無事、幾何分布（指数分布の離散版みたいなものですね〜）であることがわかりました。

パラメータが $p$ である幾何分布は平均が $(1-p)/p$ で分散が $(1-p)/p^2$ となりますね。

step.2

次に $T_{n}=\tau^{n}_{1} + \sum_{k=2}^{n}{(\tau^{n}_{k} - \tau^{n}_{k-1})}$ であることを考えると

$\displaystyle E[ T_{n} ] = 1+\sum_{k=2}^{n}{\frac{n}{n-k+1}} = \sum_{m=1}^{n}{\frac{n}{m}}$

$\displaystyle V[ T_{n} ] = \sum_{k=2}\frac{n(k-1)}{(n-k-1)^{2}} = \sum_{m=1}^{n}{\frac{n(n-m)}{m^2}}$

とわかります。

ここで $\displaystyle \ln{n} \le \sum_{m=1}^{n}{\frac{1}{m}} \le 1+\ln{n}$ であることから、

$\displaystyle \lim_{n \to \infty}E[ \frac{T_{n}}{n\ln{n}} ]=1$ が得られます。

従って、十分に大きな $n$ を考えれば、任意の $\epsilon$ に対して

$\displaystyle Pr( |\frac{T_{n}}{n\ln{n}}-1|\geq \epsilon ) \le Pr(|\frac{T_{n}}{E[T_{n}]}-1|\geq \epsilon/2) \le \frac{V[\frac{T_{n}}{E[T_{n}]}]}{(\epsilon/2)^2}$

（最後の不等式はチェビチェフ）

ここで、 $\displaystyle V[ T_{t}] = \sum_{m=1}^{n}{\frac{n(n-m)}{m^2}} \le n^2 \sum_{m=1}^n{\frac{1}{m^2}}$ を用いることで

$\displaystyle V[\frac{T_{n}}{E[T_{n}]}] = V[ T_{n} ]/(E[ T_{n} ])^2 \leq c \frac{\sum_{m=1}^{n}{m^{-2}}}{(\ln{n})^2} \to 0 (n \to \infty)$

よって期待値の値に確率収束することがわかりました。

コンプガチャ

先ほどのクーポンコレクター問題をコンプガチャ問題に拡張すると

$X_{i}$ を $1$ から $n$ までの値を取る確率変数とする。そのうち、 $1$ から $k$ までの値を取る確率がそれぞれ $\frac{1}{m}$ であるとする（このラベル $1$ から $k$ 個がレアアイテムに相当）。この時、レアアイテムを全て揃えるまでにかかる時間を $T_{k}^{n}=\inf \left\{m |\left\{ X_{1},X_{2},...,X_{m} \right\} \supset \left\{ 1,2,...,k \right\} \right\}$ とする。
すると、 $m \to \infty$ において、 $\frac{T_{k}^{n}}{m\ln{k}}$ が1に確率収束する。