クーポン収集者の問題

確率論において、クーポン収集家の問題とは、「すべてのクーポンを集めて勝つ」コンテストの数学的分析を指します。これは、次のような質問をします。特定の製品 (例: 朝食用シリアル) の各ボックスにクーポンが入っており、n種類のクーポンがある場合、 n 枚のクーポンをすべて集めるのにt個以上のボックスを購入する必要がある確率はどれくらいですか? 別の言い方をすると、n 枚のクーポンがある場合、各クーポンを少なくとも 1 回引くまでに、何枚のクーポンを交換抽選で引く必要があると予想されますか? この問題の数学的分析により、必要な試行回数の予想値は に比例して増加することが明らかになっています。^[a]たとえば、n  = 50 の場合、50 枚のクーポンをすべて集めるのに平均で約 225 ^[b]回の試行が必要です。 ${\displaystyle \Theta (n\log(n))}$

第二種スターリング数の定義により、ちょうどT 回の描画が必要となる確率はです。スターリング数の生成関数を操作することにより、Tのすべてのモーメントを明示的に計算できます。一般に、k番目のモーメントは で、 は微分演算子 です。たとえば、0 番目のモーメントは で、1 番目のモーメントは で、これはなどと 明示的に評価できます。$${\displaystyle {\frac {S(T-1,n-1)n!}{n^{T}}}}$$$${\displaystyle f_{k}(x):=\sum _{T}S(T,k)x^{T}=\prod _{r=1}^{k}{\frac {x}{1-rx}}}$$${\displaystyle (n-1)!((D_{x}x)^{k}f_{n-1}(x)){\Big |}_{x=1/n}}$${\displaystyle D_{x}}$${\displaystyle d/dx}$$${\displaystyle \sum _{T}{\frac {S(T-1,n-1)n!}{n^{T}}}=(n-1)!f_{n-1}(1/n)=(n-1)!\times \prod _{r=1}^{n-1}{\frac {1/n}{1-r/n}}=1}$$${\displaystyle (n-1)!(D_{x}xf_{n-1}(x)){\Big |}_{x=1/n}}$${\displaystyle nH_{n}}$

時間T をn 枚のクーポンをすべて集めるのに必要な抽選回数とし、t _{i を}i  − 1 枚のクーポンを集めた後にi番目のクーポンを集めるのにかかる時間とします。すると となります。Tとt _{i を}ランダム変数と考えます。新しいクーポンを集める確率が であることに注意してください。したがって、は期待値 の幾何分布に従います。期待値の線形性により、次の式が得られます。 ${\displaystyle T=t_{1}+\cdots +t_{n}}$${\displaystyle p_{i}={\frac {n-(i-1)}{n}}={\frac {n-i+1}{n}}}$${\displaystyle t_{i}}$${\displaystyle {\frac {1}{p_{i}}}={\frac {n}{n-i+1}}}$

${\displaystyle {\begin{aligned}\operatorname {E} (T)&{}=\operatorname {E} (t_{1}+t_{2}+\cdots +t_{n})\\&{}=\operatorname {E} (t_{1})+\operatorname {E} (t_{2})+\cdots +\operatorname {E} (t_{n})\\&{}={\frac {1}{p_{1}}}+{\frac {1}{p_{2}}}+\cdots +{\frac {1}{p_{n}}}\\&{}={\frac {n}{n}}+{\frac {n}{n-1}}+\cdots +{\frac {n}{1}}\\&{}=n\cdot \left({\frac {1}{1}}+{\frac {1}{2}}+\cdots +{\frac {1}{n}}\right)\\&{}=n\cdot H_{n}.\end{aligned}}}$

ここでH _{n は}n番目の調和数です。調和数の 漸近解析を使用すると、次の式が得られます。

${\displaystyle \operatorname {E} (T)=n\cdot H_{n}=n\log n+\gamma n+{\frac {1}{2}}+O(1/n),}$

ここで、 はオイラー・マスケローニ定数です。 ${\displaystyle \gamma \approx 0.5772156649}$

マルコフ不等式を使用して目的の確率を制限します。

${\displaystyle \operatorname {P} (T\geq cnH_{n})\leq {\frac {1}{c}}.}$

上記は、すでにいくつかのクーポンを収集している場合に対応するために少し変更することができます。すでに収集されたクーポンの数を kとすると、次のようになります。

