Sampling From a Stream of an Indefinite Length

Post author: Li-Pin Juan (阮立斌)
Post link: <a href="https://libinruan.gitlab.io/2020/06/05/Sampling-From-a-Stream-of-an-Indefinite-Length/" title="Sampling From a Stream of an Indefinite Length">https://libinruan.gitlab.io/2020/06/05/Sampling-From-a-Stream-of-an-Indefinite-Length/
Copyright Notice: All articles in this blog are licensed under <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/" rel="noopener" target="_blank"> BY-NC-SA unless stating additionally.

Posted on 2020-06-05 Edited on 2021-06-14 Views: Disqus:

How do we ensure that the probability of an item in a stream being selected is no different than those of the others? Reservoir Sampling is the algorithm that comes to our rescue. In this post I lazily showed why Reservoir Sampling works.