【转】蓄水池抽样

蓄水池抽样

  

1 排列公式A(n, m)&＃xff1a;
2 A(n, m) &＃61; n*(n-1)*(n-2)*...*(n-(m-1)) &＃61; n! / (n-m)!
3 注意0!&＃61;1(n!表示n(n-1)(n-2)...1,也就是6&＃xff01;&＃61;6x5x4x3x2x1
4
5 组合公式C(n, m)&＃xff1a;
6 C(n, m) &＃61; A(n, m) / A(m, m) &＃61; (n! / (n-m)!) / (m! / 0!) &＃61; n!/((n-m)! * m!)

 

　　对应蓄水池抽样问题&＃xff0c;可以类似的思路解决。

　　先把读到的前k个对象放入“水库”&＃xff0c;对于第k&＃43;1个对象开始&＃xff0c;以k/(k&＃43;1)的概率选择该对象&＃xff0c;以k/(k&＃43;2)的概率选择第k&＃43;2个对象&＃xff0c;以此类推&＃xff0c;以k/m【即c(m-1, k-1) / c(m, k)】的概率选择第m个对象&＃xff08;m>k&＃xff09;。如果m被选中&＃xff0c;则随机替换水库中的一个对象。最终每个对象被选中的概率均为k/n&＃xff0c;证明如下。

       证明&＃xff1a;第m个对象被选中的概率&＃61;选择m的概率*&＃xff08;其后元素不被选择的概率&＃43;其后元素被选择的概率*不替换第m个对象的概率&＃xff09;&＃xff0c;即