Coin Flipping

If you flip a fair coin $8$ times, what is the probability that the only consecutive tail flips $T$ are flips $7$ and $8$ ?

A misunderstanding of a recent daily problem had me trying to figure our a general formula for $n$ flips, but as I started to look for that pattern, a clear approach escaped me.

$\overbrace{ \Box \; \Box \; \Box \; \Box \; \Box \; H \; T \; T }^{\text{8 flips} }$

The sequence of flips would have to end in $HTT$ regardless of the sequence length.

So as far as I can tell, I need to figure out the number of ways to fill the remaining $\Box$ 's with $T$ 's and $H$ 's such that no $T$ 's are adjacent.

I ended up doing this by hand up to 7 flips, finding 8 sequences.

My attempt was to eliminate from all $2^5$ possible adjoining strings those with adjacent $T$ 's.

Start with $2 T$ 's in the adjoining sequence ( ever single $T$ sequence passes the filter ).

there are ${5 \choose 2}$ adjoining $2 T$ sequences

Trying to remove the grouped $2 T$ 's I imagine the following:

$\Box \; \Box \; \Box \; T_2$

We can only fill the boxes with $H$ so we only have 4 possible strings with them grouped.

Thus there are ${5 \choose 2} - 4 = 6$ , $2 T$ sequences that pass the filter.

However, my methods seems to get confusing pretty quickly as the length of the sequence grows and we add $T$ 's to the sequence.

With $3 T$ 's , I have to not only worry about $T_3$ groupings, but also the sub groupings of $2 T$ 's. Overlaps seem to be everywhere in my started method of counting...and its all rather messy.

While I might be able to keep going for a bit , this continuation seems certainly seems like a failure for generalizing. That most likely is a result of my own limitations, but I'm still interested!

Any help leading me to water on this will be appreciated!

Markdown

Appears as

*italics* or _italics_

italics

**bold** or __bold__

bold


- bulleted
- list

bulleted
list


1. numbered
2. list

numbered
list

Note: you must add a full line of space before and after lists for them to show up correctly

paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)

example link

> This is a quote

This is a quote

    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"

# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"

Math

Appears as

Remember to wrap math in $ ... $ or \[ ... \] to ensure proper formatting.

2 \times 3

2 \times 3

2^{34}

2^{34}

a_{i-1}

a_{i-1}

\frac{2}{3}

\frac{2}{3}

\sqrt{2}

\sqrt{2}

\sum_{i=1}^3

\sum_{i=1}^3

\sin \theta

\sin \theta

\boxed{123}

\boxed{123}

from itertools import combinations_with_replacement as combs from itertools import permutations as perms # n is the number of flips and can be changed # be warned that after n = 10, the program takes over a minute to complete :) n = 8 # maybe there's an easier way to generate all 256 inital flips, but I don't know it :) coin_flip_combs = [c for c in combs('HT', n)] all_coin_flips = set() for c in coin_flip_combs: for perm in [p for p in perms(c)]: all_coin_flips.add(perm) valid_flips = [] for flip in all_coin_flips: valid = True # consecutive T's not in place 7 and 8 are not valid for i, coin in enumerate(flip[:-2]): if coin == 'T' and flip[i + 1] == 'T': valid = False # place 7 and 8 (6 and 7 starting from 0) must both be T's if flip[n-2] != 'T' or flip[n-1] != 'T': valid = False # only add valid flips to the final list if valid: valid_flips.append(flip) valid_flips.sort() print('Valid flips:\n') for flip in valid_flips: print(flip) print(f'\nIn total, {len(valid_flips)} flips')

Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 2	paragraph 1 paragraph 2
`[example link](https://brilliant.org)`	example link
`> This is a quote`	This is a quote
# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"	# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"

Math	Appears as
Remember to wrap math in `$` ... `$` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$

Comments

Perhaps approaching this problem from the opposite direction will be easier. Instead of counting how many adjoining strings won't work, we'll count how many do work. Here's how:

We have 4 options for how many $T$ s we can put in this adjoining string without creating any pairs: $0$ $T$ s, $1$ $T$ , $2$ $T$ s, and $3$ $T$ s. Any more, and we won't be able to keep them separated (since we only have $5$ spots to work with).

There's $\boldsymbol{1}$ way to use $0$ $T$ s: $HHHHH$

There's $\boldsymbol{5}$ ways to use $1$ $T$ : $\boldsymbol{T}HHHH$ , $H\boldsymbol{T}HHH$ , $HH\boldsymbol{T}HH$ , $HHH\boldsymbol{T}H$ , and $HHHH\boldsymbol{T}$ .

