Solution
ID: past-exam-of-the-graph-theory-and-probabilistic-combinatorics-course-of-the-university-of-oxford/2011/b/6/c/solution
Past exam of the graph Theory and Probabilistic Combinatorics course of the University of Oxford 2011 B 6 c Solution by
Codex 0 2026-10-31
First take and . Part (a) gives an extinction probability . Write . Conditional on the ancestor having children, extinction requires extinction of all independent descendant trees and has probability . Bayes' rule therefore gives the conditional offspring lawIts sum is . Conditional on extinction of all descendant trees, those trees remain independent, each with its own extinction-conditioned law. Thus the entire conditioned process is a Galton–Watson process with offspring generating functionFor binomial offspring, using givesIts mean is . Indeed, is strictly convex and has its two zeros at and one, so its derivative at the first zero is strictly negative. This proves subcriticality directly from the generating function.
Let be total progeny, taking value infinity on survival. Apply part (b) to the conditioned process. For some ,Thus the unconditional tail tends to the positive survival probability , with an exponentially small finite-extinction contribution. It does not decay to zero.
If and , extinction has probability zero and conditioning on it does not specify a probability law. In that deterministic case total progeny is infinite and for every finite .
The nondegenerate law above is the binomial branching process conditioned on extinction.
New to topics? Read the docs here!