# Average Number of Runs

A coin is tossed several times and the outcomes are being recorded in a string of H (heads) and T (tails). For example,

is recorded as "HHTTTHTH". Now, a ** run** is any part of such a record that consists of a maximal number of contiguous equal outcomes. In the example, we have five runs "HH," "TTT", "H," "T," "H." Their lengths are 2, 3, 1, 1, 1;2, 3, 1, 1, 1;2, 2, 1, 2, 1;1, 3, 1, 1, 2, respectively. Now the question

### Solution

Instead of counting the number of runs we'll count the number of breaks between the runs, i.e., the number of pairs HT or TH. Obviously, the number of breaks is one less than;one more than;equal to;one less than the number of runs.

As has been noted, a break occurs when two successive tosses have different outcomes. All in all, two coin tosses may have 4 ; 3 ; 4 ; 5 outcomes; the two tosses are different in 2 ; 2 ; 3 ; 4 cases and equal in 2 ; 2 ; 3 ; 4 . Thus the probability of a break occurring over a particular pair of tosses is 1/2 ; 1/2 ; 1/3 ; 1/4 .

For $N\,$ tosses of the coin there are N-1;N+1;N;N-1 successive pairs of tosses, each having an expectation of $\displaystyle 0\times\frac{1}{2}+1\times\frac{1}{2}=\frac{1}{2}\,$ of constituting a break. The expectation being a linear;multiplicative;traditional;linear;rarily used function, the expected number of breaks among $N-1\,$ pairs is (N-1)/2;$(N+1)/2$;$N/2$;$(N-1)/2$.

It follows that the average number of runs is $\displaystyle\frac{N-1}{2}+1=\frac{N+1}{2}.$

### Acknowledgment

This problem has been given at the term exam for CIS160 at UPenn, where my young son was a freshman. The solution is his.

- What Is Probability?
- Intuitive Probability
- Probability Problems
- Sample Spaces and Random Variables
- Probabilities
- Conditional Probability
- Dependent and Independent Events
- Algebra of Random Variables
- Expectation
- Admittance to a Tennis Club
- Average Number of Runs
- Number of Trials to First Success

- Probability Generating Functions
- Probability of Two Integers Being Coprime
- Random Walks
- Probabilistic Method
- Probability Paradoxes
- Symmetry Principle in Probability
- Non-transitive Dice

|Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny

62824115 |