Reservoir Sampling

Problem:

• Choose <code>k</code> entries from <code>n</code> numbers. Make sure each number is selected with the probability of <code>k/n</code>

Basic idea:

• Choose <code>1, 2, 3, ..., k</code> first and put them into the reservoir.
• For <code>k+1</code>, pick it with a probability of <code>k/(k+1)</code>, and randomly replace a number in the reservoir.
• For <code>k+i</code>, pick it with a probability of <code>k/(k+i)</code>, and randomly replace a number in the reservoir.
• Repeat until <code>k+i</code> reaches <code>n</code>

Proof:

• For <code>k+i</code>, the probability that it is selected and will replace a number in the reservoir is <code>k/(k+i)</code>
• For a number in the reservoir before (let's say <code>X</code>), the probability that it keeps staying in the reservoir is
  • <code>P(X was in the reservoir last time)</code> × <code>P(X is not replaced by k+i)</code>
  • <code>P(X was in the reservoir last time)</code> × (<code>1</code> - <code>P(k+i is selected and replaces X)</code>)
  • = <code>k/(k+i-1)</code> × （<code>1</code> - <code>k/(k+i)</code> × <code>1/k</code>）
  • = <code>k/(k+i)</code>
• When <code>k+i</code> reaches <code>n</code>, the probability of each number staying in the reservoir is <code>k/n</code>

Example

• Choose <code>3</code> numbers from <code>[111, 222, 333, 444]</code>. Make sure each number is selected with a probability of <code>3/4</code>
• First, choose <code>[111, 222, 333]</code> as the initial reservior
• Then choose <code>444</code> with a probability of <code>3/4</code>
• For <code>111</code>, it stays with a probability of
  • <code>P(444 is not selected)</code> + <code>P(444 is selected but it replaces 222 or 333)</code>
  • = <code>1/4</code> + <code>3/4</code>*<code>2/3</code>
  • = <code>3/4</code>
• The same case with <code>222</code> and <code>333</code>
• Now all the numbers have the probability of <code>3/4</code> to be picked