${\displaystyle {\begin{aligned}\operatorname {E} (T_{k})&{}=\operatorname {E} (t_{k+1}+t_{k+2}+\cdots +t_{n})\\&{}=n\cdot \left({\frac {1}{1}}+{\frac {1}{2}}+\cdots +{\frac {1}{n-k}}\right)\\&{}=n\cdot H_{n-k}\end{aligned}}}$

そして、元の結果が得られます。 ${\displaystyle k=0}$

ランダム変数t _iの独立性を利用すると、次の式が得られます。

${\displaystyle {\begin{aligned}\operatorname {Var} (T)&{}=\operatorname {Var} (t_{1}+\cdots +t_{n})\\&{}=\operatorname {Var} (t_{1})+\operatorname {Var} (t_{2})+\cdots +\operatorname {Var} (t_{n})\\&{}={\frac {1-p_{1}}{p_{1}^{2}}}+{\frac {1-p_{2}}{p_{2}^{2}}}+\cdots +{\frac {1-p_{n}}{p_{n}^{2}}}\\&{}=\left({\frac {n^{2}}{n^{2}}}+{\frac {n^{2}}{(n-1)^{2}}}+\cdots +{\frac {n^{2}}{1^{2}}}\right)-\left({\frac {n}{n}}+{\frac {n}{n-1}}+\cdots +{\frac {n}{1}}\right)\\&{}=n^{2}\cdot \left({\frac {1}{1^{2}}}+{\frac {1}{2^{2}}}+\cdots +{\frac {1}{n^{2}}}\right)-n\cdot \left({\frac {1}{1}}+{\frac {1}{2}}+\cdots +{\frac {1}{n}}\right)\\&{}<{\frac {\pi ^{2}}{6}}n^{2}\end{aligned}}}$

（バーゼル問題を参照）。 ${\displaystyle {\frac {\pi ^{2}}{6}}={\frac {1}{1^{2}}}+{\frac {1}{2^{2}}}+\cdots +{\frac {1}{n^{2}}}+\cdots }$

チェビシェフの不等式を使用して目的の確率を制限します。

${\displaystyle \operatorname {P} \left(|T-nH_{n}|\geq cn\right)\leq {\frac {\pi ^{2}}{6c^{2}}}.}$

上側裾のより強い裾推定は次のようにして得られる。最初の試行で - 番目のクーポンが選択されなかったイベントを とする。すると ${\displaystyle {Z}_{i}^{r}}$${\displaystyle i}$${\displaystyle r}$

${\displaystyle {\begin{aligned}P\left[{Z}_{i}^{r}\right]=\left(1-{\frac {1}{n}}\right)^{r}\leq e^{-r/n}.\end{aligned}}}$

したがって、 については となる。クーポンの和集合により、 が得られる。 ${\displaystyle r=\beta n\log n}$${\displaystyle P\left[{Z}_{i}^{r}\right]\leq e^{(-\beta n\log n)/n}=n^{-\beta }}$${\displaystyle n}$

${\displaystyle {\begin{aligned}P\left[T>\beta n\log n\right]=P\left[\bigcup _{i}{Z}_{i}^{\beta n\log n}\right]\leq n\cdot P[{Z}_{1}^{\beta n\log n}]\leq n^{-\beta +1}.\end{aligned}}}$

• ピエール＝シモン・ラプラスだけでなく、ポール・エルデシュとアルフレッド・レーニもTの分布に関する極限定理を証明した。この結果は以前の限界値のさらなる拡張である。証明は^[1]に記載されている。

${\displaystyle \operatorname {P} (T<n\log n+cn)\to e^{-e^{-c}},{\text{ as }}n\to \infty .}$これはガンベル分布です。マルチンゲールによる簡単な証明は次のセクションで示します。

• ドナルド・J・ニューマンとローレンス・シェップは、各クーポンをm 部収集する必要がある場合のクーポン収集者の問題を一般化しました。T _{m を}各クーポンがm部収集される最初の時点とします。彼らは、この場合の期待値が次の式を満たすことを示しました。

${\displaystyle \operatorname {E} (T_{m})=n\log n+(m-1)n\log \log n+O(n),{\text{ as }}n\to \infty .}$

ここでm は固定されています。m = 1 のとき、期待値の前述の式が得られます。

• 同じくエルデシュとレンイによる一般的な一般化:

${\displaystyle \operatorname {P} \left(T_{m}<n\log n+(m-1)n\log \log n+cn\right)\to e^{-e^{-c}/(m-1)!},{\text{ as }}n\to \infty .}$

• フィリップ・フラジョレらによると、^非一様確率分布の一般的なケースでは、

