Amoeba
Probability puzzles require you to weigh all the possibilities and pick the most likely outcome.
A jar begins with one amoeba. Every minute, every amoeba turns into 0, 1, 2, or 3 amoebas with a probability of 25% for each case (dies, does nothing, splits into 2, or splits into 3). What is the probability that the amoeba population eventually dies out?
Answer
If p is the probability that a single amoeba's descendants will die out eventually, the probability that N amoebas' descendants will all die out eventually must be p^N, since each amoeba is independent of every other amoeba. Also, the probability that a single amoeba's descendants will die out must be independent of time when averaged over all the possibilities. At t=0, the probability is p, at t=1 the probability is 0.25(p^0+p^1+p^2+p^3), and these probabilities must be equal. Extinction probability p is a root of f(p)=p. In this case, p = sqrt(2)-1.
The generating function for the sequence P(n,i), which gives the probability of i amoebas after n minutes, is f^n(x), where f^n(x) == f^(n-1) ( f(x) ), f^0(x) == x . That is, f^n is the nth composition of f with itself.
Then f^n(0) gives the probability of 0 amoebas after n minutes, since f^n(0) = P(n,0). We then note that:
f^(n+1)(x) = ( 1 + f^n(x) + (f^n(x))^2 + (f^n(x))^3 )/4
so that if f^(n+1)(0) -> f^n(0) we can solve the equation.
The generating function also gives an expression for the expectation value of the number of amoebas after n minutes. This is d/dx(f^n(x)) evaluated at x=1. Using the chain rule we get f'(f^(n-1)(x))*d/dx(f^(n-1)(x)) and since f'(1) = 1.5 and f(1) = 1, we see that the result is just 1.5^n, as might be expected.
Hide
