# 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?

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.

• I think they will reach $0$ with probability $1$, that is "almost always," but it is clearly conceivable that you toss nothing but heads, and so never get to $0$. This is a Markov chain with infinitely states. – saulspatz Jul 26 '19 at 13:25

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

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