关于逐次调整概率的随机抽取元素算法正确性的疑问

这个方法本质是**无放回简单随机抽样（SRSWOR）**的一种实现，核心是保证每个个体被选中的概率均等（都是30/100），且最终恰好抽到30个样本，下面从两个关键角度拆解：

1. 每个个体被选中的概率都是30/100 #

拿你例子里的第二个个体来算：

• 情况1：第一个个体被选中（概率30/100），此时剩下99个个体要抽29个，第二个被选中的概率是29/99
• 情况2：第一个个体没被选中（概率70/100），此时剩下99个个体要抽30个，第二个被选中的概率是30/99

把两种情况的概率相加：
(30/100)*(29/99) + (70/100)*(30/99) = 30*(29+70)/(100*99) = 30*99/(100*99) = 30/100

同理，不管是第几个个体，用数学归纳法可以证明：它被选中的总概率始终是30/100。比如第k个个体，假设前面已经选了t个样本，剩下需要选30-t个，剩余个体数是100-(k-1)，那它被选中的概率是(30-t)/(100-k+1)，把所有可能的t的情况加权求和，最终结果还是30/100。

2. 最终恰好能抽到30个样本 #

每一步的概率都是根据「剩余需要抽取的样本数/剩余总体数」来设置的：

• 当剩余需要抽取的数量等于剩余总体数时，后面的所有个体都会被选中（概率1）
• 比如抽到第71个个体时，如果前面已经选了30个，那后面的都不会被选中；如果前面只选了29个，那第71到100个共30个个体，每个的选中概率都是1/30，最终必然会选1个，凑够30个。

整个流程相当于动态调整抽样概率，确保在无放回的情况下，每个个体的入选机会均等，完全符合简单随机抽样的要求。

内容的提问来源于stack exchange，提问作者PwNzDust