title: Random.nextInt(int) is [slightly] biased
body: <p>Namely, it will never generate more than 16 even numbers in a row with some specific <code>upperBound</code> parameters:</p>
  
  <pre><code>Random random = new Random();
  
  int c = 0;
  int max = 17;
  int upperBound = 18;
  
  while (c &lt;= max) {
      int nextInt = random.nextInt(upperBound);
      boolean even = nextInt % 2 == 0;
      if (even) {
          c++;
      } else {
          c = 0;
      }
  }
  </code></pre>
  
  <p>In this example the code will loop forever, while when <code>upperBound</code> is, for example, 16, it terminates quickly. </p>
  
  <p>What can be the reason of this behavior? There are some notes in the method's javadoc, but I failed to understand them. </p>
  
  <hr>
  
  <p><strong>UPD1</strong>: The code seems to terminate with odd upper bounds, but may stuck with even ones</p>
  
  <hr>
  
  <p><strong>UPD2</strong>:
  I modified the code to capture the statistics of <code>c</code> as suggested in the comments: </p>
  
  <pre><code>Random random = new Random();
  
  int c = 0;
  long trials = 1 &lt;&lt; 58;
  int max = 20;
  int[] stat = new int[max + 1];
  
  while (trials &gt; 0) {
      while (c &lt;= max &amp;&amp; trials &gt; 0) {
          int nextInt = random.nextInt(18);
          boolean even = nextInt % 2 == 0;
          if (even) {
              c++;
          } else {
              stat[c] = stat[c] + 1;
              c = 0;
          }
          trials--;
      }
  }
  
  System.out.println(Arrays.toString(stat));
  </code></pre>
  
  <p>Now it tries to reach <code>20</code> evens in the row - to get better statistics, and the <code>upperBound</code> is still <code>18</code>.</p>
  
  <p>The results turned out to be more than surprising: </p>
  
  <pre><code>[16776448, 8386560, 4195328, 2104576, 1044736, 
   518144, 264704, 132096, 68864, 29952, 15104, 
   12032, 1792, 3072, 256, 512, 0, 256, 0, 0]
  </code></pre>
  
  <p>At first it decreases as expected by the factor of 2, but note the last line! Here it goes crazy and the captured statistics seem to be completely weird.</p>
  
  <p>Here is a bar plot in log scale:</p>
  
  <p><img src="https://i.stack.imgur.com/vELdJ.png" alt="c statistics"></p>
  
  <p>How <code>c</code> gets the value <code>17</code> 256 times is yet another mystery</p>