隨機抽樣問題表示如下： 要求從N個元素中隨機的抽取k個元素，其中N無法確定。 這種應用的場景一般是數據流的情況下，由于數據只能被讀取一次，而且數據量很大，并不能全部保存，因此數據量N是無法在抽樣開始時確定的；但又要保持隨機性，于是有了這個問題。所以搜索網站有時候會問這樣的問題。 這里的核心問題就是“隨機”，怎么才能是隨機的抽取元素呢？我們設想，買彩票的時候，由于所有彩票的中獎概率都是一樣的，所以我們才是“隨機的”買彩票。那么要使抽取數據也隨機，必須使每一個數據被抽樣出來的概率都一樣。 【解決】 解決方案就是蓄水庫抽樣（reservoid sampling）。主要思想就是保持一個集合（這個集合中的每個數字出現），作為蓄水池，依次遍歷所有數據的時候以一定概率替換這個蓄水池中的數字。 其偽代碼如下： ~~~ Init : a reservoir with the size： k for i= k+1 to N M=random(1, i); if( M < k) SWAP the Mth value and ith value end for ~~~ 解釋一下：程序的開始就是把前k個元素都放到水庫中，然后對之后的第i個元素，以k/i的概率替換掉這個水庫中的某一個元素。 下面來具體證明一下：每個水庫中的元素出現概率都是相等的。 【證明】 （1）初始情況。出現在水庫中的k個元素的出現概率都是一致的，都是1。這個很顯然。 （2）第一步。第一步就是指，處理第k+1個元素的情況。分兩種情況：元素全部都沒有被替換；其中某個元素被第k+1個元素替換掉。 我們先看情況2：第k+1個元素被選中的概率是k/(k+1)（根據公式k/i），所以這個新元素在水庫中出現的概率就一定是k/(k+1)（不管它替換掉哪個元素，反正肯定它是以這個概率出現在水庫中）。下面來看水庫中剩余的元素出現的概率，也就是1-P(這個元素被替換掉的概率)。水庫中任意一個元素被替換掉的概率是：(k/k+1)*(1/k)=1/(k+1)，意即首先要第k+1個元素被選中，然后自己在集合的k個元素中被選中。那它出現的概率就是1-1/(k+1)=k/(k+1)。可以看出來，舊元素和新元素出現的概率是相等的。 情況1：當元素全部都沒有替換掉的時候，每個元素的出現概率肯定是一樣的，這很顯然。但具體是多少呢？就是1-P(第k+1個元素被選中)=1-k/(k+1)=1/(k+1)。 （3）歸納法：重復上面的過程，只要證明第i步到第i+1步，所有元素出現的概率是相等的即可。 看到一個問題：怎樣隨機從N個元素中選擇一個元素，你依次遍歷每個元素，但不知道N多大。 將N個元素用[1、2、...、N]編號。如果在知道N的大小，我們可以從[1、N]中隨機選擇一個數作為選擇對象。 但是現在不知道N的大小，要使每一個元素被取的概率相等（隨機）。這個概念叫蓄水池抽樣。 Solution：以1/i的概率取第i個元素。 證明：數學歸納法。當i=1時：第1個元素以1/1=1的概率被取，符合條件。 設i=k時符合條件，即前k個元素都以1/k的概率被取。 則i=k+1時：對于第k+1個元素，被取概率為1/（k+1），符合條件。 對于前k個元素，每個元素被取的概率=被取并且沒被第k+1個元素替換的概率=（1/k）*(1?1/（k+1）)=1/（k+1）符合條件。 綜上所述：得證。 將問題擴展：給你一個長度為N的鏈表。N很大，但你不知道N有多大。你的任務是從這N個元素中隨機取出k個元素。你只能遍歷這個鏈表一次。你的算法必須保證取出的元素恰好有k個，且它們是完全隨機的（出現概率均等）。 這次與上面唯一的不同是：總共需要取k個元素。仿照即可得出解決方案。 Solution：以1的概率取前k個元素，從i=k+1開始，以k/i的概率取第i個元素，若被取，以均等的概率替換先前被取的k個元素。 證明：同樣數學歸納法。當i=k+1時：第k+1個元素以k/k+1概率被取，前k個元素被取的概率=1 - 被第k+1個元素替換的概率=1?k/(k+1)*1/k=k/(k+1) 符合條件。 設i=p時符合條件，即前p個元素都以k/p的概率被取。 則i=p+1時：對第p+1個元素，被取概率為k/(p+1)符合條件。 對于前p個元素，每個元素被取的概率=被取并且沒有被第p+1個元素替換的概率= k/p*((1?k/(p+1))+k/(p+1)*(1?1/k))=k/p+1同樣符合條件。 綜上所述：得證。 另外還有一種方法：給每個元素隨機生成一個固定區間（如[0,1]）的權重。用一個大小為k的堆來選取權重較大的k個元素。仿照也可解決最開始的取1個的問題。