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

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

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)

Charles

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

Chris