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.

  • 1
    $\begingroup$ 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. $\endgroup$ – 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.$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.