title: reservoir sampling problem
body: <p><a href="http://blogs.msdn.com/spt/archive/2008/02/05/reservoir-sampling.aspx" rel="nofollow noreferrer"><strong>This MSDN article</strong></a> proves the correctness of <a href="http://en.wikipedia.org/wiki/Reservoir_sampling" rel="nofollow noreferrer"><strong>Reservoir Sampling algorithm</strong></a> as follows:</p>
  
  <hr>
  
  <ol>
  <li><p>Base case is trivial. For the k+1st
  case, the probability a given
  element i with position &lt;= k is in R
  is s/k.</p></li>
  <li><p>The probability i is replaced is the probability k+1st element is chosen multiplied by i being chosen to be replaced, which is: s/(k+1) * 1/s = 1/(k+1), and prob that i is not replaced is k/k+1.</p></li>
  <li><p>So any given element's probability of lasting after k+1 rounds is: (chosen in k steps, and not removed in k steps) = s/k * k/(k+1), which is s/(k+1).</p></li>
  <li><p>So, when k+1 = n, any element is present with probability s/n.</p></li>
  </ol>
  
  <hr>
  
  <p>about step 3:</p>
  
  <ul>
  <li><p>What are the <code>k+1 rounds</code> mentioned?</p></li>
  <li><p>What is <code>chosen in k steps, and not removed in k steps</code>?</p></li>
  <li><p>Why are we only calculating this probability for elements that were already in <code>R</code> after the first <code>s</code> steps?</p></li>
  </ul>