Problem 5

The Bank of Bath issues coins with an

H

on one side and a

T

on the other. Harry has

n

of these coins arranged in a line from left to right. He repeatedly performs the following operation: if there are exactly

k>0

coins showing

H

, then he turns over the

k

th coin from the left; otherwise all coins show

T

and he stops. For example, if

n=3

, the process starting with

THT

THT\to HHT\to HTT\to TTT

, which stops after three operations. (a) Show that, for each initial configuration, Harry stops after a finite number of operations. (b) For each initial configuration

C

, let

L(C)

be the number of operations before Harry stops. Determine the average value of

L(C)

over all

2^n

possible initial configurations.

Step 2 of 6: A final tail is inert

Previous step Next step

In plain words

The last position is never selected while it is a tail.

C=C'T\Longrightarrow L(C)=L(C')

Detailed analysis

Suppose the last coin is $T$ . There can be at most $n-1$ heads, so the rule never selects coin $n$ . The first $n-1$ coins therefore evolve exactly as an independent $(n-1)$ -coin configuration $C'$ , and $L(C)=L(C')$ . By induction this branch terminates and has average $E_{n-1}$ .