# Runs

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, + 1) + (1 – p ) ∙ f(– 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, + 1) + .5 ∙ g(– 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).

### 5 Responses to Runs

1. Sally Oh says:

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

• Sally Oh says:

my example got changed
“for example
a run = 3 (exactly 3) = P(3+) – P(4+) only when N =8”

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

• Charles says:

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

2. Sally Oh says:

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)

3. Chris Palmer says:

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