2.假设当 j=i 的时候结论成立,此时以 k/i 的概率来选择第i个元素,前i-1个元素出现在蓄水池的概率都为k/i。 证明当j=i+1的情况: 即需要证明当以 k/i+1 的概率来选择第i+1个元素的时候,此时任一前i个元素出现在蓄水池的概率都为k/(i+1). 前i个元素出现在蓄水池的概率有2部分组成, ①在第i+...
终于要讲到蓄水池采样算法(Reservoir Sampling)了。先说一下算法的过程: 假设数据序列的规模为 \(n\),需要采样的数量的为 \(k\)。 首先构建一个可容纳 \(k\) 个元素的数组,将序列的前 \(k\) 然后从第 \(k+1\) 个元素开始,以 \(\frac{k}{n}\) 证明过程 对于第 \(i\) 个数(\(i \le k\...