The Author Online Book Forums are Moving

The Author Online Book Forums will soon redirect to Manning's liveBook and liveVideo. All book forum content will migrate to liveBook's discussion forum and all video forum content will migrate to liveVideo. Log in to liveBook or liveVideo with your Manning credentials to join the discussion!

Thank you for your engagement in the AoF over the years! We look forward to offering you a more enhanced forum experience.

rachelb (6) [Avatar] Offline
#1
I hadn't come across reservoir sampling before and it is a really neat algorithm. However, the text does not spell out its key property - namely that however many elements have been consumed from the stream, each element from the stream has the same probability of being included in the sample.

It is easy to devise an algorithm that gives every element consumed from a stream a chance of being in the reservoir - this would be a random sample, but it would not necessarily be a uniform random sample.
andrew.psaltis (33) [Avatar] Offline
#2
rachelb wrote:.... the text does not spell out its key property - namely that however many elements have been consumed from the stream, each element from the stream has the same probability of being included in the sample.


Thank you for catching this and point it out. I have adjusted the text accordingly.