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

(Cross-posted to math stackexchange question 130154)

I am trying to analyze the following branching process. We start with a root (level 0) node. Each surviving node has two children, each of which may or may not survive. This branching process goes through $n$ levels, so there are $2^n$ leaf nodes. I want to estimate the probability that there is at least one surviving leaf node.

Furthermore, each node in the branching process carries some "information," which affects the survival probability and distribution of its children. The two children of a node (including their information and survival) are independently and identical distributed, given the information of the parent.

For each level $i = 0, \dots, n$ I have a lower bound $P_i$ on the probability that any given level-$i$ node survives. However, all of these events may be very dependent on each other. I also have a lower bound $Q$ on the probability that any given level-$i$ node survives to level $i+1$ (independent of any other events that may have occured).

In the regime $2^n P_n \ll 1$ one could hope to show that the probability that a leaf node survives is about $2^n P_n$. At the very least, I would like to show that the probability of survival is much more than $2^n Q^n$. This is what would occur if I had a uniform Galton-Watson process with probability $Q$ exactly.

Intuitively, the "clumpiest" possible distribution of probabilities would be if all the nodes at level $n$ had completely the same support. In other words, there is an initial probability of $P_n$ that all the leaves in the tree survive. But it seems that with appropriate values for $P_1, \dots, P_{n-1}$ and $Q$ one should be able to rule this out.

Thanks for any help

share|cite|improve this question
Referring to your last paragraph: it could be that the probability of all the nodes up to level $i$, and no node of higher level to survive is exactly $P_i$. So this would give only $P_n$, so a bound without using $Q$ is out of the question. A bound of $2^n Q^n$ is trivial by a coupling argument, if the probability to survive another level is "independent of any other events that may have occurred". – Ori Gurel-Gurevich Apr 10 '12 at 1:11
The above comment referred to a previous version of the last paragraph. – Ori Gurel-Gurevich Apr 10 '12 at 1:12

Your Answer


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

Browse other questions tagged or ask your own question.