数酸

数学に関して書き留めておこうと思ったものを気まぐれに。

不均等な場合のクーポンコレクター問題

${ n }$ 種類のアイテム ${ I_1,I_2,...,I_n }$ からなるガチャで ${ I_k }$ が当たる正の確率を ${ p_k }$ とする( $\sum_{k=1}^n p_k=1$ )。

このガチャについて全種類コンプリートするまでに引くガチャの回数の期待値 ${ E }$ は

${ J:=\{ I_1,I_2,...,I_n \} }$

${ J }$ の空でない部分集合 ${ L }$ に対して ${ S(L) }$ をそのアイテムに対応する確率の和とすると(例. ${ S(\{ I_1,I_2 \}) =p_1+p_2 }$ )

$E=\sum_{L\subset J, L \neq \emptyset } \frac{(-1)^{\#L-1}}{S(L)}$

3種類の場合を見れば一般の場合も計算方法は全くかわらないので、見た目の煩雑さを避けるために ${ n=3 }$ の場合の証明をみる。書き下すと、３種類のアイテム ${ I_1,I_2,I_3 }$ の出現確率がそれぞれ ${ p,q,r }$ であるとすると

$E=\frac{1}{p}+\frac{1}{q}+\frac{1}{r}-\frac{1}{p+q}-\frac{1}{q+r}-\frac{1}{r+p}+1$

コンプリート達成時の回数を ${ T }$ とする。 ${ t }$ 回目にコンプリートしていないことは ${ T \gt t }$ と表される。 ${ t }$ 回目までにアイテム ${ I_k }$ がまだ出現していない事象を ${ R_i }$ とすると

$P(T \gt t )=P(R_1 \cup R_2 \cup R_3)$

包除原理から

${\displaystyle =P(R_1)+P(R_2)+P(R_3)}$

${\displaystyle -P(R_1 \cap R_2)-P(R_2 \cap R_3)-P(R_3 \cap R_1)}$

${\displaystyle +P(R_1 \cap R_2 \cap R_3 ) }$

たとえば ${ P(R_1) }$ は ${ t }$ 回ずっとアイテム ${ I_1 }$ が出ない確率であるから ${ (1-p)^t }$ と計算できる。他も同様。

${P(R_1 \cap R_2 \cap R_3 ) }$ は ${ t=0 }$ でのみ ${ 1 }$ で、それ以外は ${ 0 }$ であることに注意する。

以上から ${ 0^0=1 }$ として

$P(T \gt t)=(1-p)^t+(1-q)^t+(1-r)^t$

$-(1-p-q)^t-(1-q-r)^t-(1-r-p)^t+0^t$

非負整数値をとる確率変数の期待値計算の便利な公式

$E[T]=\sum_{t=0}^\infty P(T \gt t)$

より計算が完了する。□