问题背景 #

考虑样本空间$M$是${1,...,n}$的所有$m$元子集构成的集合，$|M| = \binom{n}{m}$。命题$Q$定义：随机变量$S$是从$M$中均匀随机抽取的子集，即每个$m$元子集被选中的概率都是$\frac{1}{\binom{n}{m}}$。

对于任意$x\in {1,...,n}$，命题$U$满足：$P(x\in S) = \frac{m}{n}$。

核心问题 #

• 命题$U$是否和$Q$等价？（也就是$Q\iff U$是否成立？）
• 如果$U\implies Q$不成立，那么需要补充什么额外条件才能让这个蕴含关系成立？

原提问者的尝试 #

我认为$Q\implies U$是成立的：如果按照$Q$的定义来生成$S$，那么对于任意$x$，有
$$
P(x\in S) = \frac{\binom{n-1}{m-1}}{\binom{n}{m}} = \frac{m}{n}
$$
不过反过来$U\implies Q$的证明就比较困难了。另外注意到事件之间并不独立：对于$x\neq y\in {1,...,n}$，
$$
P(x\text{ 和 }y\in S) = \frac{\binom{n-2}{m-2}}{\binom{n}{m}} = \frac{(m-1)m}{(n-1)n}\neq P(x\in S)P(y\in S)
$$

解答与分析 #

首先直接给结论：$U$和$Q$并不等价，$U\implies Q$是不成立的，咱们举个具体的小例子就能直观理解：

比如取$n=4$，$m=2$。按照$Q$的规则，所有6个二元子集的概率都是$\frac{1}{6}$，每个元素出现在子集中的概率是$\frac{2}{4}=\frac{1}{2}$，完全符合$U$的要求。

但我们可以构造另一个随机子集$S$，它满足$U$，但绝对不是均匀分布：

• 让$S={1,2}$和$S={3,4}$这两个子集的概率各为$\frac{1}{2}$，剩下的4个子集概率全为0。
• 你算一下就会发现，不管是元素1、2还是3、4，每个元素出现在$S$中的概率都是$\frac{1}{2}$，完全满足$U$的条件，但显然这个$S$的分布和$Q$定义的均匀分布差远了。

那要补充什么条件才能让$U\implies Q$成立呢？

关键是要约束所有高阶的联合包含概率，而不只是单个元素的边缘概率。具体来说，需要补充的条件是：

对于任意$1\leq k\leq m$，以及任意$k$个不同的元素$x_1,x_2,...,x_k\in{1,...,n}$，都有
$$
P(x_1,x_2,...,x_k \in S) = \frac{\binom{n-k}{m-k}}{\binom{n}{m}} = \frac{m(m-1)...(m-k+1)}{n(n-1)...(n-k+1)}
$$

这个条件的意思是，任意$k$个不同元素同时出现在$S$里的概率，要和均匀分布下的概率完全一致。当这个条件对所有$k$从1到$m$都成立时，就能唯一确定$S$是均匀分布的$m$元子集（也就是满足$Q$）。

为什么单个元素的概率不够？因为像上面的反例那样，我们可以把概率“集中”在某些特定子集上，保持每个元素的边缘概率不变，但整体分布完全偏离均匀性。只有当所有阶数的联合概率都匹配均匀分布时，才能保证分布的唯一性。

备注：内容来源于stack exchange，提问作者C.C.