MathOverflow is a question and answer site for professional mathematicians. 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

I have a time-inhomogeneous Galton-Watson binary branching process over a finite number of generations $n$. In each generation $i$, there is a probability $p_i$ of a child surviving; so each node has 2 children with probability $p_i^2$, 1 child with probability $2 p_i (1-p_i)$, and zero children with probability $(1-p_i)^2$. Furthermore $p_i$ is a decreasing function of $i$. So the process starts out as a super-critical branching and ends as a sub-critical branching.

I want to show that the process survives to time $n$ with probability say $\Omega(1)$ or $\Omega(1/\text{poly}(n))$. What is the easiest criterion to show this?

The process is inhomogeneous. The number of expected survivors at level $i$ is $\mu_i = 2^i p_1 \dots p_i$, which is a unimodular function of $i$. It seems that a sufficient criterion should be $\mu_n \geq 1$ or maybe $\mu_n = \Omega(\text{poly}(n))$.


share|cite|improve this question
When you say time-inhomogeneous, you mean homogenous over nodes at each time, but with a different offspring distribution for each time? Why not just apply the standard generating function method to get the generating function at the $n$th time? – Anthony Quas Feb 1 '12 at 3:50
PS: No bound on $\mu_i$ can ever suffice: you can always (inductively) make it so unlikely that there will be any offspring that even if the maximum number of offspring are born at all of the previous stages, the probability that any of them has any offspring at the current stage is ridiculously small (of course you pay for this by having zillions of babies if it ever does happen) – Anthony Quas Feb 1 '12 at 3:52
@Anthony Quas, note that the number of children is at most 2. So it seems like this situation that you describe should not be possible. – David Harris Feb 1 '12 at 17:55
up vote 2 down vote accepted

A new answer for the new version of the question.

Under the constraint that $p_i$ are decreasing and $\mu_n\ge 1$, the minimal survival probability is obtained when all $p_i=1/2$. You can see this by showing that for any level $j$, if you fix all the $p_i$ except for $p_j$ and $p_{j+1}$ then the minimum is obtained when $p_j=p_{j+1}$.

share|cite|improve this answer
Fantastic, thanks! – David Harris Feb 2 '12 at 23:01

I'm not a probabilist, but I took a course on this material recently and here's what I can tell you. Let $(Z_n)$ denote the branching process, i.e. $Z_0=1$ (root), and if $Z_n>0$ then $Z_{n+1} = \sum_{k=0}^{Z_n}{X_{n,k}}$ where each $X_{n,k}$ is distributed as $Z_1$ and $(X_{n,k})_{k=0}^\infty$ is an iid sequence independent of $(Z_1,\dots,Z_n)$. The children of the root are given by $Z_1$, and every node has children according to this process. We'll denote the probability of extinction by $\eta$

If $E(Z_1)<1$ then $\eta =1$

This would occur for example if the probability of zero children in your example is high, but the probability of 1 or 2 children is low. You certainly don't want to be in this situation. The proof is the Markov inequality and a simple observation: $P(Z_n\geq 1) \leq E(Z_n) = E(Z_1)^n$

If the $(X_{n,k})_{k=0}^\infty$ are independent then $E(Z_1)>1$ implies $\eta<1$ and $\eta$ is the smallest solution of the equation $\eta = \sum_{k=0}^\infty P(Z_1=k)\eta^k$.

The proof is just generating functions. Let $\eta_{n+1} = P(Z_{n+1}=0)$ be the probability that the process dies at level $n+1$. Then $\eta_{n+1} = G(\eta_n)$ where $G(s) = E(s^{Z_1}) = \sum_{k=0}^\infty s^k P(Z_1=k)$. Perhaps you can use this to get your desired bound on $1-\eta$.

share|cite|improve this answer
This is assuming that the child distributions are the same at all times. – David Harris Feb 2 '12 at 2:39
Aha, I see that you've edited your question. I think in the early version the fact that the offspring distributions change by generation was not clear. So I guess this answer won't be that helpful. Sorry! – David White Feb 2 '12 at 20:55

For the (time-homogenous) critical Galton-Watson tree, the survival probability is of order $1/n$. The argument goes through for time-inhomogenous as well, if you're willing to assume that all offspring distributions have expectation $\ge 1$ (and uniform bound on the number of possible offsprings).

A straightforward way of showing this is by induction. Write $q_n$ for the survival probability until time $n$. Then $$q_{n+1}=p_1 q_n + p_2 (2 q_n - q_n^2) \ ,$$ where $p_0,p_1,p_2$ is the offspring distribution at time 0. Let's assume that the expectation is exactly 1 (there's clearly monotonicity here), then $$q_{n+1}=q_n-p_2 q_n \ ,$$ and $p_2\le 1/2$.

Now it a matter of bounding the sequence $q_n$. It will be easier to work with $r_n=1/q_n$, and show that it is growing at most linearly. Then we get $$r_{n+1}=\frac{1}{\frac{1}{r_n}-\frac{p_2}{r_n^2}}=r_n+\frac{p_2}{1-\frac{p_2}{r_n}}$$ so as $r_n\to\infty$ we get that $0\le r_{n+1}-r_n\le p_2 + o(1)$ which is what we want.

EDIT: I see you have edited the question slightly and ask specifically about the case of percolation. In that case, if you assume that all $p_i\ge 1/2$ it is immediate that the survival probability is at least $c/n$ by monotonicity. My answer above is more general and can be easily extended for the case of arbitrary uniform bound on the number of offspring.

share|cite|improve this answer
As I have added a comment, you cannot assume any uniform bound on the $p_i$ probabilities -- they are decreasing as $p_i$ decreases. – David Harris Feb 2 '12 at 15:49
See my new answer. – Ori Gurel-Gurevich Feb 2 '12 at 22:44

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.