# Coin toss

1. Aug 19, 2007

### 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.

2. Aug 19, 2007

### 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.

Last edited: Aug 20, 2007
3. Aug 19, 2007

### DaveC426913

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

4. Aug 19, 2007

### Pavel

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 :)

5. Aug 19, 2007

### 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 any one 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.

6. Aug 20, 2007

### Barmecides

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.

7. Aug 20, 2007

### CRGreathouse

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

8. Aug 20, 2007

### matt grime

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%.

9. Aug 20, 2007

### EnumaElish

I don't get the point?

10. Aug 20, 2007

### EnumaElish

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.

11. Aug 20, 2007

### CRGreathouse

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.

12. Aug 20, 2007

### Pavel

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.

13. Aug 21, 2007

### 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.

14. Aug 21, 2007

### CRGreathouse

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.)

15. Aug 21, 2007

### CRGreathouse

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.)

16. Aug 21, 2007

### Pavel

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.

17. Aug 21, 2007

### Pavel

I meant did NOT understand..........

18. Aug 22, 2007

### CRGreathouse

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

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.

Last edited: Aug 22, 2007