My derivation above is wrong; according to my working, the probability p of getting n heads in a row in t tosses is given by:
Code:
p = ( 2^(t-n) * (t-n+1) ) / ( 2^t )
It's the 2^(t-n) on the top that's important.
That gives a probability, p, of
7.89 * 10^-9. 1,000,000,000 coin flips in a single threaded Java program (see below) takes 23 seconds.
For a probability of 0.1 (i.e. a 10% chance of getting 100 heads in a row), we need to do
1.267*10^29 flips. That will take my Java program around 2.92 * 10^21 seconds, or about 10^14 years -- i.e. 100,000 billion years. That's a lot, but it's nowhere near the heat death of the universe time frame (which is about 10^100 years). I could speed it up by throwing more hardware at it -- one of our big multicore DB servers has about 100x to 150x as much grunt as this laptop, for example. But obviously that only brings it down to 10^12 years or so.
However, the numbers for smaller numbers of heads are more tractable than you might think, because of the (2^(n-t)) factor in the numerator. To get 20 heads, for example, took the following numbers of flips on a few successive runs:
1037833, 3561129, 3362374, 6192144, 3523847
None of these took longer than a second.
Trying to get 40 heads, I managed instead (in successive runs of a billion flips) a max count of 29 heads, 28 heads, 30 heads.
Here's the Java:
ZOMG Spoiler! Click here to view!
Code:
package foo;
import java.util.Date;
import java.util.Random;
public class CoinToss {
private Random rng;
private long maxCount;
public CoinToss(long maxCount) {
rng = new Random();
this.maxCount = maxCount;
}
public void go(int numberOfHeadsToGet) {
long startTime = new Date().getTime();
long count=0;
int headsInARow=0;
int maxHeadsInARow=0;
while (headsInARow < numberOfHeadsToGet && count<maxCount) {
if (rng.nextInt(2) == 1) {
headsInARow++;
} else {
if (headsInARow > maxHeadsInARow)
maxHeadsInARow = headsInARow;
headsInARow=0;
}
count++;
}
long endTime = new Date().getTime();
System.out.println("I ran for "+((endTime-startTime)/1000)+" seconds");
System.out.println("I did "+count+" flips");
if (headsInARow == numberOfHeadsToGet)
System.out.println("**MISSION ACCOMPLISHED**");
else
System.out.println("I had "+maxHeadsInARow+" heads in a row");
}
/**
* @param args
*/
public static void main(String[] args) {
CoinToss ct = new CoinToss(1000000000);
ct.go(10);
}
}
Register
Calendar
FAQ
Search
