algorithm - 如何证明采样算法？

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，但您可能可以自己做。