5
$\begingroup$

You have a four sided die numbered 1-4 and are playing a game. On the first round, you roll the die once. If you get a 1 you lose the die. If you get a 2 you keep the die. If you get a 3 or 4 you get another, identical die. On the second round you roll each die that you have, and the same thing happens with each die. Once you finish rolling all your dice you move on to the third round and so on. If you have zero dice you lose the game. What is the probability that you never lose the game over infinite rounds?

$\endgroup$
6
$\begingroup$

This is a classic example of a branching process. As other answers have pointed out, the extinction prob $p = Prob(lose) = 1$ or $1/2$. To pick the correct answer, the linked wikipedia article has this to say:

it can be shown that starting with one individual in generation zero, the expected size of generation $n$ equals $\mu^n$ where $\mu$ is the expected number of children of each individual. If $\mu < 1$, then the expected number of individuals goes rapidly to zero, which implies ultimate extinction with probability $1$ by Markov's inequality. Alternatively, if $\mu > 1$, then the probability of ultimate extinction is less than $1$.

In the OP example, $\mu = (0 + 1 + 2 + 2) / 4 = 5/4 > 1$, so if you believe the wikipedia article, then $p < 1$. So the right answer is:

$$p = \frac12$$

Disclaimer: I personally don't know enough about branching processes to verify what wikipedia said. The article has some more details (in addition to what's quoted above) but I haven't read it in detail.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I’ve already used up all my votes for the next 1:30, but this gets mine afterwards, for actually completing the problem. $\endgroup$ – URL Dec 26 '19 at 22:35
  • 1
    $\begingroup$ @URL - thanks. it is nevertheless interesting to see others attempt it without knowing about branching processes. i especially like Matthew Daly's intuitive explanation for rejecting $p=1$ because "it always shows up". $\endgroup$ – antkam Dec 26 '19 at 22:50
5
$\begingroup$

Let $p$ be the probability of losing a die and all its "spawns" (the dice you got with it by rolling $3$ or $4$ and their spawns and so on). So we have

$$ p = \frac{1}{4} + \frac{1}{4} p + \frac{1}{2}p^2$$

This comes from the following reasoning: You can either lose the die immediately or keep the situation as is (you have the same $p$) or then you get a spawn and have to get rid of that too (hence the $p^2$).

Solving gives $p=\frac{1}{2}$ or $p=1$. Which one should we choose?

EDIT Other solutions have given resources for choosing the correct value, but for completion's sake I'll add some reasoning to my answer (also since I've learned something new myself and to reinforce it for my self :D).

I'll prove we should choose the smaller of the solutions (so in this case $p = \frac{1}{2}$).

Define

$X_n = $ "The number of dice we have after round $n$"

$A_n = \{X_n = 0\} =$ "We have lost all dice after round $n$"

$p_n = \mathbb{P}(A_n)$

We have $A_{n+1} \subset A_n$, so $p=\lim_{n\to\infty} p_n$.

Then define

$$f(x) = \frac{1}{4} + \frac{1}{4}x + \frac{1}{2}x^2.$$

Lemma 1

$$p_{n} = f(p_{n-1}).$$

Proof of Lemma 1: Notice that $f$ is the probability generating function (pgf) of $X_1$ and let's define $f_n$ to be the pgf of $X_n$. Then we have

$$f_n = f \circ f_{n-1}$$

This comes from the fact that if we have $k$ dice, they each "transform as" $f(x)$ and are independent so they produce a term $f(x)^k$ . So it goes like that: we keep composing f with itself. Now, lemma 1 follows easily, since $p_n = f_n(0)$. $$\tag*{$\blacksquare$}$$

Let $t$ be the smallest value on $[0,1]$ for which we have $t=f(t)$ (so $t=\frac{1}{2}$ in this case, but let's do this a bit more generally). Now, if we prove $p_n \leq t$ for all $n$ we are done, since $p$ is their limit. Let's do this inductively. The base case: $p_0=0 \leq t$. Inductive step: assume $p_n \leq t$. Since $f$ is increasing on $[0, 1]$,

$$p_{n+1} = f(p_n) \leq f(t) = t$$

and this finishes the proof.

Notice also, that $f'(1) = \mathbb{E}(X_1)$ is the slope of $f$ at $1$ and since $f'' \geq 0$, $f$ is convex so whether $\mathbb{E}(X_1)$ is bigger than $1$ or not decides whether the smallest solution will be $<1$ or $=1$. Because $f$ is a pgf, $f(1) = 1$ so $1$ will be the "default" solution if there arent' any smaller ones.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ I think that choosing between $p=\frac12$ and $p=1$ is non-trivial. My intuition certainly doesn’t discard either option. $\endgroup$ – URL Dec 26 '19 at 21:50
  • $\begingroup$ @URL Yes definitely, that was an honest question :D. I added reasoning for why we should always choose the smallest solution on $[0, 1]$. The final note shows how this agrees with the criterion of antkam's answer. $\endgroup$ – minkbag Dec 27 '19 at 15:52
4
$\begingroup$

Let $p$ be the probability that you eventually lose starting from one die. The key idea is that, since throwing each die is independent, the probability of eventually losing when you hold $n$ dice is $p^n$. Therefore, by the rule of the game, $$p=\frac14+\frac14p+\frac12p^2\\2p^2-3p+1=0$$

So this gives us $p=0.5$ or $p=1$. Looking at this problem with other rules I'm inclined to reject $p=1$, as it always turns up, so I will say there is a 50% chance of eventually losing.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Although not rigorous, your intuition that $p=1$ should be rejected coz "it always turns up" is good! I think it is justified by some comments in the wikipedia article on branching process (in the derivation section on extinction prob). In any case you certainly picked the right answer. See my answer for the link and why your choice is correct. $\endgroup$ – antkam Dec 26 '19 at 22:36
-1
$\begingroup$

there's always the chance that with n dice you will roll all of them and get 1's, it's just a really small probability but it might happen. Generally on each round you are expected to increase the number of dice you have by 25%.

EDIT: To answer the question more specifically, with n dice your chance of losing is $\frac1{4^n}$. With each round the expected increase of amount of dice you have is 25%, so over infinite rounds you will expect to have $n\to \infty$ which means $\frac1{4^n}\to0$

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ This doesn’t answer the question. $\endgroup$ – URL Dec 26 '19 at 21:14
  • $\begingroup$ @URL here, I added an explanation for why the probability to lose will get very small. $\endgroup$ – aradarbel10 Dec 26 '19 at 21:21
  • 1
    $\begingroup$ This is a better answer, but I’m still not sure that it is complete. Yes, the further the game goes on, the more unlikely one is to lose. But the overall probability isn’t zero. There’s at least a $\frac14$ probability of losing, if you roll $1$ on the first turn. $\endgroup$ – URL Dec 26 '19 at 21:23
  • 1
    $\begingroup$ So you are concluding that there is no chance the player will ever lose the game, is this right? Did you notice that this contradicts other answers? If so, then why is your answer correct? Just to give you a hint: there are other ways to lose apart from losing all your dice in one round $\endgroup$ – Thanassis Dec 27 '19 at 0:01

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