Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

A colony begins with a cell, which can die, do nothing, transform to two or three cells, with probability 1/4 for each case at next time point. Children cells share the same property described above. What's the probability of this colony's extinction?

I got two solutions, $1$ and $\sqrt{2}-1$, from a simple recursive equation, $p=\frac{1}{4}(1+p+p^2+p^3)$. But I've no idea which one is correct. Thanks for your help!

share|cite|improve this question
It's certainly not 1, as it guarantees extinction, which is possible iff the probability to die is greater than $\frac{1}{2}$ – Alex Jul 20 '13 at 15:06
I forget how to prove it, but the probability of extinction is $<1$ if the expected number of offspring is $>1$. – Chris Eagle Jul 20 '13 at 18:49
up vote 5 down vote accepted

You've done most of the work; what remains is to decide whether $1$ or $\sqrt2-1$ is the probability of eventual extinction. For that purpose, let $x_n$ be the probability of the event that the population goes extinct at or before the $n$-th time step. Notice that these events form an increasing sequence with respect to $\subseteq$, so the probability of their union, the event of eventual extinction, is the supremum (and also the limit) of the increasing sequence of numbers $x_n$. The issue is therefore whether this sequence ever gets above $\sqrt2-1$.

We have $x_0=0$ (since the population is initially a single cell, not extinct), and $$ x_{n+1}=\frac14(1+x_n+{x_n}^2+{x_n}^3) $$ (because of the rules for how the cells multiply or die or do nothing). Notice that this equation says $x_{n+1}=f(x_n)$, where $f(x)=\frac14(1+x+x^2+x^3)$ is the function whose fixed points you already calculated. In particular, you know that $f(\sqrt2-1)=\sqrt2-1$. But $f(x)$ is clearly an increasing function of $x$ as long as $x\geq0$. So, since $x_0<\sqrt2-1$, we get, by induction on $n$, that $x_n<\sqrt2-1$ for all $n$. Therefore, the probability of eventual extinction is not $1$ but $\sqrt2-1$.

share|cite|improve this answer
can you explain why the sign of $x_n$ is a plus and not a minus? – al-Hwarizmi Jul 20 '13 at 20:26
+1 for this solution. – Did Jul 20 '13 at 21:05
@al-Hwarizmi If you mean the linear term $x_n$ in the formula for $x_{n+1}$, I can't imagine why you'd think there should be a minus sign. The probability that a cell does nothing (neither dies nor multiplies) is $1/4$, not $-1/4$. – Andreas Blass Jul 20 '13 at 21:08
Isnt this the death term that cant be from the same sign as the birth terms? I just cannot follow how you derived this equation? – al-Hwarizmi Jul 21 '13 at 8:56
@al-Hwarizmi No, the death term is the constant term 1. Each of the four possibiliites (death, remaining one cell, becoming 2 cells, and becoming 3 cells) has probability $1/4$. In the first of these 4 cases, the cell is dead, so the probability of extinction at or before $n+1$ is $1$. In the second case, it remains one cell, so the probability of extinction by $n+1$ equals the probability that the one cell existing after the first stage becomes extinct in at most $n$ additional stages, $x_n$. [continued in next comment] – Andreas Blass Jul 21 '13 at 15:25

I think I can shed some light on the recursion identity.

Let's call $p$ the probability that the population starting from one cell dies out. We have 4 scenarios:

1) The cell dies with probability $1/4$, hence extinction (term $1/4$).

2) It does nothing with the same probability, hence postponing the question (term $p/4$).

3) It spawns another cell, hence we study the extinction of two populations (term $p^2/4$)

4) It spawns two cells, hence we study the extinction of three populations (term $p^3/4$)

Thus, $$p=\frac 14 (1+p+p^2+p^3),$$ which gives us the roots $1$, $-1\pm \sqrt 2$.

Now we need to chose the correct root between $1$ and $\sqrt 2-1$. My intuition suggests that thanks to the expectation to generate half a cell on each step rules out the root $p=1$ (i.e. extinction almost surely), but I might be wrong. So my money is on $p=\sqrt 2-1$, and I would be glad if someone could give a formal proof of this result (or prove me wrong, of course).

share|cite|improve this answer
I am afraid, you have a time dependent process and not a stationary and will need to set up the master equations and regard the transition probabilities so the birth/death process. Then build the expectation values for the living cells a.s.f. – al-Hwarizmi Jul 20 '13 at 19:23
@al-Hwarizmi I don't see a time-dependent process here, I study only the probabilistic events (not even Markov's chains). If I want an estimation on the number of cells at a given time, then yes, I would need some other instruments. – TZakrevskiy Jul 20 '13 at 19:28
@al-Hwarizmi There're no steps, there're no functions of time. I have a random event with four outcomes, each of them is characterised by a certain quantative property. I calculate the expectation of that property given the probabilities of outcomes. – TZakrevskiy Jul 20 '13 at 19:54
@al-Hwarizmi I don't have generations/colonies/etc. I have one event with 4 outcomes. – TZakrevskiy Jul 20 '13 at 20:02
Yes. Your calculation is absolute fine. I am just considering how we can take it foward to an answer to the question. – al-Hwarizmi Jul 20 '13 at 20:15

I have translated this into a birt/death-process. Often one can set the master equations and derive the macroscopic relations from the microscopic. As there is no non-linearity (no liason of the cells) the rarction rates correspond to your probability of $1/4$ and we get

$$C \xrightarrow{k} D$$ $$C \xrightarrow{k} 2C$$ $$C \xrightarrow{k} 3C$$ $$C \xrightarrow{k} C$$

$$\frac{d C}{d t}=-k\,C+kC+k\,C+k\,C$$

$$\frac{d C}{d t}=2k\,C$$

Not sure if there is any threat to the colony to ever die out. $C$ in the equations represents the Expectation value (first moment) of the living cells over the population.

The above calculation holds if you start with a large population. If you start with one cell you will need to set up the master equations with the transition probailities and follow the progress of how your probability distribution changes over each time step. At the start it is $1/4$ then less and less. Larger the population gets less the probability that it dies out. Once large enough (law of large numbers) it will follow the above equations.

share|cite|improve this answer
The probability of extinction is very obviously at least $1/4$. – Chris Eagle Jul 20 '13 at 18:50
I have no idea what you're using the words "microscopic" and "macroscopic" to mean. – Chris Eagle Jul 20 '13 at 18:53
But this is false: there is probability $1/4$ that the initial cell dies immediately. – Chris Eagle Jul 20 '13 at 19:12
Have you read the question? We begin with ONE CELL. – Chris Eagle Jul 20 '13 at 19:22
No matter how cells you have at a given step, there's a non-zero probability that they all die, so your word "never" is out of place here. – TZakrevskiy Jul 20 '13 at 19:41

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.