Given $n$ coins, adding 1 to $n$ per heads and subtracting 1 per tails when flipping all of them, will $n$ reach 0 and how many flips should it take?

Question

I came up with a problem a while ago stated:

"Given $n$ coins, each with an equal probability of landing on heads or tails when flipped, all coins are flipped simultaneously, and for every heads, a new coin is added, and for every tails, a coin is taken away. Will the amount of coins always reach $0$ in a finite amount of flips for any starting $n$, and if so, what is the expected amount of iterations to reach $0$ for any $n$?"

I have made some efforts to study this problem, but have never gotten far. What I do know is given $n_0$ coins to start and $h_0$ heads and $t_0$ tails when flipped the first time, the amount of coins after the flip, $n_1=(n_0-t_0)*2$, as $n_1=n_0+h_0-t_0$ and $h_0+t_0=n_0$ so $n_0-t_0=h_0$. Given any starting $n$ value, any even number $\geq0$ can be reached in an infinite number of different ways, but the sum of the probabilities of reaching any of them except maybe $0$ must be less than $1$. Additionally, after each iteration, whatever $n$ value is present can be effectively be considered the starting $n$ value, which, for greater $n$ which have a greater expected number of iterations to reach $0$, seems to indicate a divergence in the amount of iterations expected to reach $0$, possibly to the point of reaching $0$ being not guaranteed. However, since each $n$ value has an expected change of $0$ for a flip, it seems the distribution of $n$ values would be highly random, eventually guaranteeing $0$ being reached.

I am pretty confident the amount of coins will always reach $0$, but other details such as a proof for that, and how many expected iterations it would take to get there given any $n$ are beyond me. Any help would be greatly appreciated.

Answer 1

Here is an alternative representation.

You have a simple random walk where $X_{k+1}=X_k+1$ with probability $\frac12$ and $X_{k+1}=X_k-1$ with probability $\frac12$, starting with $X_0=n\gt 0$. It is well known that the probability of ever hitting $0$ is $1$ and the expected number of steps before first hitting $0$ is infinite.

Now consider $Y_k$ where $Y_0 =X_0$ and $Y_{k+1}=X_{\sum_0^k Y_k}$, so $Y_0=n$, $Y_1=X_n$, $Y_2=X_{n+X_n}$ etc.

$Y_k$ has exactly the same distribution as the coins in your question after $k$ steps, and so will eventually reach $0$ with probability $1$ as $X_j$ cannot reach $0$ for any $j$ unless $Y_k$ does so for some $k$ and vice versa. Similarly the expected number of steps to do so is infinite.

Note that because the coins are fair, for any $k$ you have $\mathbb E[X_k] = \mathbb E[Y_k] =n$

Answer 2

Let $p$ be the probability of a single coin getting "extinct". Then $p$ is $\frac12$ for the case of tosisng tails, plus $\frac12p^2$ for the case of tossing heads and thereby spawning two single coins with extinction probability $p$ each. So $$ p=\frac12+\frac 12p^2$$ and hence $$p=1.$$

If you start with $n$ coins instead, this is just the $n$-fold parallel execution of the single coin game.

---

Let $p_n$ be the proabability of extinction within at most $n$ rounds. Now we have $p_0=0$ and for $n>0$ $$p_n=\frac12+\frac12p_{n-1}^2.$$ With $q_n=1-p_n$, this becomes $$q_n=q_{n-1}\cdot\left(1-\frac12q_{n-1}\right). $$ The expected number of rounds until extinction is $$ E[X] = \sum_{n=1}^\infty n\cdot (p_n-p_{n-1})=\sum_{n=0}^\infty q_n $$ The contribution to this sum of all $q<\epsilon$ is at leat $\epsilon+\epsilon(1-\frac\epsilon2)+\epsilon(1-\frac\epsilon2)^2+\ldots = \epsilon\frac1{\frac\epsilon2}=2$. We conclude that the sum is not convergent, i.e., $$ E[X]=\infty.$$