Amoeba Interview Question

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?

are we to suppose it does each of these with probability $1/4$? — shabbychef, Nov 21 '10 at 05:40
from a biological point of view, that chance is 1. The environment is bound to change to a point that no population can survive, given that in x billion years the sun is to explode. But I guess that's not really the answer he was looking for. ;-) The question doesn't make sense either. An amoebe can only divide into 2 or 0. Moral: traders shouldn't ask questions about biology. — Joris Meys, Nov 21 '10 at 12:34
Such a question on interview for a such position? Maybe it is something like http://dilbert.com/strips/comic/2003-11-27/ ? — , Nov 21 '10 at 14:02
This is a cute question as Mike mentions. The intuition here is that the eventual survival/extinction probability is the same between two generations. A more creative version could be thought of when the survival probability itself varies as a function of the number amoeba present. I've added it to my site blog. — broccoli, Aug 23 '12 at 02:33
@JorisMeys That's nonsense. Amoebas can evolve into advanced technology beings. — Fine-Tuning, Oct 05 '20 at 20:51
This problem is now in "A practical guide to quantitative finance interviews" — Fine-Tuning, Oct 05 '20 at 20:56

score 39 · Accepted Answer · edited Nov 21 '10 at 18:41

39

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?

edited Nov 21 '10 at 18:41

answered Nov 21 '10 at 11:47

Mike Anderson

1,537

3

The reason 1 is not a root is easily seen by considering the expected number of Amoeba after $k$ steps, call it $E_k$. One can easily show that $E_k = E_1^k$. Because the probability of each outcome is $1/4,$ we have $E_1 = 3/2$, and so $E_k$ grows without bound in $k$. This clearly does not gibe with $P = 1$. – shabbychef Nov 21 '10 at 18:03
12

@shabbychef It's not so obvious to me. You can have the expectation grow exponentially (or even faster) while the probability of dying out still approaches unity. (For example, consider a stochastic process in which the population either quadruples in each generation or dies out entirely, each with equal chances. The expectation at generation n is 2^n but the probability of extinction is 1.) Thus there is no inherent contradiction; your argument needs something additional. – whuber Nov 21 '10 at 21:02
1

@shabbychef -- thanks for the edit. I didn't realize we could use embedded TeX for math! @whuber -- shabbychef's statement $E_k = E_1^k$ is just a variation on my statement about the extinction probability, just add expectations instead of multiplying probabilities. Nice work, shab. – Mike Anderson Nov 21 '10 at 23:04
1

That's clear, Mike, but what's your point? Aren't we talking about how to rule out 1 as a solution? By the way, it's obvious (by inspection and/or by understanding the problem) that 1 will be a solution. This reduces it to a quadratic equation which one can easily solve on the spot. That's not usually the point of an interview question, though. The asker is probably probing to see what the applicant actively knows about stochastic processes, Brownian motion, the Ito calculus, etc., and how they go about solving problems, not whether they can solve this particular question. – whuber Nov 22 '10 at 15:18
5

@shabbychef: One way to rule out P=1 is to study the evolution of the probability generating function. The pgf is obtained by starting with t (representing an initial population of 1) and iteratively replacing t by (1+t+t^2+t^3)/4. For any starting value of t less than 1, a graphic easily shows the iterates converge to Sqrt(2)-1. In particular, the pgf is staying away from 1, showing it cannot converge to 1 everywhere, which would represent complete extinction. This is why "the 1 isn't plausible." – whuber Nov 22 '10 at 21:53
The answer that would not allow a $P=1$ solution to a more correct amoeba hypothesis is given here. It is arrived at with careful notation. – Carl Apr 11 '18 at 22:02

score 22 · Answer 2 · answered Nov 21 '10 at 11:48

22

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

answered Nov 21 '10 at 11:48

Emile

1,097

9

$\sqrt{2}-1$ is 0.4142, so it is in agreement with Mike's analytical result. And +1, because I like simulations ;-) – Nov 21 '10 at 14:04
2

Also +1 because I like simulations. Which would have been my answer ;). – Fomite Aug 23 '12 at 04:22

Sextus Empiricus · Answer 3 · 2020-10-05T21:42:31.727

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

+1 since this answer works to show that $p=1$ is not the right solution. Alternatively, I think that one can notice that the probability the population becomes extinct is that same as the probability that the associated random walk $S_n$ reaches $0$. $S_n$ goes from $i$ to $i-1$, remains in $i$, goes from $i$ to $i+1$ and from $i$ to $i+2$ all with probability $1/4$, and can be seen to be transient by comparing it to $Y_n:=\min{S_{T_n},Y_{n-1}+1}$ where $T_0:=0$, $T_n:=\inf{t>T_{n-1},|,S_t\neq S_{T_n}}$. Hence, the probability that it reaches $0$ when started from $1$ is less than $1$. — No-one, Aug 11 '23 at 17:01
($(Y_n)_{n\geq 0}$ is known to be transient because is a standard non-symmetrical random walk with probability of going from $i$ to $i+1$ equal to $2/3$ and of going from $i$ to $i-1$ equal to $1/3$.) — No-one, Aug 11 '23 at 17:09

shabbychef · Answer 4 · 2010-11-21T18:05:47.807

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.

Amoeba Interview Question

4 Answers4

Alternative derivation.

Convergence to the root and the relation with the expectation value

Linked

Related