洗牌抽样等几个概率算法

2012-11-05

洗牌,把一个数组中的数据尽量地打乱,保证是随机的,数组大小n已知

做法:循环一遍,当前到第 i 个,则从 i 到 n 中随机挑一个与 i 位置的元素交换

这个证明每一个元素,落到每个格子中的概率都是 1/n.

先分析第一个格子,很显然每个元素最终在此格子的概率都是1/n.(包括格子本身的元素留在原地的概率也是1/n).

再分析第二个格子,两种情况,第一个元素最终在第二个格子的情况,只能是第一个元素被换到后面 (1-1/n),且又换回到第二个格子 1/(n-1).这样其概率是 (1-1/n)*(1/(n-1))=1/n .而对第二个以后的元素最终在第二个格子的情况,只能是没被换到第一个格子,并且换到第二个格子.这个概率依然是 (1-1/n)*(1/(n-1))=1/n

再分析第三个格子,也是两种情况,一种情况是前面第一或第二个元素最终放在第三个格子,另一种情况是后面的元素最终放在这个格子.前一种,只能是第一二个元素先换到后面再换回来,概率类似的是 (1-1/n-1/n)*(1/(n-2))=1/n.对于第三个以后的元素最终放到第三个格子的情况,需要它们没被换到前面第一第二格子,对应概率也是 (1-1/n-1/n)*(1-1/(n-2))=1/n

依此类推,后面也是类似的情况,最终能保证每个元素到每个格子的概率都是同样的1/n

抽样,n个数组中随机抽出k个样本来

n是已知的情况.每个元素留下的概率都应该是k/n.但如何直接扫描一遍让每个以k/n的概率留下,这样做只是留下的元素个数期望是k,但不一定能保证正好是k个.

做法是这样的.设已经选取的个数是 k1,已经扫描过的个数是 n1,每经过一个时选择的概率是 (k-k1)/(n-n1)

下面是这个算法正确性.其实这个就跟买彩票一个道理,n张彩票中有k张是有奖的,然后到每次抽的时候的概率是 (彩票总个数-已开出的彩票数)/(总数-已经过的彩票数). 对第一个显然它被选为样本的概率是k/n的.对第二个,如果第一个没被选取,则概率是 (1-k/n)*(k-1)/(n-1),如果第一个被选取,则概率是 (k/n)*(k-1)/(n-1),加起来就是k/n.对第三个,就分前面一个没选取,前面选取一个,前面选取二个进行计算,反正跟彩票一样不管第几个抽,概率均是相等的.

抽样,从数据流中抽取k个样本来,数据流很大,远大于k,但大小n不给出

跟上面不同的是这个n未知.这种情况下方法是,将前k个数据都留下,然后后面到的每个,都按一定的概率替换留下数据中的某个.

这个替换的概率应该是 1/i,i表示遍历到第i个.如果数据流到i结束,要证明每个最终留下的概率都是 k/i,用归纳法证明.

对 i=k+1 的时候,第 i 个会按 1/k+1 的概率替换前面的k个中的某个,这样每个元素最终留下的概率都是 k/k+1,正确的

假设在数据流大小为 i-1 的时候这种算法是正确,即前面每个留下的概率都为 k/i-1,则当数据流大小为 i,即第 i 个到达时,它会以 1/i 的概率替换掉前k个中的某个

它留下的概率是 k/i 正确,而它前面的留下的情况是它们前面被选中,且没被第i个替换.这个概率是 (k/(i-1))*(1-1/i)=k/i