Coin Flipping

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

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

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

The sequence of flips would have to end in HTT 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 T 's and H H's such that no T 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 25 2^5 possible adjoining strings those with adjacent T T 's.

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

there are (52) {5 \choose 2} adjoining 2T2 T sequences

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

      T2 \Box \; \Box \; \Box \; T_2

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

Thus there are (52)4=6 {5 \choose 2} - 4 = 6 , 2T2 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 T's to the sequence.

With 3T3 T's , I have to not only worry about T3 T_3 groupings, but also the sub groupings of 2T2 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!

Note by Eric Roberts
1 week, 5 days ago

No vote yet
1 vote

  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.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. 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"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

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 TTs we can put in this adjoining string without creating any pairs: 00 TTs, 11 TT, 22 TTs, and 33 TTs. Any more, and we won't be able to keep them separated (since we only have 55 spots to work with).

There's 1\boldsymbol{1} way to use 00 TTs: HHHHHHHHHH

There's 5\boldsymbol{5} ways to use 11 TT: THHHH\boldsymbol{T}HHHH, HTHHHH\boldsymbol{T}HHH, HHTHHHH\boldsymbol{T}HH, HHHTHHHH\boldsymbol{T}H, and HHHHTHHHH\boldsymbol{T}.

There's 6\boldsymbol{6} ways to use 22 TTs: THTHH\boldsymbol{T}H\boldsymbol{T}HH, THHTH\boldsymbol{T}HH\boldsymbol{T}H, THHHT\boldsymbol{T}HHH\boldsymbol{T}, HTHTHH\boldsymbol{T}H\boldsymbol{T}H, HTHHTH\boldsymbol{T}HH\boldsymbol{T}, and HHTHTHH\boldsymbol{T}H\boldsymbol{T}.

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

And there's 1\boldsymbol{1} way to use 33 TTs: THTHT\boldsymbol{T}H\boldsymbol{T}H\boldsymbol{T}.

So in total, we have 13\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 13256\boxed{\frac{13}{256}}.

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

Hope this made sense!

David Stiff - 1 week, 5 days ago

Log in to reply

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
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')

David Stiff - 1 week, 5 days ago

Log in to reply

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 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 week, 5 days ago

Log in to reply

@Eric Roberts Yes, I can verify 99 flips results in 2121 valid sequences. I tried 1010 and 1111 as well, and they yielded 3434 and 5555, so it does indeed seem that the Fibonacci numbers have once again popped up! :)

David Stiff - 1 week, 4 days ago

Log in to reply

@David Stiff 👌 Thank You David!

Eric Roberts - 1 week, 4 days ago

Log in to reply

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= 1/8.

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

Clearly, it cannot have 44 or 55 tails in these 5 flips.

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

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

No. of case for having 1 T = (51) 5\choose{1} =5= 5

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

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

And the required probability =1332×18=13256= \cfrac{13}{32} \times \cfrac{1}{8} = \cfrac{13}{256}

here for general case, refer to Mark Hennings solution.

Pop Wong - 1 week, 5 days ago

Log in to reply

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

😜

Eric Roberts - 1 week, 4 days ago

Log in to reply

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.

Pop Wong - 1 week, 4 days ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...