# 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: