Question
Let T be a Galton-Watson tree with offspring distribution Poisson(2). Conditioned on non-extinction of the branching process, find the probability that the nearest-neighbor simple random walk on T is recurrent.
Step-by-step solution
Step 1. On the survival event, the Poisson(2) Galton-Watson tree is infinite and locally finite almost surely. So simple random walk on this random tree is well defined.
Step 2. A standard criterion for random walk on trees states: recurrence is equivalent to infinite effective resistance from the root to infinity, and transience is equivalent to finite effective resistance.
Step 3. For a supercritical Galton-Watson tree (mean offspring m > 1), one can construct a unit flow from the root to infinity with finite energy on the survival event. Equivalently, the effective conductance to infinity is positive, so the effective resistance is finite.
Step 4. Here m = 2 > 1. Therefore, conditioned on non-extinction, the random walk is transient almost surely. Hence the recurrence probability is 0.
Final answer
Answer: .
Marking scheme
Checkpoints (max 7 points)
- Model setup (2 pts): Correctly identify that conditioning on non-extinction yields an infinite locally finite Galton-Watson tree.
- Criterion statement (2 pts): State a correct recurrence/transience criterion on trees (effective resistance, conductance, or an equivalent theorem).
- Supercritical conclusion (2 pts): Use m = 2 > 1 to conclude transience on the survival event.
- Final answer (1 pt): State that the recurrence probability is exactly 0.
Common deductions
- No theorem or criterion, only intuition: at most 3 points.
- Correct criterion but no link to m = 2: deduct 2 points.
- Correct transience argument but missing final probability statement: deduct 1 point.