2

Apparently this title "appears subjective", so I'll try to make it as objective as possible.

Suppose you have a fair 2-sided coin which, when flipped, yields Heads or Tails with 50% likelihood each. When you flip a coin and you get Tails, the coin disappears. When you get Heads, the coin turns into two identical coins that work as described above. You start with one coin, and if you ever run out of coins the game ends. As long as you have coins, you will keep perpetually flipping coins until you run out.

Obviously, there is always a chance the game will end, since you can always have a run of Tails and lose all your coins. However, as you get more and more coins, this probability diminishes. What is the probability that the game will end, starting with one coin?

I'm fairly certain the answer is 1, purely by the fact that the expected number of coins you gain each turn is 0. Intuitively, you are bound to have a stroke of bad luck at some point in the infinite span of the game, losing all your coins. I would be interested in seeing if this reasoning is valid.

Moreover, I'm interested to know: What would happen if Heads causes the coin to become three coins? In this scenario, you have an expected gain of 1 coin per flip. What's the probability you'll run out of coins? It's definitely greater than zero, but is it less than one?

Thanks for your help.

Johan
  • 261
  • https://en.wikipedia.org/wiki/Gambler's_ruin this is a relevant concept, although I'm not familiar with the math enough to provide a full answer on it. – kviiri Jan 19 '16 at 12:46
  • Related http://math.stackexchange.com/questions/349194/asymmetric-random-walk-with-unequal-step-size-other-than-1 – leonbloy Jan 19 '16 at 13:00
  • You're describing something an awful lot like a Galton-Watson process: https://en.wikipedia.org/wiki/Galton–Watson_process – Michael Lugo Jan 19 '16 at 13:19
  • Triplicate or duplicate ??? –  Jan 19 '16 at 13:31

2 Answers2

2

Note: at the start we'll assume that an answer exists, though this is not entirely evident. We'll end up showing existence. Note, too, that in what follows we compute the probability, $Q$, that the coin survives forever. The desired answer, of course, is $1-Q$.

To generalize a bit: let $p$ be the probability that the coin comes up $H$. (In the question as stated $p=.5$). Let $Q=Q(p)$ be the probability that you never run out of coins. Consider the first toss, if it comes up $T$ (probability $1-p$) the game is over. If it comes up $H$ then you get two coins and the probability that at least one "survives" forever is then $2Q-Q^2$. It follows that $$Q=p(2Q-Q^2)\implies Q\in\{0,2-\frac 1p\}$$

From this we see that, $p<.5\implies Q=0$ as the other option exceeds $1$.

Also, $p=.5\implies Q=0$ as both options are $0$.

the case $p>.5$ does in fact come out to the other option, $2-\frac 1p$ though this takes some effort to demonstrate: to see it Let $Q_n$ denote the probability that the coins survive at least to the $n^{th}$ toss. That always exists. Clearly this is a strongly decreasing function (i.e. $Q_n<Q_{n-1}$). Of course $Q_0=1$ and $Q_n>0\;\forall n$. It follows that the $Q_n$ approach some limit $L$. The same argument as above shows that $Q_n=p(2Q_{n-1}-Q_{n-1}^2$ (to survive to stage $n$ the coin must survive the first toss and then one, at least, of the two new coins must survive to toss $n-1$). From this we see that $L\in\{0,2-\frac 1p\}$. Dividing by $Q_{n-1}$ we see that $$\frac {Q_n}{Q_{n-1}}=p(2-Q_{n-1})$$ It follows that the ratio $\frac {Q_n}{Q_{n-1}}$ tends to a limit ($2p-pL$ to be precise). But if $p>.5$ this forces $L>0$ (else $2p-pL>1$ which is impossible, as $Q_n$ is decreasing). Note that this argument also proves the existence of $Q$.

If $H$ yields $3$ coins, the same procedure gives rise to the equation $$Q=p(3Q-3Q^2+Q^3)\implies Q\in \{0,\frac 32 - \frac {\sqrt{4p-3p^2}}{2p}\}$$ (thanks to commenter @leonbloy for catching an earlier computational error). In this case, some effort shows that you get the nonzero solution when $p>\frac 13$.

lulu
  • 70,402
  • (+1) For the last value, Maxima tells me $$Q=\frac{3}{2}-\frac{\sqrt{4 p-3 {{p}^{2}}}}{2 p}$$ (we agree with $p>1/3$). For the case of the problem ($p=1/2$) this gives a probability of survival $Q=0.381966$ – leonbloy Jan 19 '16 at 13:18
  • @leonbloy Yeah, I knew I was doing that too fast. Let me take a less hasty shot at it. Thanks! – lulu Jan 19 '16 at 13:22
  • @leonbloy You are correct. I will edit. Thanks again. – lulu Jan 19 '16 at 13:25
1

Suppose $p$ is the probability of running out of coins starting from one coin.

After you flip the first coin it either disappears or gives 3 coins and each one of the 3 will have the same probability $p$ to generate a sequence of coins that eventually will end up to $0$ coins, therefore you have the relation: $$ P(\text{end up with 0 coins starting with the first})=\frac 1 2 + \frac 1 2 P(\text{end up with 0 coins starting with each of the new 3 coins}) $$ that becomes: $$ p=\frac 1 2 + \frac 1 2 p^3 $$ and solving for $p$ we have $p=\frac {\sqrt{5}-1}2 \approx 0.61803$.

The same kind of argument with duplication would give $p=\frac 1 2 + \frac 1 2 p^2$ that implies $p=1$.

Marco Disce
  • 1,960