洗牌抽样等几个概率算法

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

面试题