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.