Surprising appearance of triangular numbers during simple coin flip game

I have the following problem:

You have $$n$$ coins in a row in some beginning state of heads/tails. Define a process as follows: If you have $$k>0$$ heads, flip over the coin in the $$k$$th position from the left. If you have $$k=0$$ heads, stop. Otherwise repeat.

For example, for THT, the process goes THT $$\to$$ HHT $$\to$$ HTT $$\to$$ TTT

For fixed $$n$$, calculate the average number of steps it takes to terminate over all $$2^n$$ possible beginning states.

I saw the correct answer is

$$\frac{n^2+n}{4}$$

which is the $$n_{th}$$ triangular number divided by $$2$$. I'm not sure why this is the case. I assume this involves a recursive computation. I can see that for $$k$$ heads and $$n$$ total coins, you have a $$\frac{k}{n}$$ probability of flipping a head to a tail, which leaves you with $$k-1$$ heads. You could then solve for every value of $$k \leq n$$, and take the average. However this problem is deterministic and not probabilistic, so I don't think this approach is valid.

• Welcome to MathSE. This tutorial explains how to typeset mathematics on this site. Commented May 11, 2022 at 10:28

Let $$S_n$$ be a uniformly distributed random variable on the set of sequences of heads and tails of length $$n$$. Let $$R(s)$$ be the number of reductions required to get all tails on a sequence $$s$$. We have the equation $$\mathbb E [R(S_{n+1})]= \frac12 \mathbb E \left [R(S_{n+1})|S_{n+1} \textrm{ ends with heads}\right ]+\frac12 \mathbb E \left [R(S_{n+1})|S_{n+1} \textrm{ ends with tails}\right ]$$ First we note that $$\mathbb E \left [R(S_{n+1})|S_{n+1} \textrm{ ends with tails}\right ] = \mathbb E [R(S_{n})].$$ To see why this is true note let $$s$$ be a sequence of length $$n$$ and let $$sT$$ be that sequence with a tails on the end. To reduce $$sT$$ we add up all the heads in $$sT$$ and find that this is the number $$k$$ of heads in $$s$$(which must be $$\le n$$). Then we flip the kth element in $$sT$$. But this is just flipping the $$k$$th element in $$s$$ and keeping the tail on the end. Hence the amount of moves to reduce $$s$$ is the amount of moves to reduce $$sT$$
Next we will show that $$\mathbb E \left [R(S_{n+1})|S_{n+1} \textrm{ ends with heads}\right ] = \mathbb E [R(S_{n})]+n+1.$$ Let $$s$$ be a sequence of length $$n$$ and let $$t(s)$$ be the sequence that you get when you reverse $$s$$ and then flip every element. e.g $$t(HHHT) = HTTT$$. Now let $$s$$ be a sequence of length $$n$$ with reduction $$s'$$. Then $$t(s)H$$ is a sequence of $$n+1$$ ending in $$H$$. You can represent every sequence of length $$n+1$$ ending in heads this way because $$sH = t(t(s))H$$. Let there be $$k$$ heads in $$s$$. Then there are $$n-k$$ heads in $$t(s)$$ and $$n-k+1$$ heads (note that this is $$\le n$$) in $$t(s)H$$. To reduce $$t(s)H$$ we flip the $$n-k+1$$th element of $$t(s)H$$, which is the $$n-k+1$$th element of $$t(s)$$. Now we can flip the $$l$$th element in $$t(s)$$ by counting $$l$$ steps backwards in $$s$$ and flipping that element, i.e. flipping the $$n-l+k$$th element of $$s$$. So flipping the $$n-k+1$$th element in $$t(s)$$ is the same as flipping the $$k$$th element in $$s$$. Hence the reduction of $$t(s)H$$ is $$t(s')H$$.
This process works unless $$s$$ has no reduction in which case $$t(s)H$$ is $$HH \ldots H$$ which takes $$n+1$$ reductions to get to tails. Hence the amount or reductions required for $$t(s)H$$ is the amount of reductions required for $$s$$ plus $$n+1$$. Taking expectations gives the equation above.
Hence we have that $$\mathbb E \left [R(S_{n+1})\right] = \mathbb E [R(S_{n})]+\frac{n+1}{2}.$$ This combined with the easy ot verify fact that $$\mathbb E \left [R(S_{1})\right] = \frac12$$ gives the recurrence required to show that $$\mathbb E \left [R(S_{n})\right] = \frac{n(n+1)}{4}$$