Waste less time on Facebook — follow Brilliant.
×

Coin flip combinatorics problem

Here is a problem I ran into years ago that I find interesting:

If you flip a fair coin ten times, what is the probability there will be at least one sequence of three consecutive heads or three consecutive tails?

Hint: We know that \(2^{10}=1024\)

To turn the problem into Brilliant format, I would ask: "Of the \(2^{10}=1024\) possibilities, how many contain at least one sequence of three consecutive heads or three consecutive tails?"

Note by Alex Porush
4 years, 1 month ago

No vote yet
6 votes

  Easy Math Editor

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 \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

Sort by:

Top Newest

Consider the two scenarios:

  1. Toss a coin \(n\) times. Whatever the value of the first toss is, just record whether each of the subsequent \(n-1\) tosses was the same as (\(S\)) or different to (\(D\)) its predecessor.

  2. Take a different coin whose sides are labelled \(S\) and \(D\), and toss it \(n-1\) times.

In both cases, each sequence of \(n-1\) \(S\)s and \(D\)s is equally likely. There are however two ways of obtaining each such sequence in the first scenario (since we can obtain each sequence once by throwing a head first, and once by throwing a tail first). The point of this is that the event of getting three or more consecutive heads, or three or more consecutive tails, in the first scenario exactly corresponds to the event of getting two or more consecutive \(S\)s in the second scenario.

Working in the second scenario, we want to know how many sequences of \(n-1\) tosses result in two or more consecutive \(S\)s. It is easier to count the sequences that do not. Let \(x_m\) be the number of sequences of \(m\) tosses of the relabelled coin that do not contain consecutive \(S\)s. Certainly \(x_1=2\) and \(x_2=3\). Suppose now that \(m \ge 3\).

  • It is clear the the number of sequences of \(m\) tosses that do not contain consecutive \(S\)s and which start with a \(D\) is just equal to \(x_{m-1}\), the number of sequence of \(m-1\) tosses that do not contain consecutive \(S\)s (just ignore the first toss);

  • If the first toss is \(S\), we need the second toss to be \(D\) if we want to be \(SS\)-free. Thus the number of sequences of \(m\) tosses that do not contain consecutive \(S\)s and which start with a \(S\) is just equal to \(x_{m-2}\).

Hence \(x_m \,=\, x_{m-1} + x_{m-2}\) for all \(m \ge 3\). From this it is clear that \(x_m = F_{m+2}\) is the \((m+2)\)nd Fibonacci number (starting the sequence \(F_0=0\), \(F_1=1\), etc. ).

We now interpret these results in the first scenario. The probability of getting three consecutive heads or three consecutive tails in \(n\) throws is \(1 - x_{n-1}2^{-(n-1)} = 1 - F_{n+1}2^{-(n-1)}\). Alternatively, the number of sequences of \(n\) coin tosses which contain three consecutive heads or three consecutive tails \(2^n - 2F_{n+1}\).

Mark Hennings - 4 years, 1 month ago

Log in to reply

Great explanation! I like how you created the bijection which simplified it slightly, and then did it again.

If you look at your answer, it suggests that we can take a simpler approach by counting the complement.

Hint: How many sequences of 1's and 2's are there which add up to \(n\)?

Calvin Lin Staff - 4 years, 1 month ago

Log in to reply

The question asked for the non-complemented answer, which I gave by counting the complemented answer, and then complementing!

Your hint refers to the standard problem: how many ways are there of tiling an \(n\times1\) chessboard with single squares and \(2\times1\) dominoes? Enter the Fibonacci numbers, in the guise of the numbers \(x_n\) above. The \(2\times1\) "dominoes" are \(SD\) tosses, and the "single squares" are either single \(D\) tosses, or else a toss of \(S\) at the end of the sequence.

Mark Hennings - 4 years, 1 month ago

Log in to reply

@Mark Hennings It is easier to count the complement to the original question, without going through your bijection.

Calvin Lin Staff - 4 years, 1 month ago

Log in to reply

@Calvin Lin If I understand you right, you are writing \(n\) as an ordered sum of \(1\)s and \(2\)s, and then interpreting each such sum as a sequence of heads of tails, where you change from heads to tails with each new number. Thus the sum \(7=1+1+2+1+2\) is either HTHHTHH or THTTHTT. There are \(F_{n+1}\) ways of writing \(n\) as a sum of \(1\)s and \(2\)s, and two sequences of coin tosses for each sum. This gives \(2F_{n+1}\) as the number of coin tosses with no successive HHH or TTT.

The idea of taking alternate numbers and inferring the change in head/taillness is just applying an argument equivalent to my bijection at the same time as doing the counting, My argument just separates the two processes. We are both more interested in tracking when the coin outcome changes than what its value is at any one time.

Mark Hennings - 4 years, 1 month ago

Log in to reply

Wow... you explained it thoroughly. Thank you very much.

Lokesh Sharma - 4 years, 1 month ago

Log in to reply

9/257

Jeffer Dave Cagubcob - 4 years, 1 month ago

Log in to reply

By "sequence of three consecutive heads" do you mean "sequence of exactly three consecutive heads" or "sequence of at least three consecutive heads?" For example, does HHHH count as a "sequence of three consecutive heads" or not?

Also, I'm having great difficulty understanding the purpose of your hint. Surely anyone capable of solving this problem already knows how to count the total number of possible outcomes of ten coin flips, and those who aren't so capable will not be helped at all by it! Are you trying to imply by a trivial hint that the problem has a trivial solution?

Christopher Johnson - 4 years, 1 month ago

Log in to reply

He means "sequence of at least three consecutive heads". Also, the hint is actually incredibly insightful if you're used to seeing such problems.

Henrik Boecken - 4 years, 1 month ago

Log in to reply

How is the hint incredibly insightful to such a person? What does it tell such a person that they don't already know from having seen such problems before? I'm not trying to be a jerk, here; I really want to know!

Christopher Johnson - 4 years, 1 month ago

Log in to reply

@Christopher Johnson Sorry I took so long to answer this. Basically, the hint is a well-known problem, and the answer is just the Fibonacci numbers. The way the question is worded though slightly obscures that. The hint provides a different way of looking at the problem which is much easier to understand. http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2630571&sid=517efe238b9f8891af7a818c8e105965#p2630571 is a similar example of a problem that is made more difficult by its wording. Sorry if I didn't explain that very well.

Henrik Boecken - 4 years, 1 month ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...