Reservoir sampling
To pick one uniformly random element from a stream of unknown length in memory, with what probability should the th item replace the current pick?
Show hints (2)+
- You don't know in advance, so the rule can only use .
- Show each element ends with probability by telescoping.
Answer
Reveal answer →Final answer
for the th item
Create a free account to see the full worked solution and track your progress.
Interview format: Market Maker, Systematic & Data-Driven Trading