如何證明採樣算法？

Question

這是一個家庭作業問題。爲了打印範圍[0，N）中的M個排序的不同隨機整數，我們可以使用以下算法：

 
int n = N 
int m = M 
for i in [0,N) 
    if (bigrandom() % n--) < m) 
     print i 
     m-- 

如我們所知，該算法以相等的概率選取範圍內的所有整數。你能幫我證明嗎？

Answer 1

1. 選擇任何特定號碼的機會是m/n。
2. 如果選擇此號碼，我們有同樣的問題，但n' = n - 1和m' = m - 1。如果不是，我們有同樣的問題，但n' = n - 1和m' = m。

你的算法是這個想法的實現。

你還需要證明假設1，但你可以自己做。