Calculating Probability of 20 Heads in a Row in 24 Hours

[Pavel]

Hi, how would you go about calculating the probability that on any given day (24 hours) you toss heads say 20 times in a row. That is, let's say you continuously throw a coin, one toss per second. What's the probability that on a specific day there was one run of 20 heads in a row?

I'm thinking I need to use Poisson distribution formula, but then I need the average and the definition of the event. Both are tricky. I can't arbitrarily define events by dividing 86400 by 20, because what if there are 5 heads on the last 5 tosses of one event and 15 heads of the first tosses of the next event? That would constitute as 20 heads in a row, but that would not constitue the success by definition of the event.

Finding the mean seems to be even more challenging. How do I find out how many occurences of 20 heads in a row happen on average? I mean I can find the probability of 20 heads out of whatever number of trials by using the binomial distribution, but that doesn't give me "in a row". If I simply use 2 to the power of 20, then I limit myself to specific 20 tosses only, not any set of 20 out of 86400.

Any suggestions? Thank you in advance.

 

[EnumaElish]

To simplify, let's think of 3 tosses. Possible outcomes are {HHH, HHT, HTH, HTT, THH, THT, TTH, TTT}. The prob. of 2 heads in a row once is 2/8. Your calculation is different only in the number of tosses (and the run length). But at the end of the day it is a simple counting problem.

 

[DaveC426913]

I have come along and observed Enumafish, causing his two superposed states to collapse into one, thus the answer is...

 

[Pavel]

To simplify, let's think of 3 tosses. Possible outcomes are {HHH, HHT, HTH, HTT, THH, THT, TTH, TTT}. The prob. of 2 heads in a row once is 2/8. Your calculation is different only in the number of tosses (and the run length). But at the end of the day it is a simple counting problem.

It's actually 3/8. HHH also qualifies as 2 heads in a row. Also, I'm sure it's a simple counting problem to you, but not to me. I'm aware of the formulas for combination/permutations, but combinatorics was never part of my curriculum. Can you give me a hint please on how to approach counting this in a general form, rather than enumerating all possible outcomes and counting them individually from the list.

Thank you in advance. By the way, this is not a homework question. I just like doing probability problems, it's like Sudoku, you know :)

 

[Simon 6]

I'm going to assume that the probability to be found is that of tossing 20 or more heads in a row within 86,400 tosses.

In that event, we first calculate how many possible 20 toss successions fit into that 86,400. For example if there were a total of 21 tosses, there would be 2 possible 20 toss successions. With 86,400 tosses there would be 86,381 possible 20 toss sucessions.

The probability that anyone of these possible 20 toss successions were not all heads = "1 - (0.5 to the power of 20)". Let's call that "X"

The probability that all of these 20 toss successions were not all heads = "X to the power of 86,381". Let's call that "Y".

Therefore the probability of getting at least one 20 toss succession of heads = "1-Y". Let's call that "Z".

Sorry for the verbal equations. If my approach is correct, you should be able to calculate the answer.

 

[Barmecides]

I'm going to assume that the probability to be found is that of tossing 20 or more heads in a row within 86,400 tosses.

In that event, we first calculate how many possible 20 toss successions fit into that 86,400. For example if there were a total of 21 tosses, there would be 2 possible 20 toss successions. With 86,400 tosses there would be 86,381 possible 20 toss sucessions.

The probability that anyone of these possible 20 toss successions were not all heads = "1 - (0.5 to the power of 20)". Let's call that "X"

The probability that all of these 20 toss successions were not all heads = "X to the power of 86,381". Let's call that "Y".

Therefore the probability of getting at least one 20 toss succession of heads = "1-Y". Let's call that "Z".

Sorry for the verbal equations. If my approach is correct, you should be able to calculate the answer.

I'm not sure this approach is correct. You cannot say that Y = X^86,381 because toss successions are correlated.
If we consider Enuma example and take the particular result HTH then knowing that HT is not 2 heads entails that TH is not two heads. We should introduce some kind of correlation function in your calculation.
I have not thought about Pavel's problem but it looks very interesting ! Maybe the solution should be found by recurence starting from Enuma's proposal of finding 2 H from 3 tosses.

 

