Coin Toss probability question

siva.eas · 2006-11-23 14:34:16

Suppose a coin is tossed ten times. What is the probability that heads occured in atleast two consecutive tosses?

pi man · 2006-11-23 17:47:38

I'll apologize in advance because there has to be a better way. I'm fairly confident it's correct but it will be interesting to see if anyone else gets the same answer.

There are 1024 (2**10) possible outcomes of the 10 flips. The probability of each one of the outcomes are equal. For example, HHHHHHHHHH is just a likely to happen as is HTHTHTHTHT.

Of the 1024 possible outcomes there are:

1 way to get 10 Heads (10 choose 1)
10 ways to get 9 heads (10 choose 2)
45 ways to get 8 heads (10 choose 8)
120 ways to get 7 heads (10 choose 7)
210 ways to get 6 heads
252 ways to get 5 heads
210 ways to get 4 heads
120 ways to get 3 heads
45 ways to get 2 heads
10 ways to get 1 head
1 way to get 0 heads

Now we have to figure out how many of those ways have at least 2 heads in a row. If you get 6 or more heads, at least 2 of them have to be in a row. So thats 386 ways (1+10+45+120+210).

On the other side, there aren't any ways to get 2 heads in a row if you only rolled 0 or 1 heads. Of the 45 ways to roll 2 heads there are 9 ways to get them in a row (1 and 2, 2 and 3, ... 9 and 10). So add that to your 386 ways to wake it 395.

