 # 393 probability/amoeba.p

## Description

This article is from the Puzzles FAQ, by Chris Cole chris@questrel.questrel.com and Matthew Daly mwdaly@pobox.com with numerous contributions by others.

# 393 probability/amoeba.p

A jar begins with one amoeba. Every minute, every amoeba
turns into 0, 1, 2, or 3 amoebae with probability 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?

probability/amoeba.s

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

Continue to: