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.

Runs heads

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.

Run heads in Excel

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.

Run heads or tails

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

  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. 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”

      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

      • 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

Leave a Reply

Your email address will not be published. Required fields are marked *