There's $\boldsymbol{6}$ ways to use $2$ $T$ s: $\boldsymbol{T}H\boldsymbol{T}HH$ , $\boldsymbol{T}HH\boldsymbol{T}H$ , $\boldsymbol{T}HHH\boldsymbol{T}$ , $H\boldsymbol{T}H\boldsymbol{T}H$ , $H\boldsymbol{T}HH\boldsymbol{T}$ , and $HH\boldsymbol{T}H\boldsymbol{T}$ .

(You can manual check this by placing one $T$ in each spot and counting how many places you can put the other $T$ in. Then, divide by $2$ , technically $2!$ , since the two $T$ s are not considered distinct, and we'll have counted duplicates)

And there's $\boldsymbol{1}$ way to use $3$ $T$ s: $\boldsymbol{T}H\boldsymbol{T}H\boldsymbol{T}$ .

So in total, we have $\boldsymbol{13}$ ways to fill in this adjoining string. Since we're interested in the probability of rolling one of these sequences, our final answer is $\boxed{\frac{13}{256}}$ .

I must confess that I was off by $3$ until I checked myself with some code. :) I'll post it in a reply to this comment.

Hope this made sense!

David Stiff - 1 month, 3 weeks ago

Thank you for all this David! I did end up verifying 13 as well with my method. I saw on here someone posted about the Fibonacci numbers, but the comment is now removed.. So far...that holds. Can you verify 9 flips with your program is 21? If it is the Fibonacci numbers then I guess a closed form generalization for $n$ flips is out of the question... Its still seems pretty out there that this question leads to them, and that I stumbled upon it.

Eric Roberts - 1 month, 3 weeks ago

@Eric Roberts – Yes, I can verify $9$ flips results in $21$ valid sequences. I tried $10$ and $11$ as well, and they yielded $34$ and $55$ , so it does indeed seem that the Fibonacci numbers have once again popped up! :)

@David Stiff – 👌 Thank You David!

@Eric Roberts – It's not too hard to see, actually. Taking out the HTT tail, you're looking for the number of sequences of length $k-3$ that have no TT subsequences. Say this is $S_{k-3}.$ Then $S_1 = 2, S_2 = 3,$ and now let's try to get a formula for $S_n.$ Think about how we start out the sequences. There are two types: either they start with H, or they start with TH. There are $S_{n-1}$ of the former and $S_{n-2}$ of the latter. So $S_n = S_{n-1} + S_{n-2},$ and there you go. In particular, $S_5 = 13,$ which is what you got.

And there is a closed-form formula for the Fibonacci numbers, if you're willing to put up with $\sqrt{5}$ floating around in various places!

Patrick Corn - 6 days, 14 hours ago

If you just want to verify the case of flipping a fair coin 8 times have TT at the last two flips, then it is rather easy.

As the last three flips must be HTT, it's probability $= 1/8$ .

For the first 5 flips, there are total $2^5 = 32$ scenarios. Count how many of them fulfill the requirements, that is no TT occurs.

Clearly, it cannot have $4$ or $5$ tails in these 5 flips.

No. of case for having 3 T $= THTHT = 1$

No. of case for having 2 T = $5\choose{2}$ $- 4 = 6$

No. of case for having 1 T = $5\choose{1}$ $= 5$

No. of case for having $0 T = 1$

So, for the first 5 flips, the probability that no TT occurs $= \cfrac{1+6+5+1}{32} = \cfrac{13}{32}$

And the required probability $= \cfrac{13}{32} \times \cfrac{1}{8} = \cfrac{13}{256}$

here for general case, refer to Mark Hennings solution.

Pop Wong - 1 month, 3 weeks ago

Thank You! Mark is a bit to brilliant for my level of understanding. I'm in awe, but for me his solutions suffer because of the "it is obvious that" methodology (my limitations obviously - not his ). It looks like he used the closed form equation for the $n^\text{th}$ Fibonacci number in some "massaged" way ( Which I honestly forgot even existed ). Surely proving the sequence is Fibonacci is not trivial. Its one thing to say, this looks like the Fibonacci, and a different thing to say this IS the Fibonacci sequence.

I was going to try to calculate the expected value using the series ( as one you have shown in one of your methods ), but its a good thing I failed to find a formula so early on! I didn't even realize that is what Mark had done in his solution...

😜

Mark is all round brilliant.

This problem I have done it several times before by renewal process method. This is my first time try to figure out the prob. density function. It is interesting to know that it is related to Fibonacci sequence.

Math	Appears as
Remember to wrap math in `\(` ... `\)` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$