title: Proof of stream reservoir sampling
body: <p>I'm quite familiar with Reservoir Sampling algorithm and I'm thinking what if the total size <code>N</code> is given. What benefit can we get under this situation? As a result, here's the algorithm:</p>
  
  <pre><code>Let n be the total size of data
  Let k be the total size of sample
  for each element from data
      if random(0,1) &lt;= k/n
          put this element into sample
          -- k
      -- n
  done
  </code></pre>
  
  <p>It looks correct at the first glance but I found it hard to prove. Anybody can help me to prove this algorithm in a formal way?</p>