I was talking with a friend about a problem in population sizes in a discrete setting:

Suppose you have colony of single-celled organisms. Every hour, on the hour, with probability $p$ each cell will split into two identical cells. No cell ever dies. How many cells will there be, on expectation, after $t$ time steps, assuming there is one initial cell at time $t = 0$?

We realized that we could formulate this problem by reasoning about a series of random variables $X_0, X_1, X_2, \dots$, where $X_k$ represents the number of live cells at time $t = k$. Formally, we'd define these variables inductively as

$$X_0 = 0$$ $$X_{k+1} - X_k \sim Binom(X_k, p)$$

We were specifically interested in the following questions. First, is there a simple closed-form for $\mathbb{E}[X_k]$? Second, is there is simple closed-form for $\mathbb{P}[X_k = n]$ for an arbitrary $\mathbb{N}$?

I don't have a background in stochastic processes, but I assume this is probably a well-known problem. I started by looking at Galton-Watson processes, which seemed similar, but that particular setup doesn't account for past generations (which never die off and can always continue reproducing) and most of what I read seemed to focus on extinction probabilities rather than estimates of the total population size. That linked me to look at more general branching processes, which similarly didn't account for the fact that any individual can reproduce and also seemed to focus on the extinction probability.

My initial guess is that we'd have $\mathbb{E}[X_k] = (1 + p)^k$, since each individual cell on expectation will be $1 + p$ cells in the next generation, but this assumes that every variable takes on precisely its expected value from generation to generation and therefore is probably not a mathematically sound line of reasoning. As for the probability that there are exactly $n$ cells alive after $k$ generations, I have no idea how to set that up, given that the number of living cells in each generation depends on the results of multiple binomial samplings, each of which has an $n$ that depends on the previous sampling.

I'm interested in both answers to my original question, but also information on the general family of techniques that I should probably look into to reason about processes like these in the future.


  • $\begingroup$ I think you mean $X_0=1$ and $X_{k+1}-X_k\sim\operatorname{Binom}(X_k,p)$? Your initial guess for the expectation is correct, due to the linearity of expectation. $\endgroup$ – joriki Mar 22 '16 at 17:46
  • $\begingroup$ @joriki Can you elaborate on how linearity of expectation applies here? If all I know about $X_k$ is its expected value, I'm not sure that I can conclude anything about $X_{k+1}$. $\endgroup$ – templatetypedef Mar 22 '16 at 18:54
  • $\begingroup$ It seems that your problem can be modeled by a branching process where each vertex has $2$ offspring with probability $p$ and $1$ offspring with with probability $1-p$. This way, $X_t$ is exactly your population size at each $t$. $\endgroup$ – Graffitics Mar 22 '16 at 19:34
  • $\begingroup$ @templatetypedef: Because taking the expectation is a linear operation, it doesn't matter whether you apply it in several steps or all in one go. Every end result is weighted by the product of the probabilities that led there, no matter how you build that product. If you multiply out $(1+p)^k$, you get $2^k$ terms that correspond one-to-one to potential genealogies of cells, and the factors of $p$ are precisely the ones that you'd get if you wrote down the expectation value without using the recurrence. Linearity simplifies things a lot :-) $\endgroup$ – joriki Mar 22 '16 at 19:51

Another take on linearity:

Prepare 2 buckets. At time $0$ put put the initial cell in the first bucket. At time $1$ if that cell had split, put the offspring into the second bucket. This will happen with a probability $p$.

Leave the system alone for $k-1$ hours.

After that time expired, the expected amount of cells in the first bucket is $E(k-1)$, and in second bucket is $pE(k-1)$, and the expected total is $E(k) = E(k-1) + pE(k-1) = (1+p)E(k-1)$. Solving a recurrence gives $E(k) = (1+p)^k$.

The key is that buckets evolve independently.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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