Problem: Let $n$ be a positive integer.
Harry has $n$ coins lined up on his desk, which can show either heads or tails.
He does the following operation: if there are $k$ coins which show heads and $k > 0$,
then he flips the $k$th coin over; otherwise he stops the process.
(For example, the process starting with $THT$ would be
$THT \to HHT \to HTT \to TTT$, which takes three steps.)

Prove the process will always terminate, and determine the average number of steps
this takes over all $2^n$ configurations.

Solution: The answer is \[ E_n = \half (1 + \dots + n) = \frac14 n(n+1) \]
which is finite.

We'll represent the operation by a
directed graph $G_n$ on vertices $\{0,1\}^n$
(each string points to its successor)
with $1$ corresponding to heads and $0$ corresponding to tails.
For $b \in \{0,1\}$ we let $\ol b = 1-b$,
and denote binary strings as a sequence of $n$ symbols.

The main claim is that $G_n$
can be described explicitly in terms of $G_{n-1}$:
\begin{itemize}
  \ii We take two copies $X$ and $Y$ of $G_{n-1}$.

  \ii In $X$, we take each string of length $n-1$
  and just append a $0$ to it.  In symbols,
  we replace $s_1 \dots s_{n-1} \mapsto s_1 \dots s_{n-1} 0$.

  \ii In $Y$, we toggle every bit, then reverse the order,
  and then append a $1$ to it.
  In symbols, we replace
  $s_1 \dots s_{n-1} \mapsto \ol s_{n-1} \ol s_{n-2} \dots \ol s_{1} 1$.

  \ii Finally, we add one new edge from $Y$ to $X$ by
  $11 \dots 1 \to 11\dots110$.
\end{itemize}
An illustration of $G_4$ is given below.
\begin{center}
\begin{asy}
unitsize(0.8cm);

label("$0000$", (0, 0), red);
label("$1000$", (0, 1), red);
label("$1100$", (0, 2), red);
label("$1110$", (0, 3), red);
label("$0100$", (2, 2), red);
label("$1010$", (2, 3), red);
label("$0010$", (4, 3), red);
label("$0110$", (6, 3), red);

label("$1111$", (0, 4), blue);
label("$1101$", (0, 5), blue);
label("$1001$", (0, 6), blue);
label("$0001$", (0, 7), blue);
label("$1011$", (2, 6), blue);
label("$0101$", (2, 7), blue);
label("$0111$", (4, 7), blue);
label("$0011$", (6, 7), blue);

label(scale(1.5)*"$\downarrow$", (0, 0.5), red);
label(scale(1.5)*"$\downarrow$", (0, 1.5), red);
label(scale(1.5)*"$\downarrow$", (0, 2.5), red);
label(scale(1.2)*"$\leftarrow$", (1, 2), red);
label(scale(1.2)*"$\leftarrow$", (1, 3), red);
label(scale(1.2)*"$\leftarrow$", (3, 3), red);
label(scale(1.2)*"$\leftarrow$", (5, 3), red);

label(scale(1.5)*"$\downarrow$", (0, 4.5), blue);
label(scale(1.5)*"$\downarrow$", (0, 5.5), blue);
label(scale(1.5)*"$\downarrow$", (0, 6.5), blue);
label(scale(1.2)*"$\leftarrow$", (1, 6), blue);
label(scale(1.2)*"$\leftarrow$", (1, 7), blue);
label(scale(1.2)*"$\leftarrow$", (3, 7), blue);
label(scale(1.2)*"$\leftarrow$", (5, 7), blue);

label(scale(1.7)*"$\Downarrow$", (0, 3.5), deepgreen);
\end{asy}
\end{center}

To prove this claim, we need only show
the arrows of this directed graph remain valid.
The graph $X$ is correct as a subgraph of $G_n$,
since the extra $0$ makes no difference.
As for $Y$, note that if $s = s_1 \dots s_{n-1}$ had $k$ ones,
then the modified string has $(n-1-k)+1 = n-k$ ones, ergo
$\ol s_{n-1} \dots \ol s_1 1
\mapsto  \ol s_{n-1} \dots \ol s_{k+1} s_k \ol s_{k-1} \dots \ol s_1 1$
which is what we wanted.
Finally, the one edge from $Y$ to $X$ is obviously correct.

To finish, let $E_n$ denote the desired expected value.
Since $1 \dots 1$ takes $n$ steps to finish we have
\[ E_n = \half \left[ E_{n-1} + (E_{n-1}+n) \right] \]
based on cases on whether the chosen string is in $X$ or $Y$ or not.
By induction, we have $E_n = \half (1 + \dots + n) = \frac14 n(n+1)$,
as desired.

\begin{remark*}
  Actually, the following is true:
  if the indices of the $1$'s are $1 \le i_1 < \dots < i_\ell \le n$,
  then the number of operations required is
  \[ 2(i_1 + \dots + i_\ell) - \ell^2. \]
  This problem also has an interpretation as a Turing machine:
  the head starts at a position on the tape (the binary string).
  If it sees a $1$, it changes the cell to a $0$ and moves left;
  if it sees a $0$, it changes the cell to a $1$ and moves right.
\end{remark*}