简介

相信大家都在高中接触过超几何分布. 超几何分布是不放回的, 该分布给出了抽取 $n$ 次后抽到次品次数的概率. 如果一个随机变量 $X$ 服从于超几何分布, 那么有
$$
P(X=k)=\frac{C_{N}^kC_{M-N}^{n-k}}{C_{M}^{n}}
$$
其中 $k$ 为抽取到的次品数, $M$ 为总数, $N$ 为总次品数.

问题

生活中很多变量都服从于超几何分布, 我们举个例子

假设你们班要选出 $10$ 个人参加某个活动, 但是想要参加活动的人却有 $40$ 个人, 那么就要采取抽纸条的方式来选出参加活动的人. 准备 $40$ 张纸条, 其中有 $10$ 张是被标记了的. $40$ 个候选人每人抽取一张纸条, 抽到被标记纸条的人就可以参加活动.

当已经有 $n$ 个人抽取了之后, $n$ 个人里面有 $X$ 个人可以参加活动, 这个 $X$ 就服从于超几何分布. 现在我们想要讨论的问题是: 这样的抽取公平吗? 先抽和后抽对你抽到标记纸条的概率有没有影响? 再抽象一点, 即如果第 $n$ 次抽取时, 前面 $n-1$ 次抽取的结果都未知, 那么这次抽取抽到次品的概率是多少?

直觉告诉我们, 应该是公平的, 也就是说在这样一个无返回抽样中, 无论先后, 抽取到次品的概率都是一样的, 并且这个值应该就是 $N/M$ .

证明

我们先说明几个数学符号, 以便后续推导

$N$, $M$ 分别为次品数和总数
$X_1,X_2,\dots,X_n$ 分别为第 $n$ 次抽取抽取到的次品个数 ( $X_n$ 服从两点分布, 即其值要么 $0$ 要么 $1$)

首先, 我们可以立即得出, $P(X_1=1) = \frac{N}{M}$ . 然后我们尝试计算 $P(X_2=1)$
$$
\begin{aligned}
P(X_2=1)&=P(X_2=1,X_1=1)+P(X_2=1,X_1=0)\\
&=P(X_2=1\mid X_1=1)P(X_1=1)+P(X_2=1\mid X_1=0)P(X_1=0)\\
&=\frac{N}{M}\frac{N-1}{M-1}+\frac{M-N}{M}\frac{N}{M-1}\\
&=\frac{N(M-N+N-1)}{M(M-1)}\\
&=\frac{N}{M}
\end{aligned}
$$
果然, $P(X_2=1)$ 也等于 $\frac{N}{M}$ .

不过… 好像还是没有什么思路, 那我们继续计算 $P(X_3=1)$
$$
\begin{aligned}
P(X_3=1)&=\sum_{X_1}\sum_{X_2}P(X_3,X_2,X_1)\\
&=\sum_{X_1}\sum_{X_2}P(X_3\mid X_2,X_1)P(X_2\mid X_1)P(X_1)\\
&=\left(\frac{N}{M}\frac{N-1}{M-1}\frac{N-2}{M-2}+\frac{N}{M}\frac{M-N}{M-1}\frac{N-1}{M-2}\right)\\&+\left(\frac{M-N}{M}\frac{N}{M-1}\frac{N-1}{M-2}+\frac{M-N}{M}\frac{M-N-1}{M-1}\frac{N}{M-2}\right)
\end{aligned}
$$
并且有
$$
\frac{N}{M}\frac{N-1}{M-1}\frac{N-2}{M-2}+\frac{N}{M}\frac{M-N}{M-1}\frac{N-1}{M-2}=\frac{N}{M}\frac{N-1}{M-1}\\
\frac{M-N}{M}\frac{N}{M-1}\frac{N-1}{M-2}+\frac{M-N}{M}\frac{M-N-1}{M-1}\frac{N}{M-2}=\frac{M-N}{M}\frac{N}{M-1}
$$
于是同样的 $P(X_3=1)=\frac{N}{M}$ .

现在我们思考 $P(X_3=1)$ 与 $P(X_2=1)$ , $P(X_2=1)$ 与 $P(X_1=1)$ 之间有什么关系. 我们想象有很多轨迹, 每条轨迹最终都可以到达 $X_2=1$ 这种情况, 而将所有的能达到 $X_2=1$ 的轨迹产生的概率相加, 就是 $P(X_2=1)$ . $\frac{N}{M}\frac{N-1}{M-1}$ (第一次抽中, 第二次抽中) 和 $\frac{M-N}{M}\frac{N}{M-1}$ (第一次没抽中, 第二次抽中) 最终都可以达到第二次抽中这个结果 (也就是 $X_2=1$), 而也就只有这两条轨迹, 因此它们的概率相加便是 $P(X_2)=1$ .

类似的, 我们考虑 $X_3=1$ 的各个轨迹. $X_3=1$ 的轨迹和 $X_2=1$ 的轨迹有没有什么关联? 当然有, $X_3=1$ 的轨迹可以由 $X_2=1$ 的轨迹 “派生” 出来. 每一条 $X_2=1$ 轨迹都可以派生为两条 $X_3=1$ 轨迹, 比如说 $\frac{N}{M}\frac{N-1}{M-1}$ (第一次抽中, 第二次抽中), 这一条 $X_2=1$ 轨迹, 可以派生出 $\frac{N}{M}\frac{N-1}{M-1}\frac{N-2}{M-2}$ (第一次抽中, 第二次抽中, 第三次抽中) 与 $\frac{N}{M}\frac{(M-1)-(N-1)}{M-1}\frac{N-1}{M-2}$ (第一次抽中, 第二次没抽中, 第三次抽中) 两条轨迹, 即第二次抽中与没抽中的区别. 而 $X_4=1$ 的轨迹与 $X_3=1$ 的轨迹, $X_5=1$ 的轨迹与 $X_4=1$ 的轨迹, 乃至 $X_n=1$ 的轨迹与 $X_{n-1}=1$ 的轨迹之间, 都有这种派生关系. 如果能够证明, 一条轨迹出现的概率等于其派生出的两条轨迹出现的概率之和 (前面的计算已经看出在 $n=1,2$ 时满足这种关系), 那么就能够用数学归纳法证明每次抽取抽到次品的概率是相同的. 于是就要证明
$$
\cdots \frac{N-a}{M-b} = \cdots\frac{N-a}{M-b}\frac{N-a-1}{M-b-1}+\cdots\frac{(M-b)-(N-a)}{M-b}\frac{N-a}{M-b-1}
$$
由于 $X_n=1$ 的某条轨迹派生出 $X_{n+1}=1$ 的轨迹的过程中, 轨迹前面 $n-1$ 个动作 (即是否抽取到) 是不变的, 因此用 $\cdots$ 代替. 上面的式子显然成立, 于是我们就证明了 $P(X_n=1)=P(X_{n-1}=1)=\dots= P(X_1=1)=\frac{N}{M}$ . 也就是说, 游戏是公平的.