All men must die

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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s