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. Thank you!

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$?
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.
Such a question on interview for a such position? Maybe it is something like dilbert.com/strips/comic/2003-11-27 ?
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.

mbq · Accepted Answer · 2010-11-21 18:41:24Z

up vote 19 down vote accepted

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

mbq♦
12.1k32166

answered Nov 21 '10 at 11:47

Mike Anderson
1,00733

1

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

3

@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

@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

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

2

@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

Emile · Answer 2 · 2010-11-21 11:48:51Z

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

$\sqrt{2}-1$ is 0.4142, so it is in agreement with Mike's analytical result. And +1, because I like simulations ;-)
Also +1 because I like simulations. Which would have been my answer ;).

shabbychef · Answer 3 · 2010-11-21 18:05:47Z

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.

asked	2 years ago
viewed	1892 times
active	9 months ago

Amoeba Interview Question

3 Answers

protected by whuber♦ Aug 23 '12 at 13:45

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

Related Jobs

Linked