<script type="text/javascript" async src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/3.2.2/es5/core.min.js?config=TeX-MML-AM_CHTML">
</script>
<script type="text/x-mathjax-config">
MathJax.Hub.Config({
tex2jax: {
inlineMath: [ ['$','$'], ["\\(", "\\)"] ],
displayMath: [ ['$$','$$'], ["\\[","\\]"] ]
}
});
</script>
# Randomized Algorithm 3.6

## 3.6 The Coupon Collector's problem
\\( n \\) 枚のクーポンがあり, 一回の試行で等確率でその中の \\( 1 \\) 枚を引く.
試行回数 \\(m\\) と全てのクーポンが揃う確率の関係を調べる.

## 3.6.1  基礎的な解析
#### 試行の列の定義

全てのクーポンを少なくとも \\(1\\) 枚得るまでに必要だった回数の確率変数を \\(X\\) とする.
\\(C_1,\ C_2,\ ...,\ C_X\\) でそれぞれの試行を表す\\((C_i\in\{1,\ ...,\ n\})\\).
また, \\(i-1\\) 回目まで引いたことのなかったクーポンを \\(i\\) 回目で初めて引いた試行 \\(C_i\\) を成功という( \\(C_1,\ C_X \\) は明らかに成功).

#### 試行の列を区間に分け, 期待値を計算する.
\\(i\\) 番目の成功の直後から, \\(i+1\\) 番目の成功までを一つの区間とする\\((0\leq i\leq n-1)\\).
区間 \\(i\\) の長さを確率変数 \\(X_i\\) で表す. したがって
\\[X=\sum_{i=0}^{n-1}X_i\\]
さらに \\(i\\) 番目の区間での成功確率を \\(p_i\\) とすると
\\[p_i=\frac{n-i}{n}\\]
よって \\(X_i\\) の期待値は \\(1/p_i=n/(n-i)\\) .
期待値の線形性から
\\[E[X]=E[\sum_{i=0}^{n-1}X_i]=\sum_{i=0}^{n-1}E[X_i]=\sum_{i=0}^{n-1}\frac{n}{n-i}=n\sum_{i=1}^{n}\frac{1}{i}=nH_n\\]
\\(H_n=\ln{n}+\Theta(1)\\) なので結局
\\[E[X]=n\ln{n}+O(n)\\]
さらにこの後, \\(X\\) の値は高確率で期待値の周辺になることをみる.

#### Union Bound による上限
\\(\mathcal E_i^r\\) を \\(r\\) 回の試行で種類 \\(i\\) のクーポンを引かない事象とする.
Proposition B.3.1 より
\\[Pr[\mathcal E_i^r]=\Big(1-\frac{1}{n}\Big)^r\leq e^{-\frac{r}{n}}\\]
\\(r=\beta n\ln{n}\\) のとき
\\[Pr[X>r]=Pr[\cup_{i=1}^n \mathcal E_i^r]\leq \sum_{i=1}^nPr[\mathcal E_i^r]\leq \sum_{i=1}^nn^{-\beta}=n^{-(\beta-1)}\\]
となる.

ここからは, 任意の実数 \\(c\\) に対して, \\(X\\) の値がその期待値である \\(nH_n\\) よりも \\(cn\\) だけ離れる確率を調べる

## 3.6.2 The Poisson Heuristic

\\(X\\) のシャープな集中を示す前に, その直感を得るためにヒューリスティックな議論を示す.

\\(N_i^r\\) を \\(r\\) 回の試行で \\(i\\) が出た回数とする. \\(p=1/n\\) として
\\[Pr[N_i^r=x]=\binom{n}{x}p^x(1-p)^{n-x}\\]
である.

ここで, \\(\lambda\\) を任意の正の実数として, 非負の確率変数 \\(Y\\) と任意の非負実数 \\(y\\) に対して, 以下の分布に従う確率分布を, パラメータ \\(\lambda\\) に対するポアソン分布という.
\\[Pr[Y=y]=\frac{\lambda^ye^{-\lambda}}{y!}\\]

\\(r\rightarrow\infty\\) で \\(\lambda=rp\\) が適切に小さくなるとき, ポアソン分布は二項分布の良い近似となる.
今回 \\(\lambda=r/n\\) は適切に小さいものとして考えて, 以下の近似を得る.
\\[Pr[\mathcal E_i^r]=Pr[N_i^r=0]\approx\frac{\lambda^0e^{-\lambda}}{0!}=e^{-r/n}\\]
ポアソン分布を使うことで, \\(\mathcal E_i^r\ (0\leq i \leq n)\\)　が"**ほとんど独立**"であると主張することができる.

