6
$\begingroup$

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.

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

1 Answer 1

3
$\begingroup$

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}$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .