概率难题从M个元素的集合中随机抽取不超过N个（可少于N个,但不允许重复),每个元素被抽中的概率不等,用一张表来表现----第i个元素被抽中的概率填写为Pi,用以下方式进行抽取:步骤1：对备

Question

概率难题
从M个元素的集合中随机抽取不超过N个（可少于N个,但不允许重复),每个元素被抽中的概率不等,用一张表来表现----第i个元素被抽中的概率填写为Pi,用以下方式进行抽取:
步骤1：对备选元素（M个）按一定顺序（比如从表头到表尾）分别计算其命中结果——取i=1开始-->对第i个元素按其填表概率Pi进行随机命中判断-->i=i+1-->直到i=M；（这样我们可以随机得到n（0≤n≤M）个元素）
步骤2：若n≤N则结束,否则进入步骤3；
步骤3：将选出来的n个元素作为新的备选集合,进入步骤4；
步骤4：取r为[1,n]上的随机整数,则n个元素中的第r个被命中,将被命中的元素从备选集合中剃除,使n=n-1,进入步骤5；
步骤5：判断n是否等于N,若等则结束,否则返回步骤3；
问:实际上第i个元素被最终抽中的概率是多少?

Answer 1

因为先从M中选n所以第i个元素被首次抽中的概率是n/M
此时分类讨论,若nN,那么第i个元素第二次被抽中的概率为(n-N)/n.
则最终抽中的概率为(n/M)*[(n-N)/n]=(n-N)/M