### Claim
\\(1\leq i \leq n\\) と \\(i\\) を含まない添字の部分集合 \\(\{j_1,\ ...,\ j_k\}\\) に対して
\\[Pr[\mathcal E_i^r\ |\ \cap_{l=1}^k\mathcal E_{j_l}^k]\approx Pr[\mathcal E_i^r]\\]
#### (Proof)
\\[Pr[\mathcal E_i^r\ |\ \cap_{l=1}^k\mathcal E_{j_l}^k]=\frac{Pr[\mathcal E_i^r\ \cap\ (\cap_{l=1}^k\mathcal E_{j_l}^k)]}{Pr[\cap_{l=1}^k\mathcal E_{j_l}^k]}=\frac{(1-\frac{k+1}{n})^r}{(1-\frac{k}{n})^r}\approx \frac{e^{-(r+1)k/n}}{e^{-rk/n}}=e^{-r/n}\\]
\\(3\\) つ目の近似は \\(Proposition\ B.3.3\\) より.

この前提のもと \\(m\\) 回の試行で, \\(n\\) 種類のクーポンが揃う確率は
\\[Pr[\neg(\cup_{i=1}^n\mathcal E_i^m)]=Pr[\cap_{i=1}^n(\neg\mathcal E_i^m)]\approx (1-e^{-m/n})^n\approx e^{-ne^{-m/n}}\\]
\\(m=n(\ln{n}+c)\\) とすると
\\[Pr[X>m=n(\ln{n}+c)]=Pr[\cup_{i=1}^n\mathcal E_i^m]\approx Pr[\cap_{i=1}^n(\neg\mathcal E_i^m)]=1-e^{-e^{-c}}\\]
を得る. \\(c=3\\) で \\(0.05\\) ほどになり急速に小さくなる.
以下でより正確な議論を行う.
## 3.6.3 A Sharp Threshold
ここではより厳密な議論を行う.
### Lemma 3.7
\\(m=n(\ln{n}+c)\\) とすると　
\\[\lim_{n\rightarrow\infty}\binom{n}{k}(1-\frac{k}{n})^m=\frac{e^{-ck}}{k!}\\]

### Theorem 3.8
\\(m=n(\ln{n}+c)\\) とすると　
\\[\lim_{n\rightarrow\infty}Pr[X>m]=1-e^{-e^{-c}}\\]

#### (proof)
包除原理より,
\\[Pr[\cup\mathcal Ei^m]=\sum_{k=1}^n(-1)^{k+1}P_k^n\\]
ここで \\(P_k^n\\) は \\(k\\) 個の \\(\mathcal E_i^m\\) が同時に起こる全ての組み合わせの確率の総和. \\(S_k\\) を右辺の部分和とする.
Proposition C.2 より
\\[S_{2k}^n\leq Pr[\cup\mathcal E_i^m]\leq S_{2k+1}^n\\]
対称性と確率の計算方法より
\\[P_k^n=\binom{n}{k}Pr[\cap\mathcal E_i^m]=\binom{n}{m}(1-\frac{k}{n})^m\\]
ここで \\(P_k=e^{-ck}/k!\\) とする. Lemma 3.7 より
\\[\lim_{n\rightarrow\infty}P_k^n=P_k\\]
部分和を \\(P_k\\) に関して定義すると
\\[S_k=\sum(-1)^{j+1}P_j=\sum(-1)^{j+1}\frac{e^{-cj}}{j!}\\]
となり, 右辺は \\(f(c)=1-e^{-e^{-c}}\\) の冪級数展開となり、
\\[\lim_{k\rightarrow\infty}S_k=f(c)\\]
また \\(S_k^n \rightarrow S_k\\) なので十分大きい \\(k\\) で
\\[|S_k^n-S_k| < \epsilon and |S_k-f(c)|<\epsilon\\]
よって
\\[|S_k^n-f(c)|<2\epsilon\\]
となり
\\[|S_{2k}^n-S_{2k+1}^n|<4\epsilon\\]
結局
\\[|Pr[\cup\mathcal E]-f(c)|<4\epsilon\\]
となって, 収束する.

このことから
\\[\lim_{n\rightarrow\infty}Pr[n(\ln{n}-c)\leq X\leq n(\ln{n}+c)]=e^{-e^{-c}}\\]
となる
### Proposition B.2.2
\\( n \geq k \geq 0 \\) とする. 十分大きい \\( n\\) で \\[ \binom{n}{k} \sim \frac{n^k}{k!}\\].

### Proposition B.3.2
全ての \\( n \geq 1 \\) かつ \\( |t| \leq n\\) であるような \\( t, n \in \mathbb{R}\\) に対して,
\\[ e^t\Big(1-\frac{t^2}{n}\Big) \leq \Big(1-\frac{t}{n}\Big)^n\leq e^t \\]