What is the probability of a coin landing tails 7 times in a row in a series of 150 coin flips?

If you were to flip a coin 150 times, what is the probability that it would land tails 7 times in a row? How about 6 times in a row? Is there some forumula that can calculate this probability?

Solution 1:

Here are some details; I will only work out the case where you want $7$ tails in a row, and the general case is similar. I am interpreting your question to mean "what is the probability that, at least once, you flip at least 7 tails in a row?"

Let $a_n$ denote the number of ways to flip $n$ coins such that at no point do you flip more than $6$ consecutive tails. Then the number you want to compute is $1 - \frac{a_{150}}{2^{150}}$. The last few coin flips in such a sequence of $n$ coin flips must be one of $H, HT, HTT, HTTT, HTTTT, HTTTTT$, or $HTTTTTT$. After deleting this last bit, what remains is another sequence of coin flips with no more than $6$ consecutive tails. So it follows that

$$a_{n+7} = a_{n+6} + a_{n+5} + a_{n+4} + a_{n+3} + a_{n+2} + a_{n+1} + a_n$$

with initial conditions $a_k = 2^k, 0 \le k \le 6$. Using a computer it would not be very hard to compute $a_{150}$ from here, especially if you use the matrix method that David Speyer suggests.

In any case, let's see what we can say approximately. The asymptotic growth of $a_n$ is controlled by the largest positive root of the characteristic polynomial $x^7 = x^6 + x^5 + x^4 + x^3 + x^2 + x + 1$, which is a little less than $2$. Rearranging this identity gives $2 - x = \frac{1}{x^7}$, so to a first approximation the largest root is $r \approx 2 - \frac{1}{128}$. This means that $a_n$ is approximately $\lambda \left( 2 - \frac{1}{128} \right)^n$ for some constant $\lambda$, which means that $\frac{a_{150}}{2^{150}}$ is roughly

$$\lambda \left( 1 - \frac{1}{256} \right)^{150} \approx \lambda e^{ - \frac{150}{256} } \approx 0.56 \lambda$$

although $\lambda$ still needs to be determined.

Edit: So let's approximate $\lambda$. I claim that the generating function for $a_n$ is

$$A(x) = 1 + \sum_{n \ge 1} a_{n-1} x^n = \frac{1}{1 - x - x^2 - x^3 - x^4 - x^5 - x^6 - x^7}.$$

This is because, by iterating the argument in the second paragraph, we can decompose any valid sequence of coin flips into a sequence of one of seven blocks $H, HT, ...$ uniquely, except that the initial segment does not necessarily start with $H$. To simplify the above expression, write $A(x) = \frac{1 - x}{1 - 2x + x^8}$. Now, the partial fraction decomposition of $A(x)$ has the form

$$A(x) = \frac{\lambda}{r(1 - rx)} + \text{other terms}$$

where $\lambda, r$ are as above, and it is this first term which determines the asymptotic behavior of $a_n$ as above. To compute $\lambda$ we can use l'Hopital's rule; we find that $\lambda$ is equal to

$$\lim_{x \to \frac{1}{r}} \frac{r(1 - rx)(1 - x)}{1 - 2x + x^8} = \lim_{x \to \frac{1}{r}} \frac{-r(r+1) + 2r^2x}{-2 + 8x^7} = \frac{r^2-r}{2 - \frac{8}{r^7}} \approx 1.$$

So my official guess at the actual value of the answer is $1 - 0.56 = 0.44$. Anyone care to validate it?

Sequences like $a_n$ count the number of words in objects called regular languages, whose enumerative behavior is described by linear recurrences and which can also be analyzed using finite state machines. Those are all good keywords to look up if you are interested in generalizations of this method. I discuss some of these issues in my notes on generating functions, but you can find a more thorough introduction in the relevant section of Stanley's Enumerative Combinatorics.

Solution 2:

I'll sketch a solution; details are left to you.

As you flip your coin, think about what data you would want to keep track of to see whether $7$ heads have come up yet. You'd want to know: Whether you have already won and what the number of heads at the end of your current sequence was. In other words, there are $8$ states:

$A$: We have not flipped $7$ heads in a row yet, and the last flip was $T$.

$B$: We have not flipped $7$ heads in a row yet, and the last two flips was $TH$.

