数酸

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

重複して集めるクーポンコレクター問題

{ n }種類のアイテム{ I_1,I_2,...,I_n }からなるガチャでどのアイテムも確率{ \frac{1}{n} }で出現するとする。全てのアイテムを{ m }コずつ重複して集めるまでに引くガチャの回数の期待値{ E_m(n) }を評価してみましょう。１種類ずつ集める場合の期待値はよく知られていますが、複数ずつ集めるとなると証明の難易度が上がり、結果は以下のようになります。

 

(Donald J. Newman 1960)

{\displaystyle E_m(n)=n(\log n+(m-1)\log\log n+C_m+o(1)) }

 

定数{ C_m }は{ C_m=\gamma-\log (m-1)! }

のようですが、今回はここまで証明しません。

 

まず、多項式または級数{ f(x_1,...,x_n) } について、どの{ x_i }についてみても次数が{ m }次以上である項を削除した多項式を{ \{ f(x_1,...,x_n) \} }と表わすことにします。

 

{ k }回目にすべてのアイテムを{ m }種類ずつ集めていない確率{ p_k }は

{\displaystyle p_k=\frac{\{ (x_1+...+x_n)^k  \}}{n^k}|_{(x_1,...,x_n)=(1,...,1)} }

 なので

 {\displaystyle E_m(n)=\sum_{k=0}^\infty\frac{\{ (x_1+x_2+...+x_n)^k \} }{n^k}|_{(x_1,...,x_n)=(1,...,1)}}

 

{\displaystyle S(t)=\sum_{k=0}^{m-1}\frac{t^k}{k!}= \{ e^t \}  } 

{\displaystyle T(t)=\sum_{k=m}^{\infty}\frac{t^k}{k!}=e^t-\{ e^t \} }

と定義します。もちろん{ S(t)+T(t)=e^t }です。

すぐに分かることとして

(1)

{\displaystyle \{ e^{x_1+x_2+...+x_n} \}=e^{x_1+x_2+...+x_n}-T(x_1)T(x_2)...T(x_n) }

(2)

{\displaystyle \{ e^{x_1+x_2+...+x_n} \}=\sum_{k=0}^\infty \frac{\{(x_1+x_2+...+x_n)^k\}}{k!} }

 

{ k! }が{ n^k }だったら{ E_m(n) }の計算に利用できるので、これを置きかえる工夫をします。利用するのは

{\displaystyle  \frac{1}{n^k}=n \int_0^\infty \frac{t^k}{k!}e^{-nt}dt }

これは部分積分から簡単に確認できます。

 

{\displaystyle E_m(n)=n\int_0^\infty (1-(T(t)e^{-t})^n)dt }

 

  {\displaystyle \sum_{k=0}^\infty\frac{\{ (x_1+x_2+...+x_n)^k \} }{n^k}}

{\displaystyle =n\sum_{k=0}^\infty \{ (x_1+x_2+...+x_n)^k \} \int_0^\infty \frac{t^k}{k!}e^{-nt}dt  }

{\displaystyle =n\int_0^\infty e^{-nt} \sum_{k=0}^\infty \frac{\{ tx_1+tx_2+...+tx_n)^k\}}{k!}dt   }

{\displaystyle =n\int_0^\infty e^{-nt} ( e^{t(x_1+...+x_n)}-T(tx_1)...T(tx_n) ) dt  }

{\displaystyle (x_1,...,x_n)=(1,...,1) }を代入すれば結果が得られる。□

 

{\displaystyle \frac{E_m(n+1)}{n+1}-\frac{E_m(n)}{n}=\sum_{k=0}^{m-1} \frac{(m-1)!}{(m-k-1)!} \alpha_k(n)   }

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

但し{\displaystyle \alpha_k(n)=\int_0^1 \frac{x^n}{t^k}dx },　{\displaystyle x=T(t)e^{-t} }

 

{\displaystyle \frac{E_m(n+1)}{n+1}-\frac{E_m(n)}{n}}

{\displaystyle =\int_0^\infty (T(t)e^{-t})^n -(T(t)e^{-t})^{n+1} )dt }

 {\displaystyle =\int_0^\infty (T(t)e^{-t})^n S(t)e^{-t} )dt }

{\displaystyle x=T(t)e^{-t} }と置いて置換積分すると

