杂想-抽奖问题平凡解

Background

复习概率论的时候看到了对抽奖问题的讨论，突然就想推一下平凡解

总共有\(n\)张票，其中有\(k\)张中奖，问第\(i\)个来抽奖的人中奖的概率。

这应该算是一个最平凡的情形了吧

Solution

整个概率空间可以被划分为\(k+1\)个部分，第\(j\)个部分\(S_j\)表示前\(i-1\)个人中了\(j\)张

那么 \[ ans=\sum_{j=0}^{k} P(S_j)P(A|S_j) \] 其中\(P(A)\)表示第\(i\)个人中奖

对于前\(i-1\)个人中了\(j\)张的情况，有方案数为 \[ cnt_j=\binom{k}{j}\binom{n-k}{i-1-j}(i-1)! \] 所以 \[ P(S_j)=\frac{cnt_j}{\sum_t cnt_t} \] 其中 \[ \sum_t cnt_t=(i-1)!\sum_t \binom{k}{j}\binom{n-k}{i-1-j} \] 后面部分是一个范德蒙德卷积，从而 \[ \sum_t cnt_t=(i-1)!\binom{n}{i-1} \] 从而 \[ \begin{flalign} ans=&\frac{1}{(i-1)!\binom{n}{i-1}}\sum_{j=0}^{k}cnt_jP(A|S_j)\\ &=\frac{1}{(i-1)!\binom{n}{i-1}}\sum_{j=0}^{k}\binom{k}{j}\binom{n-k}{i-1-j}(i-1)!\frac{k-j}{n-i+1}\\ &=\frac{k}{(n-i+1)\binom{n}{i-1}}\sum_{j=0}^{k}\binom{k-1}{j}\binom{n-k}{i-1-j}\\ &=\frac{k}{(n-i+1)\binom{n}{i-1}}\binom{n-1}{i-1}\\ &=\frac{k}{n-i+1}\frac{(i-1)!(n-i+1)!}{n!}\frac{(n-1)!}{(i-1)!(n-i)!}\\ &=\frac{k}{n} \end{flalign} \] 从而中奖概率确实与抽奖顺序无关

over

（久违的推式子环节，真是太舒服了~)

update：

队友给出了一个更加优雅的解法：

考虑数学归纳法：

第一个人中奖的概率显然为\(\frac{k}{n}\)

假设对于第\(j\)个人，他中奖的概率也为\(\frac{k}{n}\),我们来证对于第\(j+1\)个人，其中奖的概率也为\(\frac{k}{n}\)

其中奖的概率为 \[ P_{j+1}=\sum_{i=0}^{p}\binom{p}{i}(\frac{k}{n})^i(\frac{n-k}{n})^{p-i}\frac{k-i}{n-j}\\ 其中p=min(k,j) \] 这里将\(p\)与\(j\)做区分是因为中奖的人数最多只能有\(k\)个

注意到式子中的\(\sum_{i=0}^{p}\binom{p}{i}(\frac{k}{n})^i(\frac{n-k}{n})^{p-i}\)实际上就是一个伯努利分布，所以我们可以化为 \[ \begin{flalign} P_{j+1}&=\frac{k}{n-j}\sum_{i=0}^{p}\binom{p}{i}(\frac{k}{n})^i(\frac{n-k}{n})^{p-i}-\frac{1}{n-j}\sum_{i=0}^{p}\binom{p}{i}(\frac{k}{n})^i(\frac{n-k}{n})^{p-i}i\\ &=\frac{k}{n-j}-\frac{1}{n-j}\frac{k}{n}j\\ &=\frac{k}{n} \end{flalign} \] 其中第二个式子实际上就是伯努利分布的期望

比我的证法短多了，思路也更加清晰。优雅，太优雅了！

over