Amoeba Interview Question I was asked this question during an interview for a trading position with a proprietary trading firm. I would very much like to know the answer to this question and the intuition behind it.
Amoeba Question: 
A population of amoebas starts with 1. After 1 period that amoeba can divide into 1, 2, 3, or 0 (it can die) with equal probability. What is the probability that the entire population dies out eventually? 
 A: Like the answer from Mike Anderson says you can equate the probability for a lineage of an amoeba to become extinct to a sum of probabilities of the lineage of the children to become extinct.
$$p_{parent} = \frac{1}{4} p_{child}^3 + \frac{1}{4} p_{child}^2 + \frac{1}{4} p_{child} + \frac{1}{4}$$
Then when you set equal the parents and childs probability for their lineage to become extinct, then you get the equation:
$$p = \frac{1}{4} p^3 + \frac{1}{4} p^2 + \frac{1}{4} p + \frac{1}{4}$$
which has roots $p=1$, $p=\sqrt{2}-1$, and $p=-\sqrt{2}-1$.
The question that remains is why the answer should be $p=\sqrt{2}-1$ and not $p=1$. This is for instance asked in this duplicate Amoeba Interview Question: Is the P(N=0) 1 or 1/2? .
In the answer from shabbychef it is explained that one can look at, $E_k$, the expectation value of the size of the population after the $k$-th division, and see whether it is either shrinking or growing. To me, there is some indirectness in the argumentation behind that and it feels like it is not completely proven.

*

*For instance, in one of the comments, Whuber notes that you can have a growing expectation value $E_k$ and also have the probability for extinction in the $k$-th step approach 1. As an example, you could introduce a catastrophic event that wipes out the entire amoeba population and it occurs with some probability $x$ in each step. Then the amoeba lineage is almost certain to die. Yet, the expectation of the population size in step $k$ is growing.

*Furthermore, the answer leaves open what we have to think of the situation when $E_k = 1$ (e.g. when an amoeba splits or does not split with equal, 50%, probability, then the lineage of an amoeba becomes extinct with probability almost $1$ even though $E_k= 1$)


Alternative derivation.
Note that the solution $p=1$ can be a vacuous truth. We equate the probability for the parent's lineage to become extinct to the child's lineage to become extinct.

*

*If 'the probability for the child's lineage to become extinct is equal to $1$'.  Then 'the probability for the parent's lineage to become extinct is equal to $1$'.

But this does not mean that it is true that 'the probability for the child's lineage to become extinct is $1$'. This is especially clear when there would always be nonzero number of offspring. E.g. imagine the equation:
$$p = \frac{1}{3} p^3 + \frac{1}{3} p^2 + \frac{1}{3} p$$
Could we arrive at a solution in a slightly different way?
Let's call $p_k$ the probability for the lineage to get extinct before the $k$-th devision. Then we have:
$$p_1 = \frac{1}{4}$$
and the recurrence relation
$$p_{k+1} =  \frac{1}{4} p_{k}^3 + \frac{1}{4} p_k^2 + \frac{1}{4} p_k + p_1$$
or
$$\delta_k = p_{k+1} - p_k = \frac{1}{4} p_{k}^3 + \frac{1}{4} p_k^2 - \frac{3}{4} p_k + p_1 = f(p_k) $$
So wherever $f(p_k)>0$ the probability to get extinct before the $k$-th devision will increase with increasing $k$.

Convergence to the root and the relation with the expectation value
If the step is smaller than the distance to the root $f(p_k) <  p_{\infty}-p_k$ then this increase of the $p_k$ as $k$ grows will not surpass the point where $f(p_\infty) = 0$.
You could verify that this (not surpassing the root) is always the case when the slope/derivative of $f(p_k)$ is above or equal to $-1$, and this in it's turn is always the case for $0\leq p \leq 1$ and polynomials like $f(p) = -p + \sum_{k=0}^{\infty} a_k p^k$ with $a_k \geq 0$.
With the derivative $$f^\prime(p) = -1 + \sum_{k=1}^{\infty} a_k k p^{k-1}$$ being in the extreme points equal to $f^\prime(0) = -1$ and $f^\prime(1) = -1 + E_1$ you can see that there must be a minimum between $p=0$ and $p=1$ if $E_1>1$ (and related there must be a root between $0$ and $1$, thus no certain extinction). And opposite when $E_1 \leq 1$ there will be no root between $0$ and $1$, thus certain extinction (except the case when $f(p) = 0$ which occurs when $a_1 = 1$).
A: This sounds related to the Galton Watson process, originally formulated to study the survival of surnames. The probability depends on the expected number of sub-amoebas after a single division. In this case that expected number is $3/2,$ which is greater than the critical value of $1$, and thus the probability of extinction is less than $1$. 
By considering the expected number of amoeba after $k$ divisions, one can easily show that if the expected number after one division is less than $1$, the probability of extinction is $1$. The other half of the problem, I am not so sure about.
A: Cute problem. This is the kind of stuff that probabilists do in their heads for fun.
The technique is to assume that there is such a probability of extinction, call it $P$.  Then, looking at a one-deep decision tree for the possible outcomes we see--using the Law of Total Probability--that
$P=\frac{1}{4} + \frac{1}{4}P + \frac{1}{4}P^2 + \frac{1}{4}P^3$
assuming that, in the cases of 2 or 3 "offspring" their extinction probabilities are IID.  This equation has two feasible roots, $1$ and $\sqrt{2}-1$.  Someone smarter than me might be able to explain why the $1$ isn't plausible.
Jobs must be getting tight -- what kind of interviewer expects you to solve cubic equations in your head?
A: Some back of the envelope calculation (litterally - I had an envelope lying around on my desk) gives me a probability of 42/111 (38%) of never reaching a population of 3.
I ran a quick Python simulation, seeing how many populations had died off by 20 generations (at which point they usually either died out or are in the thousands), and got 4164 dead out of 10000 runs.
So the answer is 42%.
