Reservior Sampling

Reservior Sampling

1.Idea

蓄水池算法是一种Randomized Algorithm， 对于n个数(n 可以为无限大)，它能保证每个数都以相等的概率被选到。它的基本思想是，维护一个size为k (k < n)的蓄水池，依次遍历所有数据的时候以相等的概率替换这个蓄水池中的数字

2. Implementation

public static List<Integer> reserviorSampling(int[] nums, int k) {
        List<Integer> res = new ArrayList<>();

        if (nums.length <= k) {
            return res;
        }

        for (int i = 0; i < k; i++) {
            res.add(nums[i]);
        }

        Random rand = new Random();

        for (int i = k + 1; i < nums.length; i++) {
            int j = rand.nextInt(i);

            // If we use j == k here, that means we want an item to be selected with probability 1/i
            if (j < k) {
                res.set(j, nums[i]);
            }
        }
        return res;
    }

3. Proof (Mathematical Induction)

证明： 对于n(n > k)个数，每个数被选到的概率是 k/n

1. 假设当 i=k 的时候结论成立，此时以 k/i 的概率来选择第i个元素，前i-1个元素出现在蓄水池的概率都为k/i。

2. 当i = k+1时，蓄水池的容量为k，第k+1个元素被选择的概率明显为k/(k+1)

3. 当i = k +1时, 需要证明当以 k/i+1 的概率来选择第i+1个元素的时候，此时任一前i个元素出现在蓄水池的概率都为k/(i+1).

   前i个元素出现在蓄水池的概率有2部分组成:

   ①在第i+1次选择前得出现在蓄水池中

   ②得保证第i+1次选择的时候不被替换掉

   由1知道在第i+1次选择前，任一前i个元素出现在蓄水池的概率都为k/i

4. 对于前i个数被替换的概率：

   首先要被替换得第 i+1 个元素被选中 (不然不用替换了)概率为 k/i+1

   其次是因为随机替换的池子中k个元素中任意一个，所以不幸被替换的概率是 1/k，故

5. 前i个元素(池中元素)中任一被替换的概率 = k/(i+1) * 1/k = 1/i+1, 则(池中元素中)没有被替换的概率为: 1 - 1/(i+1) = i/i+1

   得到前i个元素出现在蓄水池的概率为 k/i * i/(i+1) = k/i+1

4. Time & Space Complexity

Time: O(n)

Space: O(1)