$C$: We have not flipped $7$ heads in a row yet, and the last three flips were $THH$.

$\ldots$

$G$: We have not flipped $7$ heads in a row yet, and the last seven flips were $THHHHHH$.

$H$: We've flipped $7$ heads in a row!

If we are in state $A$ then, with probability $1/2$ we move to state $B$ and with probability $1/2$ we stay in state $A$. If we are in state $B$ then, with probability $1/2$ we move to state $C$ and with probability $1/2$ we move back to state $A$. $\ldots$ If we are in state $G$, with probability $1/2$ we move forward to state $H$ and with probability $1/2$ we move back to state $A$. Once we are in state $H$ we stay there.

In short, define $M$ to be the matrix $$\begin{pmatrix} 1/2 & 1/2 & 1/2 & 1/2 & 1/2 & 1/2 & 1/2 & 0 \\ 1/2 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1/2 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1/2 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1/2 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1/2 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1/2 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1/2 & 1 \end{pmatrix}$$

Then the entries of $M^n$ give the probability of transitioning from one given state to another in $n$ coin flips. (Please, please, please, do not go on until you understand why this works! This is one of the most standard uses of matrix multiplication.) You are interested in the lower left entry of $M^{150}$.

Of course, a computer algebra system can compute this number for you quite rapidly. Rather than do this, I will discuss some interesting math which comes out of this.

(1) The Perron-Frobenius theorem tells us that $1$ is an eigenvalue of $M$ (with corresponding eigenvector $(0,0,0,0,0,0,0,1)^T$, in this case) and all the other eigenvalues are less then $1$. Let $\lambda$ be the largest eigenvalue less than $1$, then probability of getting $7$ heads in a row, when we flip $n$ times, is approximately $1-c \lambda^n$ for some constant $c$.

(2) You might wonder what sort of configurations of coin flips can be answered by this method. For example, could we understand the case where we flip $3$ heads in a row before we flip $2$ tails in a row? (Answer: Yes.) Could we understand the question of whether the first $2k$ flips are a palindrome for some $k$? (Answer: No, not by this method.) In general, the question is which properties can be recognized by finite state automata, also called the regular languages. There is a lot of study of this subject.

(3) See chapter $8.4$ of Concrete Mathematics, by Graham, Knuth and Patashnik, for many more coin flipping problems.

Solution 3:

With respect to the exact answer, the recursion is related to the Fibonacci n-Step Numbers (look at the phrase below the table).

With respect to an approximate/asympotic solution: it can also be obtained by probabilistic reasoning.

Instead of throwing N (150) coins, lets consider the (thought) experiment of throwing M alternate runs (a ‘run’ is a sequence of consecutive tails/heads). That is, instead of throwing N iid Bernoulli random variables (two values with prob=1/2), we throw M iid geometric random variables ( p(1)=1/2 p(2)=1/4 p(3)=1/8 ...) which we interpret as the length of each alternate run of consecutive tails/head in the coins sequence.

The expected value of the the runs (in both experiments) is 2. If we choose M=N/2, then the expected total number of coins (in the seconde experiment) will be N, and so we can expect (informally) that the two experiments are asympotically equivalent (in the original experiment the number of coins is fixed, the number of runs is a random variable; in the second, the reverse; this could be related to the use of different ensembles in statistical physics).

Now, in the modified experiment it’s easy to compute the probability that no run exceeds a length L: it’s just $(1-1/2^{L})^{N/2}$ If we consider just tails, the number of "trials" would be N/4 instead. This, in our case, (L=150, N=6) gives P=0.44160

Solution 4:

The probability for NO run in $n$ flips is the coefficient of $x^n$ of the polynom series of $$G := (p,r,x) \to \frac{1-p^r x^r} {1-x+(1-p)*(p^r)*x^{r+1}}$$ For $p=0.5$, $r=7$, the coefficient of $x^{150}$ is $0.558041257197$.

The probability for One run or more is $0.441958742803$ (44.19%).

Solution 5:

I would've thought a better approximation would be:

$$λ(1−1 256 ) 144 ≈λe −144/256 ≈0.57λ $$

$$P = 1 - 0.57 = 0.43$$

Since it's not possible to get 7 consecutive heads in the first 6 flips. However this is clearly a worse approximation, assuming the Monte Carlo is accurate.