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.

4 years, 10 months ago

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. 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 1paragraph 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}$$

Sort by:

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]$$.

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

Staff - 4 years, 10 months ago

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

1. 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).

2. 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:

1. "what is the probability that heads occur consecutively seven times?", in which case HHHHTTHHHHHTT would do as a "good" sequence,

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

- 4 years, 10 months ago

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

Staff - 4 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}$$.

- 4 years, 10 months ago