{\displaystyle dx=(T'(t)-T(t))e^{-t}dt=\frac{t^{m-1}}{(m-1)!}e^{-t}dt }

 なので

 {\displaystyle =\int_0^1 x^n S(t) \frac{(m-1)!}{t^{m-1}} dx } 

  {\displaystyle =\sum_{k=0}^{m-1}\int_0^1   \frac{(m-1)!}{k!}\frac{x^n}{t^{m-k-1}} dx } 

{\displaystyle =\sum_{k=0}^{m-1} \frac{(m-1)!}{k!} \alpha_{m-k-1}(n)   }

より示される。□

 

{\displaystyle \sum_{i \lt n} \frac{1}{i+1}=\log n + {\rm Const} +o(1) }

{\displaystyle \sum_{i \lt n} \frac{1}{i \log i}=\log \log n +{\rm Const}+o(1)  } 

であるからあとは

(1)

{\displaystyle \sum_n \alpha_k(n) \lt \infty }　{ (1 \lt k \lt m) }

(2)

{\displaystyle \alpha_1(n)=\frac{1}{n \log n}+\epsilon_n }　{\displaystyle \sum_n|\epsilon_n|\lt \infty }

 

 を示せば目標を達成します。

 (1)

 {\displaystyle \sum_n \alpha_k(n) =\int_0^1 \frac{dx}{(1-x)t^k} }

であり、発散の可能性は{ x=0,1 }の近傍にある。

{ t \ge 0 }において{ T(t) \le t^m e^t  }であることが級数展開の係数比較から分かるから{ x \le t^m }つまり{ x^{\frac{1}{m}}\le t }

したがって{ x=0 }の近傍では{ x^{-\frac{k}{m}} }のオーダーでおさえられているから発散しない。

一方{ x=1 }の近傍については、{ t \ge 0 }において

{ x=1-S(t)e^{-t}\le 1-e^{-t} }より

{ t \ge -\log(1-x) }であり、

{ k \gt 1 }なら{\displaystyle \frac{1}{x (\log x)^k} }は{ x=0 }の近傍で発散しないことから発散しない。□

 

(2)

まず{ \alpha_1(n) }を上から評価すると

{ t \ge -\log(1-x) }より任意の{ r \lt n }に対して

{\displaystyle t \ge x+\frac{x^2}{2}+...+\frac{x^r}{r}\ge x^r(1+\frac{1}{2}+...+\frac{1}{r}) \ge x^r \log r }

 よって

{\displaystyle \alpha_1(n) \le \int_0^1 \frac{x^{n-r}}{\log r}dx=\frac{1}{(n-r+1)\log r} }

なるべく最後の式が小さくなるような{ r }として{ r=[ \frac{n}{\log n} ] }をとると{ C }を定数として

{\displaystyle \alpha_1(n) \le \frac{1}{n\log n}+C \frac{\log\log n}{n (\log n)^2} }

 とおさえられる(単純だが計算は少々面倒)。

{\displaystyle \int^\infty\frac{\log\log x}{x (\log x)^2} dx =\int^\infty \frac{\log y}{y^2}dy \lt \infty }

なので{\displaystyle  \sum_n \frac{\log\log n}{n (\log n)^2} }は収束する。

 

次に下から評価する。

{ x_0=T(t_0)e^{-t_0}  }　{ t_0 \ge 1 }として

{\displaystyle \alpha_1(n)\ge \int_0^{x_0}\frac{x^n}{t}dx \ge \frac{1}{t_0}\int_0^{x_0}x^n  dx }

{\displaystyle \ge  \frac{1}{t_0}(\int_0^1x^n  dx-\int_{x_0}^1 dx) =\frac{1}{t_0}(\frac{1}{n+1}-1+x_0) }

{\displaystyle =\frac{1}{t_0}(\frac{1}{n+1}-S(t_0)e^{-t_0}) }

さらに{ t \ge 1 }であれば

{\displaystyle S(t)\le t^{m-1}(1+...+\frac{1}{(m-1)!})\le et^{m-1}  }

であるから

{\displaystyle \alpha_1(n)\ge \frac{1}{(n+1)t_0}-t_0^{m-2}e^{1-t_0} }

{ t_0=\log n+m \log \log n }を代入することで{ C }を定数として

{\displaystyle \alpha_1(n) \ge \frac{1}{n\log n}+C \frac{\log\log n}{n (\log n)^2} }

とおさえられる(やはり単純な評価だけど計算は少し面倒)。後は上から評価したときと同様。□

.