Waste less time on Facebook — follow Brilliant.
×

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.

Note by Russelle Guadalupe
4 years, 2 months ago

No vote yet
5 votes

Comments

Sort by:

Top Newest

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 - 4 years, 2 months ago

Log in to reply

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 - 4 years, 2 months ago

Log in to reply

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.

Mark Hennings - 4 years, 2 months ago

Log in to reply

@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 - 4 years, 2 months ago

Log in to reply

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 - 4 years, 2 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...