Getting Consecutive Heads

Suppose that a fair coin is tossed $13$ times. Find the probability that exactly $7$ consecutive heads will occur.

Generalize this problem for $n$ tosses and $r$ consecutive heads.

#Combinatorics #MathProblem #Math

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

Let $H_n$ be the number of successive heads obtained in $n$ tosses, given that the first toss is a head, and let $T_n$ be the number of successive heads obtained in $n$ tosses, given that the first toss is a tail. The number of successive heads obtained in $n$ tosses is the same as $T_{n+1}$ . Thus we want to know $P[T_{13}=7]$ or, more generally, the distribution of $T_{n+1}$ .

Conditioning on the outcome of the second toss, we see that $P[H_n=k] \; = \; \left\{\begin{array}{l@{\qquad\qquad\qquad}l} \tfrac12P[H_{n-1}=k-1] + \tfrac12P[T_{n-1}=k] & k \ge 1 \\ \tfrac12P[T_{n-1}=k] & k = 0 \end{array}\right.$ $P[T_n=k] \; = \; \tfrac12P[H_{n-1}=k] + \tfrac12P[T_{n-1}=k]$ for all $n \ge 2$ .

If $H_n(t)$ and $T_n(t)$ are the probability generating functions of $H_n$ and $T_n$ respectively, then $H_1(t) = T_1(t) = 1$ , while $H_n(t) \; =\; \tfrac12tH_{n-1}(t) + \tfrac12T_{n-1}(t) \qquad \qquad T_n(t) \; = \; \tfrac12H_{n-1}(t) + \tfrac12T_{n-1}(t)$ for $n \ge 2$ . Plugging these recurrence relations into Mathematica gives $T_{13}(t) \; =\; \frac{1}{4096}\left(\begin{array}{c} 377 + 744t + 894t^2 + 806t^3 + 588t^4 + 363t^5 \\ []+ 188x^6 + 89x^7 + 31x^8 + 13x^9 + 2x^{10} + x^{11} \end{array}\right)$ and hence $P[T_{13}=7] \,=\, \tfrac{89}{4096}$ .

More generally, we can solve the matrix recurrence relation ${ H_n(t) \choose T_n(t)} \; = \; {\tfrac12t \qquad \tfrac12 \choose \tfrac12 \qquad \tfrac12 } {H_{n-1}(t) \choose T_{n-1}(t)} \qquad \qquad n \ge 2$ together with the ground step ${H_1(t) \choose T_1(t)} \,=\, {1 \choose 1}$ . Looking for eigenvalues and eigenvectors of the matrix, we deduce that ${H_n(t) \choose T_n(t)} \; = \; \alpha\left(\frac{t+1+\sqrt{t^2-2t+5}}{4}\right)^{n-1}{t-1+\sqrt{t^2-2t+5} \choose 2} \\ \; + \; \beta\left(\frac{t+1-\sqrt{t^2-2t+5}}{4}\right)^{n-1}{t-1 - \sqrt{t^2-2t+5} \choose 2}$ where $\alpha,\beta$ are such that $(t-1)(\alpha+\beta) + (\alpha-\beta)\sqrt{t^2-2t+5} \; =\; 1 \qquad \qquad 2(\alpha+\beta)\;=\;1$ The conditions on $\alpha$ and $\beta$ make the formula work for $n=1$ . When $n$ is odd the formula for $T_n(t)$ can be "simplified" into a shape which is visibly polynomial, and we obtain $T_{2n+1}(t) = \frac{1}{4^{2n}}\sum_{j=0}^n {2n \choose 2j}(t+1)^{2n-2j}(t^2-2t+5)^j - \frac{t-3}{4^{2n}}\sum_{j=0}^{n-1}{2n \choose 2j+1}(t+1)^{2n-2j-1}(t^2-2t+5)^j$ I have yet to obtain a closed form for $P[T_{2n+1}=k]$ .

Mark Hennings - 7 years, 10 months ago

I do not understand what your initial equations are measuring, or why they are true. Note that $H_n$ should measure the maximum number of successive heads, and not just the initial length of successive heads.

When $n >> r$ , then there could be multiple strings of successive heads which are at the maximum. In this case, it is not clear what your recurrence relation is supposed to be counting. This is also where your recurrence relations break down.

My value of 7 consecutive heads out of 13 coins is different from either of your values.

In the case that $r \leq 2n$ , we can do a direct counting of the cases. For $r > 2n$ , we need to use PIE to avoid double counting.

Calvin Lin Staff - 7 years, 10 months ago

Consider $n$ tosses, where the first is a head.

If the second toss is a head (with probability $\tfrac12$ ), then the probability of getting $k$ occurrences of consecutive heads out of the $n$ tosses is the probability of getting $k-1$ occurrences of consecutive heads out of the final $n-1$ tosses (excluding the first one) where we now have that the first of these $n-1$ tosses is a head (the first two tosses have given us one such occurrence).
If the second toss is a tail (with probability $\tfrac12$ ), then the probability of getting $k$ occurrences of consecutive heads out of the $n$ tosses is the probability of getting $k$ occurrences of consecutive heads out of the final $n-1$ tosses (excluding the first one) where we now have that the first of these $n-1$ tosses is a tail (we have not obtained a successive head occurrence in the first pair this time).

Thus

$P[H_n=k] \; = \; \tfrac12P[H_{n-1}=k-1] + \tfrac12P[T_{n-1}=k]$

with similar arguments holding for the other formulae.

Our difference of opinion on this may be about what the question is asking. The question can be read as:

"what is the probability that heads occur consecutively seven times?", in which case HHHHTTHHHHHTT would do as a "good" sequence,
or as "what is the probability that a string of seven consecutive heads occurs?", in which "good" sequences would be like TTHHHHHHHTTHT.

I am answering the first of these questions.

Mark Hennings - 7 years, 10 months ago

@Mark Hennings – Ah yes, that's a fair interpretation. I was considering the second version. In which case, I concur with your analysis.

Note that your recurrence relation should use the variable $t$ instead of $x$ .

Calvin Lin Staff - 7 years, 10 months ago

Oops! The coin is tossed $13$ times, not $12$ . Thus the distribution we want is $T_{14}$ , not $T_{13}$ . Now

$T_{14}(t) \; = \; \tfrac{1}{8192}\left(\begin{array}{c} 610 + 1308t + 1686t^2 + 1624t^3 + 1269t^4 + 834t^5 + 476t^6 \\ {} + 230t^7 + 104t^8 + 34t^9 + 14t^{10} + 2t^{11} + t^{12} \end{array}\right)$ and hence $P[T_{14}=7] = \tfrac{230}{8192} = \tfrac{115}{4096}$ .

Mark Hennings - 7 years, 10 months ago

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}$