${\displaystyle \operatorname {E} (T)=\int _{0}^{\infty }\left(1-\prod _{i=1}^{m}\left(1-e^{-p_{i}t}\right)\right)dt.}$

これは次の式に等しい

${\displaystyle \operatorname {E} (T)=\sum _{q=0}^{m-1}(-1)^{m-1-q}\sum _{|J|=q}{\frac {1}{1-P_{J}}},}$

ここで、mは収集するクーポンの数を表し、P _{J は}クーポンセットJ内のいずれかのクーポンを取得する確率を表します。

^{このセクションは[3]}に基づいています。

を抽選後にまだ見られないクーポンの数として、離散ランダム過程を定義します。ランダム過程は、状態、遷移確率 を持つマルコフ連鎖によって生成されるシーケンスにすぎません。ここで を定義します。すると、 であるため、マルチンゲールです。したがって、 が成り立ちます。特に、任意の に対して極限法則が成り立ちます。これは に対して極限法則が成り立つことを示唆しています。 ${\displaystyle N(0),N(1),\dots }$${\displaystyle N(t)}$${\displaystyle t}$${\displaystyle n,n-1,\dots ,1,0}$$${\displaystyle p_{i\to i-1}=i/n,\quad p_{i\to i}=1-i/n}$$$${\displaystyle M(t):=N(t)\left({\frac {n}{n-1}}\right)^{t}}$$$${\displaystyle E[M(t+1)|M(t)]=(n/(n-1))^{t+1}E[N(t+1)|N(t)]=(n/(n-1))^{t+1}(N(t)-N(t)/n)=M(t)}$$${\displaystyle E[N(t)]=n(1-1/n)^{t}}$${\displaystyle \lim _{n\to \infty }E[N(n\ln n+cn)]=e^{-c}}$${\displaystyle c>0}$${\displaystyle T}$

より一般的には、それぞれはマルチンゲール過程であり、これにより のすべてのモーメントを計算できます。たとえば、別の極限法則 を与えます。より一般的には、のすべてのモーメントが定数に収束することを意味するため、 は 上の何らかの確率分布に収束します。 ${\displaystyle \left({\frac {n}{n-k}}\right)^{t}N(t)\cdots (N(t)-k+1)}$${\displaystyle N(t)}$$${\displaystyle E[N(t)^{2}]=n(n-1)\left({\frac {n-2}{n}}\right)^{t}+n\left({\frac {n-1}{n}}\right)^{t},\quad n\geq 2}$$${\displaystyle \lim _{n\to \infty }Var[N(n\ln n+cn)]=e^{-c}}$$${\displaystyle \lim _{n\to \infty }E[N(n\ln n+cn)\cdots (N(n\ln n+cn)-k+1)]=e^{-kc}}$$${\displaystyle N(n\ln n+cn)}$${\displaystyle 0,1,2,\dots }$

を極限分布に従うランダム変数とします。新しい変数 を導入することで、 両辺を明示的に合計することができます。${\displaystyle N}$$${\displaystyle {\begin{aligned}E[1]&=1\\E[N]&=e^{-c}\\E[N(N-1)]&=e^{-2c}\\E[N(N-1)(N-2)]&=e^{-3c}\\&\vdots \end{aligned}}}$$${\displaystyle t}$$${\displaystyle E[1+Nt/1!+N(N-1)t^{2}/2!+\cdots ]=1+e^{-c}t/1!+e^{-2c}t^{2}/2!+\cdots }$$${\displaystyle E[(1+t)^{N}]=e^{e^{-c}t}}$

極限ではとなり、これはまさに極限法則が示す通りです。 ${\displaystyle t\to -1}$${\displaystyle Pr(N=0)=e^{-e^{-c}}}$

導関数を複数回取ると、がポアソン分布であることがわかります。 ${\displaystyle d/dt}$${\displaystyle Pr(N=k)={\frac {e^{-kc}}{k!}}e^{-e^{-c}}}$

• マクドナルドのモノポリー– クーポン収集の問題の一例で、セット内の一部のクーポンをより希少なものにすることで難易度をさらに高めている
• ワターソン推定量
• 誕生日の問題

• 「クーポン コレクター問題」、Ed Pegg, Jr.、Wolfram デモンストレーション プロジェクト。Mathematica パッケージ。
• クーポン収集者は、シングル、ダブル、トリプルなどをいくつ期待すべきでしょうか? 、 Doron Zeilbergerによる短いメモ。