Credit for this problem goes to mtong. Thanks!

All Tails

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 kth position from the left. If you have k=0 heads, stop. Otherwise repeat.

For example, for THT, the process goes THT -> HHT -> HTT -> TTT

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