数酸

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

非復元抽出型のクーポンコレクター問題

{ n }種類のアイテムが{ m }コずつ計{ N(=nm) }コ入ったガチャがある。引いているあいだにアイテムの補充はないとして、すべての種類をコンプリートするまでに引く回数の期待値{ E_m(n) }を求めましょう。結果は以下のようになります。

 

{\displaystyle E_m(n)=N(1-\theta)+1  }

{\displaystyle \theta^{-1}=(1+\frac{1}{m})(1+\frac{1}{2m})+...+(1+\frac{1}{(n-1)m}) }

 

{ \theta }はだいたい、引かずに済むガチャの割合を表しています。

特に{ m=2 }の場合は

{\displaystyle E_2(n)=2n+1-\frac{(2n)!!}{(2n-1)!!} }

とも表せます。

たとえば10種類のアイテムが３つずつ入っている場合は{ \theta=0.4191... }で{ E_3(10)=18.42.... }なので平均して18回程度コンプリートまでに引く必要があります。

 

Proof

{ p_k }で、{ k }回目にまだコンプリートできていない確率とすると、包除原理から

{ p_0=1 }

{\displaystyle p_1=\binom{n}{1}\frac{\binom{N-m}{1}}{\binom{N}{1}}-\binom{n}{2}\frac{\binom{N-2m}{1}}{\binom{N}{1}}+\binom{n}{3}\frac{\binom{N-3m}{1}}{\binom{N}{1}}+... }

 {\displaystyle p_2=\binom{n}{1}\frac{\binom{N-m}{2}}{\binom{N}{2}}-\binom{n}{2}\frac{\binom{N-2m}{2}}{\binom{N}{2}}+\binom{n}{3}\frac{\binom{N-3m}{2}}{\binom{N}{2}}+...}

{\displaystyle p_3=\binom{n}{1}\frac{\binom{N-m}{3}}{\binom{N}{3}}-\binom{n}{2}\frac{\binom{N-2m}{3}}{\binom{N}{3}}+\binom{n}{3}\frac{\binom{N-3m}{3}}{\binom{N}{3}}+...} 

 {... }

これを縦に集計していくと

{\displaystyle E_m(n)=\sum_{k=0}^\infty p_k}

{\displaystyle =1+\sum_{k=1}^{N-m}\binom{n}{1}\frac{\binom{N-m}{k}}{\binom{N}{k}}-\sum_{k=1}^{N-2m}\binom{n}{2}\frac{\binom{N-2m}{k}}{\binom{N}{k}}+... }

{\displaystyle  =1+\sum_{j=1}^{n-1} (-1)^{j-1} \binom{n}{j}\sum_{k=1}^{N-jm} \frac{\binom{N-jm}{k}}{\binom{N}{k}} }

 

{\displaystyle \sum_{k=1}^{N-jm} \frac{\binom{N-jm}{k}}{\binom{N}{k}}=\frac{N-jm}{jm+1}=\frac{N+1}{jm+1}-1 }

 なので(※)

{\displaystyle  =1+\sum_{j=1}^{n-1} (-1)^{j-1} \binom{n}{j} (\frac{N+1}{jm+1}-1) }

{\displaystyle  =N+1+\sum_{j=0}^{n} (-1)^{j-1} \binom{n}{j}(\frac{N+1}{jm+1}-1) }

 

{\displaystyle  =N+1+(N+1)\sum_{j=0}^{n} (-1)^{j-1} \binom{n}{j}\frac{1}{jm+1} }

{\displaystyle  =N+1-\frac{N+1}{m}\sum_{j=0}^{n} (-1)^j \binom{n}{j}\frac{1}{j+\frac{1}{m}}  }

 

soratobipenguin.hatenablog.com

で示した

{\displaystyle \sum_{k=0}^n \frac{(-1)^k {}_nC_k }{k+\alpha} =\frac{n!}{\alpha(\alpha+1)...(\alpha+n)} }

 

を適用して

 {\displaystyle  =N+1-\frac{N+1}{m}\frac{n!}{\frac{1}{m}(1+\frac{1}{m})...(n+\frac{1}{m})} }

  {\displaystyle  =N+1-\frac{n!}{\frac{1}{m}(1+\frac{1}{m})...(n-1+\frac{1}{m})} }

  {\displaystyle  =N+1-N\frac{(n-1)!}{(1+\frac{1}{m})...(n-1+\frac{1}{m})} }

より示される。□

 

 

 (※)正整数{ a,b }　{ a \gt b }に対して

{\displaystyle \sum_{k=1}^{b}\frac{\binom{b}{k}}{\binom{a}{k}}=\frac{b}{a-b+1}  }

 

 { a }コの球が袋に入っており、そのうち{ b }コが白玉、残りは赤玉とする。

非復元抽出で袋から球を、赤玉が出るまで引き続ける。それまでに引いた白玉の個数を{ X }とする。

{\displaystyle P(X \ge k)=\frac{\binom{b}{k}}{\binom{a}{k}} }　であるから

{\displaystyle E[X]=\sum_{k=1}^b P(X\ge k)=\sum_{k=1}^{b}\frac{\binom{b}{k}}{\binom{a}{k}} }

 一方、各白玉ごとにみると、その白玉がどの赤玉よりも先に出る確率は{ \frac{1}{a-b+1} }であり、白玉は{ b }コあるから

{\displaystyle E[X]=\frac{b}{a-b+1} }□