异想天开

What's the true meaning of light, Could you tell me why

等概率地从n个数选出m个数

日期:2016-02-18 13:36:14
  
最后更新日期:2016-04-24 11:30:06
这题根本扯犊子

我们所学的组合数,从n个数选m个数,对于每一个数是不是等概率的?答案是肯定的。
从n个数选1个数,搞一个随机数,然后取模,自然选的每个数都是等概率的1/n。
等概率的意义在于我们没有针对任何一个数特殊对待。
比如第一次随机取一个数,第二次随机取一个数,第m次随机取一个数。整个空间上看,每个数被抽中的概率都是这些事件的和。
对任意一个数:
第一次抽中概率1/n
第二次抽中概率(n-1)/n*(n-1)=1/n
。。。
第m次抽中概率也是1/n
那么一个数整体被抽中概率为m/n。


放大一点,对于n个数任意m个数,每个组合出现概率可以这样认为:
抽第一个数被抽中的概率为m/n
抽第二个被抽中概率为(m-1)/(n-1)
抽第m个数被抽中概率为1/(n-m+1)
这个样本的被抽中的概率之积即为组合数的倒数。