**Example 1**: What is the probability that there will be a run of at least 6 heads in 20 tosses of a fair coin?

We solve this problem by recursion. Let *p* = the probability that a heads will occur on any toss, *r* = the size of run we are looking for and *n* = the total number of tosses. For Example 1, *p* = .5, *r* = 6 and *n* = 20. Now for* i* = 0, 1, …, *n*, and *j* = 0, 1, …, *r* define

*f*(*i, j*) = the probability of getting a run of at least *r* heads in *n* tosses assuming there are *i* tosses remaining and the last* j* tosses have all been heads and so far there has not been a run of *r* heads.

Clearly for all *j < r*

*f*(0, *j*) = 0

And for all* i*

*f*(*i*, *r*) = 1

For all *i* > 0 and *j < r*, we have the following recursive formula:

*f*(*i, j*) = *p ∙ f*(*i – *1, *j *+ 1) + (1 – *p* ) ∙ *f*(*i *– 1, 0)

Here the leftmost term on the right side of the equation corresponds to getting a heads when *i* tosses remain and the rightmost term corresponds to getting tails when *i* tosses remain.

Thus the probability that there will be a run of at least *r* heads in n tosses of a coin with probability *p* that a heads will occur on any toss is given by *f*(*n*, 0).

We solve Example 1 by building an Excel worksheet as shown in Figure 1.

**Figure 1 – Run of at least 6 heads in 20 tosses**

Here range B3:G3 consists of all 0’s, range H4:H24 consists of all 1’s. Cell B5 contains the formula =0.5*C4+0.5*$B4. We then copy this formula into the rest of the table by highlighting the range B5:G24 and pressing Ctrl-D and Ctrl-R.

We see (cell B24) that the value of *f*(20, 0) = .122315. This is the result we are looking for. The probability of getting a run of at least 6 heads in 20 tosses of a fair coin is .122315.

If we want to know the probability that the longest run of heads in 20 tosses is 6 heads, then we need to first calculate the probability of a run of at least 7 heads in 20 tosses, as shown in Figure 2.

**Figure 2 – Run of at least 7 heads in 20 tosses**

Figure 2 shows that the probability of a run of at least 7 heads is .058182. Thus the probability that the longest run of heads is exactly 6 heads is .122315 – .058182 = .064133. We can’t say that the probability of a run of exactly 6 heads is .064133 since we can have situations where there are runs of 6 heads as well as 7 or more heads (e.g. HHHHHHTHHHHHHHTTTTTT).

**Example 2**: What is the probability that there will be a run of at least 6 in 20 tosses of a fair coin?

Here the run can be of either heads or tails. Once again we solve this problem by recursion. This time for *i* = 0, 1, …, *n – *1, and *j* = 1, 2, …, *r* define

*g*(*i, j*) = the probability of getting a run of least *r* during n tosses assuming there are *i* tosses remaining and the last* j* tosses have all been the same and so far there has not been a run of *r* heads or tails.

This time to keep things simple, we will assume that we have a fair coin and so *p* = .5.

Clearly for all 0 < *j < r*

*g*(0, *j*) = 0

And for all *i < n*

*g*(*i, r*) = 1

For all 0 <* i < n* and *j < r*, we have the following recursive formula:

*g*(*i, j*) = .5* ∙ g*(*i – *1, *j *+ 1) + .5 ∙ *g*(*i *– 1, 1)

Here the leftmost term on the right side of the equation corresponds to getting the same outcome as on the previous toss when *i* tosses remain and the rightmost term corresponds to getting a different outcome from the previous toss when *i* tosses remain.

Thus the probability that there will be a run of at least *r* in n tosses of a fair coin is given by *g*(*n – *1, 1).

We solve Example 2 by building the Excel worksheet shown in Figure 3.

**Figure 3 – Run of at least 6 in 20 tosses**

The probability of getting a run of at least 6 heads or tails in 20 tosses of a fair coin is .23877 (cell U23).

Charles

Thanks for the reference from your Binomial distribution section to this section on Runs, which is the correct section for my issues.

Chris

yes, you found it!

you were actually solving a different question

and it is very simple to do in Excel and looks to work for any value of p

that is for example P(6+run) – P(7+run)

“Thus the probability of a run of exactly 6 heads is”

requires a different Markov chain recursion with 9 states

run 0

r 1

r 2

r 3

r 4

r 5

r 6

r 7+

r 6,0 (this state is absorbing)

we sum states r6 and the cumulative value for r6,0 at each flip

for the probability

easy and fun for Excel to handle 🙂

wish i could add an image to my comment

(i think WordPress can do this with a Plugin)

I liked the Excel approach with “states” being the number of Heads (success) remaining instead of one where the states are the # of Heads in a row

I disagree with the final value in this statement

“Figure 2 shows that the probability of a run of at least 7 heads is .058182. Thus the probability of a run of exactly 6 heads is .122315 – .058182 = .064133”

68625 /1048576 (0.0654459)

is the exact answer I got from a Markov chain and recursion in my Excel

(and just brute force counting too)

for example

a run = 3 (exactly 3) = P(3+) – P(4+) only when N =8

and that is because we must sum 2 different states the chain can be in after N trials

either after the Nth trial being in state = 3run (T HHH)

or that is has been in HHHT

for the e6run

the successful sequences could be either T HHH HHH at the end

or T HHH HHH T at all other locations except the beginning HHH HHH T

you should be pleasantly surprised by setting up the recursion for exactly 6

and see what i mean

if you email me i could send you a link to my Excel workbook to view

in my online folder

thank you for a wonderful website!

Sally

my example got changed

“for example

a run = 3 (exactly 3) = P(3+) – P(4+) only when N =8”

should read

for example

a run = 3 (exactly 3) = P(3+) – P(4+) only when N is less than or equal to 7

it breaks down when N is greater than or equal to 8

subtracting the two values most times will result in errors, some very large

Sally,

Yes, you are correct. If N = 8 and r = 3, the problem occurs in the two cases where there is a run of 4 heads as well as a run of 3 heads, namely HHHTHHHH and HHHHTHHH. Thanks for pointing out this error.

The statement I should have made is

“Figure 2 shows that the probability of a run of at least 7 heads is .058182. Thus the probability that the longest run of heads is exactly 6 is .122315 – .058182 = .064133″

Charles