title: Efficiently generating discrete random numbers
body: <p>I want to quickly generate discrete random numbers where I have a known CDF. Essentially, the algorithm is:</p>
  
  <ol>
  <li>Construct the CDF vector (an increasing vector starting at 0 and end at 1) <code>cdf</code></li>
  <li>Generate a uniform(0, 1) random number <code>u</code>
  <ul>
  <li>If <code>u &lt; cdf[1]</code> choose 1</li>
  <li>else if <code>u &lt; cdf[2]</code> choose 2</li>
  <li>else if <code>u &lt; cdf[3]</code> choose 3
  *...</li>
  </ul></li>
  </ol>
  
  <p><strong>Example</strong></p>
  
  <p>First generate an cdf:</p>
  
  <pre><code>cdf = cumsum(runif(10000, 0, 0.1))
  cdf = cdf/max(cdf)
  </code></pre>
  
  <p>Next generate <code>N</code> uniform random numbers:</p>
  
  <pre><code>N = 1000
  u = runif(N)
  </code></pre>
  
  <p>Now sample the value:</p>
  
  <pre><code>##With some experimenting this seemed to be very quick
  ##However, with N = 100000 we run out of memory
  ##N = 10^6 would be a reasonable maximum to cope with
  colSums(sapply(u, "&gt;", cdf))
  </code></pre>