Branching process survival probability

Question

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))$.

Thanks!

Answer 1

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}$.

Answer 2

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$.

Answer 3

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.