3.2 The Alternating Strings Problem............................. 8

We give some examples of differentiating identities to prove formulas in probability theory and combinatorics. The main result we prove concerns the number of alternating strings of heads and tails in tossing a coin. Specifically, if we toss a coin n1 + n2 times and see n1 heads and n2 tails, the mean of the number of runs is 2n1n2n1+n2 + 1 and the variance is 2n1n2(2n1n2−n1−n2) (n1+n2)2(n1+n2−1). For example, if we observed HHHTHHTTTTHTT then n1 = 6, n2 = 7 and there would be 6 alternating strings or 6 runs. More generally, assume we toss a coin with probability p of heads a total of N times. The expected number of runs is 2p(1 − p)(N − 1) + 1. In particular, if the coin is fair (so p = 12) the