Question:

One day, an alien comes to Earth. Every day, each alien does one of four things, each with equal probability to:

(i) Kill himself
(ii) Do nothing
(iii) Split himself into two aliens (while killing himself)
(iv) split himself into three aliens (while killing himself)

What is the probability that the alien species eventually dies out entirely?

.

.

C

A

P

T

A

I

N

I

N

T

E

R

V

I

E

W

.

.

Solution:

The answer is √2 – 1.

Suppose that the probability of aliens eventually dying out is x.

Then for n aliens, the probability of eventually dying out is xn because we consider every alien as a separate colony. Now, if we compare aliens before and after the first day, we get:

`x = (1 /4) * 1 + (1 /4) * x + (1 /4) * x² + (1 /4) * x³`

`x³ + x² − 3x + 1 = 0`

`(x − 1)(x 2 + 2x − 1) = 0`

We get,  `x = 1, −1 − √ 2`, or `− 1 + √ 2`

We claim that x cannot be 1, which would mean that all aliens eventually die out. The number of aliens in the colony is, on average, multiplied by 0+1+2+3 4 = 1.5 every minute, which means in general the aliens do not die out. (A more rigorous line of reasoning is included below.) Because x is not negative, the only valid solution is x = √ 2 − 1.

To show that x cannot be 1, we show that it is at most √ 2−1.

Let xn be the probability that a colony of one bacteria will die out after at most n minutes. Then, we get the relation:

`xn + 1 = 1/4 (1 + xn + x²n + x²n)`

We claim that xn ≤ √ 2 − 1 for all n, which we will prove using induction.

It is clear that x1 = 1 /4 ≤ √ 2 − 1. Now, assume xk ≤ √ 2 − 1 for some k. We have:

`xk+1 ≤ 1/4 (1 + xk + x²k + x³k )`

`≤ 1/4 ( 1 + (√ 2 − 1) + (√ 2 − 1)² + (√ 2 − 1)³ )`

`= √ 2 − 1`

which completes the proof that xn ≤ √ 2 − 1 for all n. Now, we note that as n becomes large, xnapproaches x. Using formal notation, this is:

`x = lim (n →∞) xn ≤ √ 2 − 1`, so x cannot be 1.