放回采樣最終不同樣本數量

作者：無影隨想 
時間：2016年1月。 
出處：http://www.zhaokv.com/2016/01/sample-with-replacement-unique-number.html
聲明：版權所有，轉載請聯繫作者並註明出處

機器學習很多場景中會用到放回采樣，比如bagging方法。採樣後的數據集會有一些數據重覆，一些數據缺失，從$N$個樣本中採樣$K$個樣本，不同樣本數量的期望為$U(K)=N(1-\left(\frac{N-1}{N}\right)^K)$。怎麼來的呢？這裡給出簡單的證明。

首先，顯然有$U(1)=1$；其次，設從$N$個樣本中採樣$k-1$個樣本，不同樣本數量的期望為$U(k-1)$，則第$k$個樣本是未曾抽到的樣本的概率為$1-\frac{U(k-1)}{N}$，所以$U(k)=1+\frac{N-1}{N}U(k-1)$$=1+\frac{N-1}{N}+\left(\frac{N-1}{N}\right)^2+\cdots+\left(\frac{N-1}{N}\right)^{k-1}$，根據等比數列求和公式得$U(K)=N(1-\left(\frac{N-1}{N}\right)^K)$。

對於一種特殊情況，當$K=N$且$N$足夠大時，則有最終不同樣本數量是原始樣本數量的期望為$(1-\frac{1}{e})$，大約是$\frac{2}{3}$。

可以通過一段Python程式來驗證結論的正確性：

1 import random, math
2  
3 S = set()
4 N = 10000000
5 [S.add(random.randint(1,N)) for i in range(N)]
6 print(len(S), int(N*(1-1/math.e)))

我得到的輸出結果為

1 (6321214, 6321205)

當然，你的運行結果可能和上面有所差別。