从$ o（1）$空间中随机均匀地满足谓词的集合中选择一个元素

Question

我们得到了一组对象，例如整数，$ s $。此外，我们还为我们提供了一个谓词$ p $，例如$ p（i）： leftrightArrow i geq 0 $。我们不提前知道$ s $的元素满足谓词$ p $，但我们想从$ s'= {i in mid i in s wedge中随机进行采样或均匀选择一个元素p（i）} $。

天真的方法是扫描$ s $，例如记录$ p $所保留的所有整数或索引，然后随机选择其中一个。不利的一面是，在最坏的情况下，我们需要$ | s | $ space。

对于大型集或说流环境，天真的方法是不可接受的。该问题是否存在现场算法？

Answer 1

以下方法通常称为 水库采样. 。开始扫描集合$ s $，并将索引$ j $保持到集合。您遇到的满足谓词的第一个元素将$ J $设置为概率$ 1/1 $。当您遇到概率$ 1/2 $的第二个此类元素时，更新您的选择。当您遇到满足谓词的$ k $ th元素时，将$ j $设置为概率$ 1/k $。

该算法在$ theta（n）$时间和恒定空间中工作。为了正确性，应证明每个项目都有相同的选择概率，并且它们被采样的事件是独立的。独立性的第二个主张显而易见：我们的决定不是基于我们以前是否已经采样项目。通过归纳，可以很容易地证明第一个主张（同等可能性）。

有关详细信息，请参阅 JS Vitter，用储层随机抽样, ，算法R.有关更紧凑的演示，请参见 这些幻灯片.