[CRGreathouse]

Numerically, I get 4.03537%. That's higher than I would have expected.

 

[matt grime]

Numerically, I get 4.03537%. That's higher than I would have expected.

Which just goes to prove the observation that people don't really 'get' probability - if asked to write down a 'random' string of Hs and Ts, people never put enough long runs of Hs or Ts in it. They make it 'too' random. Just consider splitting the 84000+ trials into batches of 20 tosses, then there 4320 of those alone (1-20,21-40,...). The probability you see a run of 20 in those subsets alone is approx 0.5%.

 

[EnumaElish]

I have come along and observed Enumafish, causing his two superposed states to collapse into one, thus the answer is...

I don't get the point?

 

[EnumaElish]

It's actually 3/8. HHH also qualifies as 2 heads in a row.

I was going with "there was one run of 20 heads in a row." I am not sure that HHH qualifies as ONE run of two heads.

 

[CRGreathouse]

Which just goes to prove the observation that people don't really 'get' probability - if asked to write down a 'random' string of Hs and Ts, people never put enough long runs of Hs or Ts in it. They make it 'too' random. Just consider splitting the 84000+ trials into batches of 20 tosses, then there 4320 of those alone (1-20,21-40,...). The probability you see a run of 20 in those subsets alone is approx 0.5%.

Well, at least I was going in the right direction -- Simon 6's method would have given 7.90775%, which is almost double the true answer. He actually calculated the chance of 20 heads in a sequence of 1,814,000 coin flips where every 21st is tails and the remainder are fair. In these terms your lower bound (0.41114%) is 88,200 flips where every 21st is tails.

 

[Pavel]

I was going with "there was one run of 20 heads in a row." I am not sure that HHH qualifies as ONE run of two heads.

I see where the confusion is, my bad. There's a difference between one run of 20 heads in a row and one run of at least 20 heads in a row. You took it in the former interpretation and I meant the latter one. You know what, I think the at least calculation looks more involved, so let's stick with your interpretation - what's the probability of having exactly one run of exactly 20 heads over a period of 1 day (1 toss per sec).

In that case, I'm not sure I can agree with the "batch" approach as stated by Matt. As I mentioned in my opening post, if i toss 5 heads on the last 5 tosses of one batch and 15 heads on the first 15 tosses of the next batch, your calculation would not take that into a count as "success hit", because the batch itself was not 20 heads in a row, right?? But that scenario would indeed qualify as a successful run of 20 heads in a row.

If the batches are to be considered at all, then I think they should be 1-20; 2-21; 3-22 and so on. Then every batch has a probability of 2 to the power of 20 to be all heads. And there are 86400 - 20 batches. So, the probability of one batch to be all heads is then 1/1048576 * 86,380 = 0.082, which is 8%. Hmm, sounds kinda high, but wouldn't this be a better approach?

CRG, how did you come up with 4%? Do you mind showing. That answer sounds intuitevely better, although I understand that you should never listen to intuition when it comes to stats.


Thanks again!

Pavel.

 

[Pavel]

Hmm, I just realized that by my logic, the probability of tossing one tail out of 10 tosses (for example) would be 0.5 * 10 = 5, which is clearly absurd. I still like my modified batch approach though, but I also realized that these types of batches (1-20; 2-21; 3-22 etc.) require 86,400 / 20 since each batch lasts 20 seconds. So, I now need to find what the probability of having one success hit (p=1/1048576) out of 86,400 / 20 trials is. Should I use the Binomial distribution to do that? If so, exactly 1 run of 20 heads in a row would be:

number of combinations in which the success batch can happen out of 4,320possible batches, multiplied by (1/1048576 - probability of 20 heads in row), multiplied by (1 - 1/1048576) to the power of 4,320 - 1. (can somebody please enlighten me on how you encode formulas in your replies?).

So, I get (4320! / 4319!) * 0.00000095367431640625 * 0.99588954978525571010254410505008 = 0.0041029385138247534443311601007617

Hah! About 0.4% That sounds more intuitive. Would you guys consider this approach valid? Can somebody simulate the problem to empirically validate the result?

Thanks,

