# Solution to puzzle 145: Heads and tails

A fair coin is tossed n times and the outcome of each toss is recorded.  Find the probability that in the resulting sequence of tosses a head immediately follows a head exactly h times and a tail immediately follows a tail exactly t times.  (For example, for the sequence HHHTTHTHH, we have n = 9, h = 3, and t = 1.)

This problem is a counting exercise.  We will count the number of ways in which, when a coin is tossed n times, a head immediately follows a head exactly h times and a tail immediately follows a tail exactly t times.  We will then divide this by the number of possible outcomes when a coin is tossed n times; that is, 2n.  Since the coin is fair, this will yield the required probability.

There are n − 1 consecutive pairs of tosses: (1st, 2nd), (2nd, 3rd), ... , ((n−1)st, nth).
Of these, there are h HH pairs and t TT pairs, leaving n − h − t − 1 pairs that are either HT or TH.

Let {H} denote a block of one or more heads, and {T} denote a block of one or more tails.
Note that each HT pair corresponds to {H} followed by {T}; similarly each TH pair corresponds to {T} followed by {H}. Hence the total number of blocks is one greater than the number of HT and TH pairs; that is, there are n − h − t blocks.

If the number of blocks is even, there are two configurations for each particular number of blocks, one beginning with {H} and one beginning with {T}.  For example, with four blocks, we have
{H}{T}{H}{T} or {T}{H}{T}{H}.

If the number of blocks is odd, again there are two configurations for each particular number of blocks.  For example, with five blocks, we have
{H}{T}{H}{T}{H} or {T}{H}{T}{H}{T}.

We now consider these two cases separately.

## Number of blocks is even

Consider first the configuration beginning with {H}.  (The other configuration will follow similarly.)
We have ½(n − h − t) {H} blocks and ½(n − h − t) {T} blocks.
If we assume that each block initially contains only one element, then we must distribute the extra elements into the available blocks.
The number of different ways to distribute m indistinguishable balls (the extra heads and tails) into k distinguishable boxes (the blocks, distinguished by their order) is .

(Think of the k boxes as being k − 1 dividing lines, around which the m balls must be distributed.  For instance, if k = 4 and m = 7, one possible arrangement is ****|**||*, which represents 4 balls in box 1, 2 balls in box 2, 0 balls in box 3, and 1 ball in box 4.  Since we have m balls and k − 1 boxes, the total number of such arrangements is by definition given by the binomial coefficient .)

Hence the number of ways to distribute an extra h heads into ½(n − h − t) {H} blocks is .
Similarly, the number of ways to distribute an extra t tails into ½(n − h − t) {T} blocks is .
The total number of distributions for the first configuration is therefore equal to the product of these two numbers.
The total number for the second configuration (beginning with {T}) is the same, by symmetry.  Hence the total number of distributions is:

.

## Number of blocks is odd

First of all we must deal with a special case.  If there is only one block, then the outcome was the same on every toss.
The only block is {H} h = n − 1 (and t = 0) every outcome was heads.
The only block is {T} t = n − 1 (and h = 0) every outcome was tails.
In either case, there is precisely one way in which the distribution can occur.

We now assume the number of blocks is greater than one.  Consider first the configuration beginning with {H}.
We have ½(n − h − t + 1) {H} blocks and ½(n − h − t − 1) {T} blocks.

The number of ways to distribute an extra h heads into ½(n − h − t + 1) {H} blocks is .
The number of ways to distribute an extra t tails into ½(n − h − t − 1) {T} blocks is .
The total number of distributions for the first configuration is equal to the product of these two numbers.

Now consider the configuration beginning with {T}.
We have ½(n − h − t − 1) {H} blocks and ½(n − h − t + 1) {T} blocks.

The number of ways to distribute an extra h heads into ½(n − h − t − 1) {H} blocks is .
The number of ways to distribute an extra t tails into ½(n − h − t + 1) {T} blocks is .
The total number of distributions for the second configuration is equal to the product of these two numbers.

Hence the total number of distributions is:

.

## Conclusion

We now divide the above numbers by 2n to obtain the required probabilities.  The probability that when a fair coin is tossed n times a head immediately follows a head exactly h times and a tail immediately follows a tail exactly t times is:

 , if n − h − t is even. , if h = n − 1 or t = n − 1. , otherwise.

Source: Original