Monday, September 08, 2014

Flip a coin and get the same results 100 times in a row

This morning, I heard someone say on a podcast that it was possible to flip a coin and get the same result 1000 times - it would just take a while. Then I thought, "if I could flip a coin as fast as random.nextInt(2), how long would it take?"

The full code I wrote in a pastebin. See the results of one continous run, in another pastebin.

The core code is very simple. Keep flipping a coin (random.nextInt(2)) for as long as you get the same result over and over - returning the number of times you got the same result.

private int countContiguousOccurences(final Random random) {
   int count = 1;
   final int first = random.nextInt(2);
   while (random.nextInt(2) == first) {
      count++;
   }
   return count;
}

Next, record how many times you flipped and got the same result in a row. Store this in a map of (key = int, value = long). The key int is how many times you got the same result in a row. The value long is how many times you have flipped the coin and got the same result this many times in a row. So for example, if we flipped and got heads five times in a row, and this was the tenth time we did it, we would be storing (key = 5, value = 10).

private void rememberCountOfContiguousOccurences(final Random random,
      final Map<Integer, Long> counts) {
   Integer count = countContiguousOccurences(random);
   if (counts.containsKey(count)) {
      Long countOccurences = counts.get(count);
      countOccurences++;
      counts.put(count, countOccurences);
   } else {
      counts.put(count, 1l);
      Date currentTime = new Date();
      message(String.format("New count [%3d] at [" //
         + FORMAT_TIMESTAMP.get().format(currentTime)
         + "] after %s.\n", count, reportTime(currentTime.getTime()
         - start)));
   }
}

I control the code with a thread in such a way that we try for ten of the same results in a row, then twenty, thirty, forty etc, incrementing the target by ten each time. Whenever the target is hit, output the results like this:

It took 168 milliseconds to get [20] results in a row.
How often we flipped the same result [   1] times in a row: 154382.
How often we flipped the same result [   2] times in a row: 77054.
How often we flipped the same result [   3] times in a row: 38763.
How often we flipped the same result [   4] times in a row: 19426.
How often we flipped the same result [   5] times in a row: 9608.
How often we flipped the same result [   6] times in a row: 4883.
How often we flipped the same result [   7] times in a row: 2359.
How often we flipped the same result [   8] times in a row: 1202.
How often we flipped the same result [   9] times in a row: 587.
How often we flipped the same result [  10] times in a row: 316.
How often we flipped the same result [  11] times in a row: 150.
How often we flipped the same result [  12] times in a row: 70.
How often we flipped the same result [  13] times in a row: 41.
How often we flipped the same result [  14] times in a row: 22.
How often we flipped the same result [  15] times in a row: 7.
How often we flipped the same result [  16] times in a row: 9.
How often we flipped the same result [  17] times in a row: 1.
How often we flipped the same result [  18] times in a row: 1.
How often we flipped the same result [  20] times in a row: 1.

Note that I report at the end of each run how many times we achieved each count in a row. So in this run we got the same result twice in a row 77054 times, and we got the same result eighteen times in a row just once. In this run, we didn't hit nineteen times in a row at all.

Each time I get a new count, it is reported as it happened. In this way, I can see that I don't always new results in order. See below for a sample of the latest run.

Initial results show that getting 30 of the same result in a row is easy - it happens within a couple of minutes.. but getting to 40 is a jump to hours, and 50: days.

New count [ 30] at [10 Sep 2014, 10:02:55.254 PM] after 22 seconds and 711 milliseconds.
New count [ 29] at [10 Sep 2014, 10:04:20.712 PM] after 1 minutes, 48 seconds and 169 milliseconds.
New count [ 32] at [10 Sep 2014, 10:06:57.301 PM] after 4 minutes, 24 seconds and 758 milliseconds.
New count [ 33] at [10 Sep 2014, 10:08:40.588 PM] after 6 minutes, 8 seconds and 45 milliseconds.
New count [ 31] at [10 Sep 2014, 10:09:11.408 PM] after 6 minutes, 38 seconds and 865 milliseconds.
New count [ 34] at [10 Sep 2014, 10:12:58.718 PM] after 10 minutes, 26 seconds and 175 milliseconds.
New count [ 35] at [10 Sep 2014, 10:18:24.287 PM] after 15 minutes, 51 seconds and 744 milliseconds.
New count [ 37] at [10 Sep 2014, 10:47:36.084 PM] after 45 minutes, 3 seconds and 541 milliseconds.
New count [ 36] at [10 Sep 2014, 11:20:35.756 PM] after 1 hours, 18 minutes, 3 seconds and 213 milliseconds.
New count [ 38] at [11 Sep 2014, 01:30:12.367 AM] after 3 hours, 27 minutes, 39 seconds and 824 milliseconds.
New count [ 40] at [11 Sep 2014, 03:36:59.302 AM] after 5 hours, 34 minutes, 26 seconds and 759 milliseconds.
New count [ 39] at [11 Sep 2014, 04:18:59.431 AM] after 6 hours, 16 minutes, 26 seconds and 888 milliseconds.
New count [ 41] at [12 Sep 2014, 07:38:47.966 PM] after 1 days, 21 hours, 36 minutes, 15 seconds and 423 milliseconds.
New count [ 45] at [13 Sep 2014, 01:09:16.112 AM] after 2 days, 3 hours, 6 minutes, 43 seconds and 569 milliseconds.
New count [ 43] at [14 Sep 2014, 12:25:38.984 PM] after 3 days, 14 hours, 23 minutes, 6 seconds and 441 milliseconds.