Q：假设有n种赠券，每种赠券获取几率相同，而且赠券亦无限供应。集齐n种赠券平均要抽多少次？
解答
题目即为求抽取次数的期望 设$T$是收集所有$n$种赠券的次数，$t_{i}$是在收集了第$i-1$种后，到收集到第$i$种所花次数 $T=\sum\limits_{i=1}^{n}{t_{i}}$，$t_{i}(i=1,2,…,n)$相互独立，且$t_{i}\sim Ge(p_{i})$，$p_{i}=\frac{n-i+1}{n}$ 故$E(T)=\sum\limits_{i=1}^{n}E(t_{i})=\sum\limits_{i=1}^{n}\frac{1}{p_{i}}=\frac{n}{n}+\frac{n}{n-1}+…+\frac{n}{1}=nH_{n}$
作为进阶，我们来求一下$T$的方差
$$ \begin{aligned} Var(T) & = \sum_{i=1}^{n}Var(t_{i}) = \sum_{i=1}^{n}\frac{1-p_{i}}{p_{i}^2} \\ & = \sum_{i=1}^{n}\frac{n(i-1)}{(n-i+1)^2} = n\sum_{i=1}^{n}\frac{n-(n-i+1)}{(n-i+1)^2} \\ & = n\sum_{i=1}^{n}(\frac{n}{(n-i+1)^2}-\frac{1}{(n-i+1)}) \\ & = n^2\sum_{i=1}^{n}\frac{1}{i^2}-n\sum_{i=1}^{n}\frac{1}{i} \\ & = n^2H_n^{(2)}-nH_n \end{aligned} $$
加强
加强1
引理：证明$\sum\limits_{k=1}^{n}(-1)^{k+1} \frac{1}{k} C_{n}^{k}=1+\frac{1}{2}+\cdots+\frac{1}{n}$
注意到
$$ \frac{1}{k} C_{n}^{k}=\frac{1}{k}\left(C_{n}^{k}+C_{n-1}^{k-1}\right)=\frac{1}{k} C_{n-1}^{k}+\frac{1}{n} C_{n}^{k} $$
记$f_{n}=\sum\limits_{k=1}^{n}(-1)^{k-1} \frac{1}{k} C_{n}^{k}$，则
$$ \begin{aligned} f_{n}&=\sum_{k=1}^{n}(-1)^{k+1} \frac{1}{k} C_{n}^{k}+(-1)^{n+1} \frac{1}{n}\\ &=\sum_{k=1}^{n-1}(-1)^{k+1} \frac{1}{k} C_{n-1}^{k}+\frac{1}{n} \sum_{k=1}^{n-1}(-1)^{k+1} C_{n}^{k}+(-1)^{n-1} \frac{1}{n} \\ & =f_{n-1}+\frac{1}{n} \sum_{k=1}^{n}(-1)^{k+1} C_{n}^{k}\\&=f_{n-1}+\frac{1}{n} \end{aligned} $$
其中最后一步由于 $$ \sum_{i=1}^{n}(-1)^{k+1}C_n^k=\sum_{i=0}^{n}(-1)^{k+1}C_n^k+C_n^0=C_n^0-\sum_{i=0}^{n}(-1)^{k}C_n^k=1 $$ 故$f_n=f_{n-1}+\frac{1}{n}$,又$f_1=1$，故$f_n=1+\frac{1}{2}+\cdots+\frac{1}{n}$
接下来我们看加强的问题：
Q：假设有n种赠券，每种赠券获取几率相同，而且赠券亦无限供应。每次抽取t个赠券，集齐n种赠券平均要抽多少次？
A：记事件$A_{k,i}$为第$k$次抽取后第$i$种赠券未中的情形,$T$为抽取次数，则
$$ \begin{align*} &\quad\ P(T>k)\\ &=P\left(\mathop{\cup}\limits_{i=1}^{n} A_{k, i}\right)\\ &=\sum_{i=1}^{n} P\left(A_{k, i}\right)-\sum_{1 \leqslant i< j \leqslant n_{i}} P\left(A_{k, i} \cap A_{k, j}\right)+\cdots+(-1)^{n+1} P\left(\cap_{i=1}^{n} A_{k, i}\right) \end{align*} $$
注意到
$$ P\left(\cap_{s=1}^r A_{k, i_{s}}\right)=\left(\frac{C_{n-r}^{t}}{C_{n}^{t}}\right)^{k} ， 1 \leqslant r \leqslant n $$
代入上式，有
$$ P(T>k)=\sum_{r=1}^{n}(-1)^{r+1} C_{n}^{r}\left(\frac{C_{n-r}^{t}}{C_{n}^{t}}\right)^{k} $$
$$ \begin{aligned} E(T) &=\sum_{k=0}^{\infty} P(T>k)=\sum_{k=0}^{\infty} \sum_{k=1}^{n}(-1)^{r+1} C_{n}^{t}\left(\frac{C_{n-r}^{t}}{C_{n}^{t}}\right)^{k}\\ &=\sum_{r=1}^{n}(-1)^{r+1} C_{n}^{r} \sum_{k=0}^{\infty}\left(\frac{C_{n-r}^{t}}{C_{n}^{t}}\right)^{k} \\ &=\sum_{r=1}^{n}(-1)^{r+1} C_{n}^{r} \frac{1}{1-C_{n-r}^{t} / C_{n}^{t}} \end{aligned} $$
我们验证t=1时的情形
$$ \begin{aligned} E(T)&=\sum_{k=1}^{n}(-1)^{r+1} \frac{n}{r} C_{n}^{r}=n \sum_{r=1}^{n}(-1)^{r+1} \frac{1}{r} C_n^r\\ &=n\left(1+\frac{1}{2}+\cdots+\frac{1}{n}\right) \end{aligned} $$
加强2
Q:假设有n种赠券，每种赠券有$a_i$个,每次抽出后放回，问抽到n种赠券的时候抽取次数的期望？
A：记$p_i=\frac{a_i}{\sum\limits_{i=1}^na_i}(i=1,2,…,n)$，事件$A_{k,i}$为第$k$次抽取后第$i$种赠券未中的情形，$T$为抽取次数，显见$\sum\limits_{i=1}^np_i=1$
$$ \begin{aligned} &\quad\ P(T>k)\\ &=P\left(\cup_{i=1}^{n} A_{k, i}\right)\\ &=\sum_{i=1}^{n} P\left(A_{k, i}\right)-\sum_{1 \leqslant i< j \leqslant n_{i}} P\left(A_{k, i} \cap A_{k, j}\right)+\cdots+(-1)^{n+1} P\left(\cap_{i=1}^{n} A_{k, i}\right) \end{aligned} $$
而$P\left(\sum\limits_{s=1}^{r} A_{k, i_{s}}\right)=\left(1-\sum\limits_{j \in J, J= \{ 1.2, \cdots, n \} \backslash\left \{ i_{1}, \ldots, i_{r}\right \} } p_{j}\right)^{k}$ 因此
$$ \begin{aligned} E(T)&=\sum_{k=0}^{\infty}P(T>k)\\ &=\sum_{k=0}^\infty(-1)^{r+1}\sum_{r=1}^n\sum_{1\leqslant i_1 < …<i_r \leqslant n}\left(1-\sum_{j \in J, J= \{ 1.2, \cdots, n \} \backslash\left \{ i_{1}, \ldots, i_{r}\right \} } p_{j}\right)^{k}\\ &=\sum_{r=1}^n(-1)^{r+1}\sum_{1\leqslant i_1 < …<i_r \leqslant n}\sum_{k=0}^\infty\left(1-\sum_{j \in J, J= \{ 1.2, \cdots, n \} \backslash\left \{ i_{1}, \ldots, i_{r}\right \} } p_{j}\right)^{k} \\ &=\sum_{r=1}^n(-1)^{r+1}\sum_{1\leqslant i_1 < …<i_r \leqslant n}\frac{1}{\sum\limits_{j \in J, J= \{ 1.2, \cdots, n \} \backslash\left \{ i_{1}, \ldots, i_{r}\right \} } p_{j}}\\ &=\sum_{r=1}^n\sum_{1\leqslant i_1 < …<i_r \leqslant n}(-1)^{r+1}\frac{1}{p_{i_{1}}+p_{i_{2}}+\cdots+p_{i_{r}}} \end{aligned} $$