Solution: The Amoeba Problem

(The following is from rec.puzzles)

If p is the probability that a single amoeba's descendants will die out eventually, the probability that N amoebas' descendents will all die out eventually must be pN, 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(p0+p1+p2+p3), 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 fn(x), where fn(x) = fn-1( f(x) ), f0(x) = x . That is, fn is the nth composition of f with itself.

Then fn(0) gives the probability of 0 amoebas after n minutes, since fn(0) = P(n,0). We then note that:

fn(x) = ( 1 + fn(x) + (fn(x))2 + (fn(x))3 )/4

so that if fn+1(0) -> fn(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(fn(x)) evaluated at x=1. Using the chain rule we get f'(fn-1(x))* d/dx(fn-1(x)) and since f'(1) = 1.5 and f(1)=1, we see that the result is just 1.5n, as might be expected.

Back