拡張と一般化
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/08/05 15:18 UTC 版)
「クーポンコレクター問題」の記事における「拡張と一般化」の解説
ポール・エルデシュとレーニ・アルフレードは、 T の分布の極限定理を証明した。この結果は、ここまでに述べた境界のさらなる拡張である。 P ( T < n log n + c n ) → e − e − c ( n → ∞ ) {\displaystyle \operatorname {P} (T<n\log n+cn)\to e^{-e^{-c}}\quad (n\to \infty )} ドナルド・J・ニューマン（英語版）とローレンス・シェップ（英語版）は、全クーポンを m 枚ずつ収集する必要がある場合として、クーポンコレクター問題を一般化した。各クーポンを m 枚収集するのにかかる時間を Tm とする。彼らは、この場合の期待値が以下を満たしていることを示した。 E ( T m ) = n log n + ( m − 1 ) n log log n + O ( n ) ( n → ∞ ) {\displaystyle \operatorname {E} (T_{m})=n\log n+(m-1)n\log \log n+O(n)\quad (n\to \infty )} ここで、 m は固定されている。 m = 1のとき、上述の式が得られる。 同じ一般化のもとでエルデシュとレーニは以下を導いた。 P ( T m < n log n + ( m − 1 ) n log log n + c n ) → e − e − c / ( m − 1 ) ! ( n → ∞ ) {\displaystyle \operatorname {P} {\bigl (}T_{m}<n\log n+(m-1)n\log \log n+cn{\bigr )}\to e^{-e^{-c}/(m-1)!}\quad (n\to \infty )} フィリップ・フラジョレ（英語版）によると、不均一な確率分布の一般的なケースでは、以下のようになる。 E ( T ) = ∫ 0 ∞ ( 1 − ∏ i = 1 n ( 1 − e − p i t ) ) d t {\displaystyle E(T)=\int _{0}^{\infty }{\big (}1-\prod _{i=1}^{n}(1-e^{-p_{i}t}){\big )}dt}
※この「拡張と一般化」の解説は、「クーポンコレクター問題」の解説の一部です。
「拡張と一般化」を含む「クーポンコレクター問題」の記事については、「クーポンコレクター問題」の概要を参照ください。
- 拡張と一般化のページへのリンク