Now it gets tougher for the 3,4 and 5 heads. (Especially since its late and I'm suffering from too much Thanksgiving turkey!)

Let's see if we can figure out how many ways we can get 5 heads and NONE of them are in a row. For the sequences below, the numbers indicate on which flips the heads were tossed.
1, 3, 5, 7, 9
1, 3, 5, 7, 10
1, 3, 5, 8, 10
1, 3, 6, 8, 10
1, 4, 6, 8, 10
2, 4, 6, 8, 10

I think that's all. So 246 of the 252 ways to get 5 heads have 2 or more heads in a row. Add that to 395 for a total of 641.

***
4 heads... gotta be an easier way but here goes. Consider the 9 cases where only 2 heads were tossed and they were in a row (1 and 2, 2 and 3, etc.). For each of those 9 cases, you can add 2 more heads in any of the 8 other tosses. That's (8 choose 2) or 28 ways. 28 * 9 = 252. But that includes a lot of duplicates. Anytime 4 heads were tossed in a row, they were counted 3 times. For example, 1234 would be counted under 12, 23, and 34. There are 7 ways to get 4 in a row (1234, 2345, ... 78910) and each of those was counted 2 times too many. Subtract 14 from the 252 to get 238.

There are 42 ways to get exactly 3 in a row (1235, 1236, 1237, 1238, 1239, 123A, 2346, 2347, 2348, 2349, 234A, 1345, 3457, 3458, 3459, 345A, 1456, 2456, 4568, 4569, 456A, 1567, 2567, 3567, 5679, 567A, 1678, 2678, 3678, 4678, 678A, 1789, 2789, 3789, 4789, 5789, 189A, 289A, 389A, 489A, 589A, 689A - where A indicates the 10th roll). Each of those ways was counted twice (1235 was counted under 12 and 23). Subtract 42 from 238 to get 196.

Lastly there are the cases where you have 2 heads in a row being rolled twice without getting 3 or 4 in the row. For example 1256. There's 21 cases of these being counted twice (1245, 1256, 1267, 1278, 1289, 129A, 2356, 2367, 2378, 2389, 239A, 3467, 3478, 3489, 349A, 4578, 4589, 459A, 5689, 569A, 679A). Subtract 21 from 192 for a final total 175 ways to get 2 or more heads in a row if 4 heads were rolled. Previous total was 641 so it's now 816.
***
3 heads...
We have to count the number of ways to get 2 or 3 heads in a row if 3 heads were flipped. I brute forced it and counted 64 ways. So the final count is 816+64= 880. So 880 of the 1024 possibilities will have 2 or more heads in a row. That's around 86%.

mathsyperson · 2006-11-24 00:02:26

Haha, wow. That's a lot of working for such a seemingly simple question. On closer inspection though, I can't really see any ways of working out the answer nicely without just brute-forcing it.

So that's what I did. I made Excel look through all 1024 combinations, and it says that 880 of them have 2 consecutive heads. So well done. All that complicated working out, and not a single mistake.

Ricky · 2006-11-24 02:17:36

How about this?

Consider a binary string of length 10, 1 representing heads, 0 representing tails.

Starting at the front, imagine we require the first two flips to be heads:

1 1 _ _ _ _ _ _ _ _

All other flips can be whatever they want. This is a binary string of length 8, and thus, 256 possible combinations.

Now move one digit to the left, and force all previous digits to be 0:

0 1 1 _ _ _ _ _ _ _

This ensures that we are in fact not getting repeats. This is a binary string of length 7, thus, 128. Now just repeat:

256 + 128 + 64 + 32 + 16 + 8 + 4 + 2 + 1 = 511

So I must be missing some combinations. The question is, which?

gnitsuk · 2006-11-24 02:44:45

The problem lies in the following.

On this first iteration you have 11--------

So you can use any 8 digit binary number after the two 1's. This indeed gives 256 possibilities.

Then we move to 011------- giving us a further 128 possibilities.

But we cannot extrapolate out resoning as next we would have:

0011------ giving us a further 64 possibilities BUT we have missed out the number
1011------

And so on. Here is where the missing possibilities lie.

Last edited by gnitsuk (2006-11-24 02:47:20)

pi man · 2006-11-25 17:54:25

It's amazing how these things get under your skin...

I probably shouldn't be surprised but it's a Fibonacci-based series!

# flips # Possible # with 2 heads # without 2 heads
(n) Outcomes in a row (Xn) in a row
_______________________________________________________________
1 2 0 2
2 4 1 2*X1+1 3
3 8 3 2*X2+1 5
4 16 8 2*X3+2 8
5 32 19 2*X4+3 13
6 64 43 2*X5+5 21
7 128 94 2*X6+8 34
8 256 201 2*X7+13 55
9 512 423 2*X8+21 89
10 1024 880 2*X9+34 144

So for 11 tosses it should be 2*880 + (21+34) = 1815 (or 2048-233)

And for 12 tosses it should be 2*1815 + (34+55) = 3719 (or 4096-377)

mathsyperson · 2006-11-25 23:28:16

Wow, maths is incredible. I'd have never expected Fibonacci to pop up in this. Of course now the question is, can we prove that this always works?

krassi_holmz · 2006-11-26 03:14:29

Many combinatorial problems yeld to fibonacci numbers.
It's good start to use some reuirrent relation.
Let
Q(n) be the total number of all combinations when a coin is tossed n times,
and
G(n) - the number of combinations in which there are at least 2 consecutive tosses.A combination of this kind we'll call correct.
Q(n) = 2^n (that's easy, because every combination of tosses can be represented as binary string :1 for heads ).
Now notice
G(1)=1;
G(2)=1;

Let compute G(n+1) , n>=2:
1.
If the first is 0, then we'll get
0xxxx... <--n x's
So this will be a correct combination, iff xxxx... is a correct combination.
So we have that the number of correct combinations of n+1 coins, when the first is null, is
G(n).
2. If the first number is 1, we get 2 cases:
2.1. If the second number is one, then we have:
11xxxx... <--n-1 x's,
which is always correct, so for every combination xxx...
In this case we have Q(n-1) correct combinations.
2.2. If the second number is 0:
10xxxxx <-- n-1 x's
As in point 1, this will be correct, iff xxx... is correct, so in this case we have G(n-1) correct cases.

And now:

For example
110
011
111
G(3)=G(2)+G(1)+2^1=0+1+2=3.
1011
1100
1110
1101
1111
0110
0111
0011
G(4)=G(3)+G(2)+2^2=1+3+4=8;
I hope I've lighted a little bit this problem.

Last edited by krassi_holmz (2006-11-26 03:18:31)

krassi_holmz · 2006-11-26 03:24:42

And, using induction, we will easily prove the interesting fact:

which is according to the pi man's observation.
I'm beginning to think that it will be easier to count combinations without 2 heads than these with two heads.
Once again - combinatorics are COOL!

Ricky · 2006-11-26 03:30:57

Ah, I got it. I did in fact know that this was Fibonacci from the get go. Believe it or not, I actually solved this problem only a few months back, but I had forgotten how I did it.

Ok, so we need a new way of counting. Counting the number of combinations where there are two sequential heads is hard. Counting the number where they aren't is easy. So what we do is:

2^n - # combinations where there aren't two sequential heads = # combinations where there are sequential heads.

Let s_n = # combinations where there aren't two sequential heads in n flips

The base cases are 1 and 2, which are 2 and 3 respectively.

Now we wish to add on a coin flip. We need to find out how many of our flips in s_n-1 end in tails. But remember that s_n-1 was generated by adding a flip to s_n-2. So if we take all of our flips in s_n-2, append a tails to each one of these, this will be all the combinations in s_n-1 which end in tails. This is exactly s_n-2. Now that we have something that ends in tails, we may either append a tails or a head to it and still have a valid combination. This is 2 * s_n-2.

Half way there. Now we need to find the number of combinations in s_n-1 which end in a heads. We already have the number which end in tails (s_n-2), so all we do is take all the combinations in s_n-1, and subtract off the ones that end in tails. This is s_n-1 - s_n-2. We may only append a tails to this, because if we appended a heads, it would be an invalid combination. This is (for clarity) 1 * (s_n-1 - s_n-2).

Now we just add the two together:

2*(s_n-2) + (s_n-1 - s_n-2) = s_n-1 + s_n-2.

And you're done.

krassiholmz · 2006-11-27 00:11:18

It will be interesting to generalise the problem.
We can think of some interesting generalisations.

Math Is Fun Forum

#1 2006-11-23 14:34:16

Coin Toss probability question

#2 2006-11-23 17:47:38

Re: Coin Toss probability question

#3 2006-11-24 00:02:26

Re: Coin Toss probability question

#4 2006-11-24 02:17:36

Re: Coin Toss probability question

#5 2006-11-24 02:44:45

Re: Coin Toss probability question

#6 2006-11-25 17:54:25

Re: Coin Toss probability question

#7 2006-11-25 23:28:16

Re: Coin Toss probability question

#8 2006-11-26 03:14:29

Re: Coin Toss probability question

#9 2006-11-26 03:24:42

Re: Coin Toss probability question

#10 2006-11-26 03:30:57

Re: Coin Toss probability question

#11 2006-11-27 00:11:18

Re: Coin Toss probability question

Board footer