D

#### A fair coin is tossed 10 times. What is the probability that there are no two tails in succession?

111 viewed last edited 4 months ago Mahesh Godavarti
1

Via @CutTheKnotMath Hint provided by Karthikeyan: think recurrence relation I am providing my brute force method. Not sure it is correct. If somebody has a better solution post it here. Mahesh Godavarti
4

Using Karthikeyan's hint.

I misunderstood the hint as no "n" tails in succession. The hint actually asks us to think about recursion for no two tails in succession in "n" tosses.

Let the number of sequences with no two tails in succession in " n " tosses be f(n) .

Let the number of sequences with no two tails in succession in " n " tosses, ending in a T be g(n) .

Let the number of sequences with no two tails in succession in " n " tosses, ending in an H be h(n) .

Then f(n) = g(n) + h(n) .

Is there a way to find a relationship between f(n+1), g(n+1), h(n+1) and f(n), g(n), h(n) ? Yes!

If the sequence of length "n" ends in a T, then we extend it by appending it with an H.

If the sequence of length "n" ends in an H, then we extended by appending it with both an H and a T.

That means g(n+1) = h(n) + g(n) = f(n) and h(n+1) = g(n) = f(n-1)

That means f(n+1) = g(n+1) + h(n+1) = f(n) + f(n-1) .

We have our recursion and we want to find f(10) .

f(1) = 2 (either "H" or "T")

f(2) = 3 (either "HH", "TH, or "HT")

f(3) = f(2) + f(1) = 5

f(4) = f(3) + f(2) = 8

f(5) = f(4) + f(3) = 13

f(6) = f(5) + f(4) = 21

f(7) = f(6) + f(5) = 34

f(8) = f(7) + f(6) = 55

f(9) = f(8) + f(7) = 89

f(10) = f(9) + f(8) = 144

Therefore, the probability = \frac{144}{1024} . Same as the other answer. 0
Correct. The only thing I'd point out is that this is the Fibonacci sequence (without the two 1s at the beginning). The recurrence relation is the same, and 2, 3 are part of the Fibonacci sequence as well, so this has to be the same sequence. For n=10, number of sequences with no two successive tails is therefore Fib(12) = 144, and the probability is 144/1024 3

I'd state it slightly differently than Mahesh (but equivalently). Pick whichever way appeals to you.

Think of any sequence with m tosses, that does not have two tails. Number of such tosses = N(m)

Now this can begin with a head or a tail.

If it begins with a head, then any sequence of m-1 tosses with no successive tails can be a postfix to the head

If it begins with a tail, then the next toss must be a head, and then any sequenc of m-2 tosses with no successive tails can be a postfix.

Thus we get the recurrence, N(m)=N(m-1)+N(m-2)

(At this point, I get excited, noticing the Fibonacci recurrence, but then I have to check initial conditions)

N(1) = 2 {H,T}

and

N(2) = 3 {HT,TH,HH}

from inspection.

Thus N(1)=Fib(3), and N(2)=Fib(4), and we have the same recurrence. Thus N(m)=Fib(m+2)!

N(10)=Fib(12)=144 You can work out the recurrence :-)

Thus the probability is 144/2^10 = 144/1024 Mahesh Godavarti
1

My solution is kind of brute force and is not easily generalizable to "What is the probability that there are no 'n' tails in succession?"

I am going to count up all possible sequences where tails do not occur in succession.

Let's tackle easy cases first. What we want is if we require a head to occur between two tails. That tells us that for number of tails \geq 6 we don't have enough heads to occur between two tails. Therefore, there are no sequences with number of tails \geq 6 . The easy cases are listed below.

1. Number of tails = 0, Number of sequences = 1
2. Number of tails = 1, Number of sequences = 10
3. Number of tails = 6, Number of sequences = 0
4. Number of tails = 7, Number of sequences = 0
5. Number of tails = 8, Number of sequences = 0
6. Number of tails = 9, Number of sequences = 0
7. Number of tails = 10, Number of sequences = 0

Now, let's tackle the harder cases with easier ones first.

Number of tails = 5. To ensure no tails occur in succession, 4 heads will be required to be inserted between the 5 tails. That leaves us with 1 head with 6 possible places it can be inserted into. Number of sequences = 6

Number of tails = 4. To ensure no tails occur in succession, 3 heads will be required to be inserted between the 4 tails. That leaves us with 3 heads with 5 places they can be inserted into. How do we distribute 3 heads among 5 bins?

1. Choose 1 bin and drop them all into the same bin: Number of sequences = 5
2. Choose 2 bins and distribute 3 heads among two bins: The only distribution for 3 is 1, 2. Number of sequences = ^5C_2 \times 2 = 20
3. Choose 3 bins and distribute 3 heads among three bins: The only distribution for 3 is 1, 1, 1. Number of sequences = ^5C_3 = 10
4. So, total number of sequences with 4 tails = 35

Number of tails = 3. To ensure no tails occur in succession, 2 heads will be required to be inserted between the 3 tails. That leaves us with 5 heads with 4 places they can be inserted into. How do we distributed 5 heads among 4 bins?

1. Choose 1 bin and drop them all into the same bin: Number of sequences = 4
2. Choose 2 bins and distribute 5 heads among two bins. The only distributions possible are 1, 4; 2, 3. Number of sequences = ^4C_2 \times 4 = 24
3. Choose 3 bins and distribute 5 heads among three bins. The only distributions possible are 1, 1, 3; 1, 2, 2; Number of sequence = ^4C_3 \times 6 = 24
4. Choose 4 bins and distribute 5 heads among four bins. The only distributions possible are 1, 1, 1, 2; Number of sequences = 4.
5. So, total number of sequences with 3 tails = 56

Number of tails = 2. To ensure no tails occur in succession, 1 head will be required to be inserted between two tails. That leaves us with 7 heads will 3 places they can be inserted into. How do we distribute 7 heads among 3 bins?

1. Choose 1 bin and drop them all into the same bin: Number of sequences = 3
2. Choose 2 bins and distribute 7 heads among two bins. The only distributions possible are 1, 6; 2, 5; 3, 4. Number of sequences = ^3C_2 \times 6 = 18 .
3. Choose 3 bins and distribute 7 heads among three bins. The only distributions possible are 1, 1, 5; 1, 2, 4; 2, 2, 3; 1, 3, 3; Number of sequences = 3 + 6 + 3 + 3 = 15.
4. Total number of sequences = 36

So, total number of sequences with no two tails in succession = 1 + 10 + 6 + 35 + 56 + 36 = 144.

Probability that there are no two tails in success = \frac{144}{1024}. 1

Another solution due to Nassim Taleb (yes, that guy).

Treat this as a Markov chain with three states - Neutral(N), Need Head (NH), and Lost (TT). We start with Neutral. Everytime we get a head, we stay in N. Everytime we get a T, we go to NH. Everytime we get a T from NH, we go to Lost (TT), and then are stuck there.

The (left) transition matrix for this markov chain will be (in Python format)

M = [[1/2., 1/2., 0], [1/2., 0, 0],[0,1/2.,1]]

Initial state

I = [1, 0 , 0]

The probability of being in the each state after 10 tosses is (M^10).I, which we get by calculation as

[ 0.08691406, 0.05371094, 0.859375 ]

So the probability of not being in the lost state (TT) is 1 - 0.859375 = 0.140625 = 144/1024 Mahesh Godavarti
0
This is pretty cool! I was trying to set it up as Markov chain. But couldn't quite get there.