Pavel.

 

[CRGreathouse]

CRG, how did you come up with 4%? Do you mind showing. That answer sounds intuitevely better, although I understand that you should never listen to intuition when it comes to stats.

As I said, I just calculated it numerically. Here's the algorithm I used:

v=vector(21);
u=vector(21);
v[1]=1.; \\ the rest of v and all of u are 0s
for(i=1,86400/2,
...for(i=2,21,u=v[i-1]/2);u[21]=u[21]+v[21];u[1]=.5-v[21]/2;
...for(i=2,21,v=u[i-1]/2);v[21]=v[21]+u[21];v[1]=.5-u[21]/2;
);
v[21] \\ return value

v[1] is the number of coin flips with 0 heads at a given step; v[2] is the number of flips with 1 head; v[21] is the number with 20 or more heads. (Every other flip the information is stored in u instead.)

 

[CRGreathouse]

Hah! About 0.4% That sounds more intuitive. Would you guys consider this approach valid? Can somebody simulate the problem to empirically validate the result?

I got about 10 times higher. I just reran it with higher precision, giving 4.03537480673478806967297406431917435570869%. (This still gives me 30-40 guard digits, which is more than I should need in any case.)

 

[Pavel]

As I said, I just calculated it numerically. Here's the algorithm I used:

v=vector(21);
u=vector(21);
v[1]=1.; \\ the rest of v and all of u are 0s
for(i=1,86400/2,
...for(i=2,21,u=v[i-1]/2);u[21]=u[21]+v[21];u[1]=.5-v[21]/2;
...for(i=2,21,v=u[i-1]/2);v[21]=v[21]+u[21];v[1]=.5-u[21]/2;
);
v[21] \\ return value

v[1] is the number of coin flips with 0 heads at a given step; v[2] is the number of flips with 1 head; v[21] is the number with 20 or more heads. (Every other flip the information is stored in u instead.)

I see. I'm sorry, I did understand what you meant by "calculating it numerically". So, I'm wrong again.

Ok, I tried an approximation this time. I found out that I can estimate how many times, on average, I need to flip the coin to get 20 heads in a row: 2^(n+1) - 2. (http://mathforum.org/library/drmath/view/56672.html)

So, on average I need to flip the coin 2,097,150 times then to get 20 in a row. Since I know the average, I'm going to use the Poisson distribution to calculate the probability on any given day (86,400 seconds):

Average number of runs of exactly 20 heads in a row on any given day: 86,400 / 2,097,150 = 0.0412. Then the probability of one of such runs on any given day is 0.0412 * e^-0.0412 = 0.0395, which is very close to the expected value of your numerical calculation of 4.0353748%. Is that right?

However, this was all done through an approximation, used for empirical probabilities. Being a combinatorial problem, there has to be a counting method for this. According to Enuma it's a simple one, but I can't get it, although I'm very intrigued. I've also tried to divide batches according to Matt's suggestion (1-20;21-40 etc), and then account for "shifting" by multiplying by 20, but still couldn't get 4%. Do you guys mind giving a little more hint?

Thanks,

Pavel.

 

[Pavel]

I see. I'm sorry, I did understand what you meant by "calculating it numerically". So, I'm wrong again.

I meant did NOT understand...

 

[CRGreathouse]

Good call on the Poisson distribution, it seems to work well.

So, on average I need to flip the coin 2,097,150 times then to get 20 in a row. Since I know the average, I'm going to use the Poisson distribution to calculate the probability on any given day (86,400 seconds):

Average number of runs of exactly 20 heads in a row on any given day: 86,400 / 2,097,150 = 0.0412. Then the probability of one of such runs on any given day is 0.0412 * e^-0.0412 = 0.0395, which is very close to the expected value of your numerical calculation of 4.0353748%. Is that right?

That gives you the probability of exactly one success*, while mine gives the probability of at least one. The Poisson distribution for at least one is much closer:

1-exp(-86400 / 2097150) = 4.0361636...

which is good to 3 decimal places.

* Badly, since that's probably closer to 2%; the Poisson distribution doesn't realize that once you have 20 in a row, if the next one is heads, you now have two collections of 20 in a row.