Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
The calculation is not too difficult but somewhat involved. It is much easier to calculate the probability that the coin lands tails at most 6 (resp. at most 5) times in a row. This probability is described by a linear recurrence which has a closed formula depending on the roots of its characteristic polynomial, and evaluating it at n = 150 gives the answer. –  Qiaochu Yuan Sep 14 '10 at 15:08
    
Thanks, I figure the odds would be 1 in 128 if there were just 7 coin flips... but I'm stuck as to how to calculate for n = 150 –  Chuck Sep 14 '10 at 18:52
4  
To see why the probability is much larger than 1/128, break the 150 coin flips into 21 groups of 7 (plus 3 left over) and ask what the chance is that none of those groups has seven tails. Answer: (1 - 1/128)^21 = about 0.85. Its complement, 0.15 = 1-0.85, underestimates the solution because the seven in a row could span two groups. An overestimate is obtained by looking at the 144 overlapping groups of 7 flips: 1 - (1-1/128)^144 = 0.68; it's an overestimate because the groups are correlated. The truth lies somewhere in between, as the answers below more rigorously attest. –  whuber Sep 14 '10 at 20:59
    
A longish article about such probabilities can be found there: gato-docs.its.txstate.edu/mathworks/… –  Jens Sep 15 '10 at 6:25
add comment

6 Answers 6

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.

share|improve this answer
3  
Nice answer! I didn't realize that it would be reasonable to approximate this by hand. –  David Speyer Sep 14 '10 at 19:13
8  
@Qiaochu: You nailed it. Monte-Carlo simulation yields 0.441 good to +-1 in the last digit (based on 1,000,000 trials). Mathematica's exact answer is $\frac{2464002327877623998726653015374205492738387}{5575186299632655785383929568‌​162090376495104} = 0.441958742802904180259284$ etc. :-). –  whuber Sep 14 '10 at 21:15
2  
Wow, that's impressive thanks guys! My statistics/math is rusty as hell. I didn't know it would be that complicated of a question but that's a very thorough answer to say the least! That helps a lot... btw I'm asking because I've toying with the notion of using a Martingale system for next baseball season.Using historical data from the past three MLB seasons you would have a .44% chance of losing $19,392.07 and a 99.56% chance of winning $5,279.32 if you bet the run line (-1.5) on the biggest favorite as shown by the opening line. Sounds pretty good if you can stomach a liiiiiittle risk ;) –  Chuck Sep 15 '10 at 0:20
2  
Chuck, I think you're misinterpreting the results. The probability is about 0.44. This does not mean it has a 0.44% chance of occurring; it means it has a 44% chance! –  Jonas Kibelbek Sep 15 '10 at 1:10
3  
Better stick to my day job LOL –  Chuck Sep 15 '10 at 1:27
show 5 more comments

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.

share|improve this answer
add comment

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 an (1-(1/2)^(L-1))^(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

share|improve this answer
add comment

The probability for NO run in n flips is the coefficient of x^n of the polynom series of G:=(p,r,x)->(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%)

share|improve this answer
add comment

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.

share|improve this answer
1  
Welcome to math.stackexchange.com! It would be most helpful---and you will garner more responses---if you would format any mathematics in your post according to these instructions: meta.math.stackexchange.com/questions/107/… –  JohnD Dec 18 '12 at 5:00
add comment

Here's a way to get an approximation for the answer via a simulation. It's kinda fun to tweak the numbers and see the probability change.

Run this in Tools -> Javascript Console in Chrome or Tools -> Web Developer -> Web Console in FireFox:

function experiment(streak, tosses) {
  var i, ctr = 0;
  for (i = 0; i < tosses; i++) {
    if (Math.random() < 0.5) ctr = 0;
    else if (++ctr === streak) return 1;
  }
  return 0;
}

function run(streak, tosses, runs) {
  var i, total = 0;
  for (i = 0; i < runs; i++) {
    total += experiment(streak, tosses);
  }
  return total / runs;
}

console.log('\nP(A) = %s\n',
  run(7, 150, 1e6));

I get the following result:

P(A) = 0.441693

Which is close to the other answers here.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.