Past exam of the mathematics course of the University of Cambridge / 2009 / ia / Paper 2 / 10F (Probability)

View the accessible rooms as the open cluster of bond percolation on a rooted ternary tree. Each accessible room has three forward corridors, independently open with probability $2/3$, so its number of accessible children has the binomial distribution $\mathrm{Bin}(3,2/3)$. The counts at successive levels form a binomial branching process with offspring probability generating functionLet $q_N$ be the probability that the root has no open path to level $N$. Then $q_0=0$, and independence of the three descendant subtrees givesThe sequence increases to the smallest fixed point $q=\varphi (q)$ in $[0,1]$, the branching extinction probability. Thus $q_N$ is close to that solution for large $N$.

Connectivity is the relevant escape event: if no window is reachable, escape is impossible; if one is reachable, ordinary random wandering reaches a window eventually with probability one. Before reaching level $N$ the guest moves within a finite connected graph, so an accessible exit cannot be avoided forever. This interpretation does not require the guest to move monotonically outward.

The Galton-Watson extinction fixed point equation isIts smallest root in $[0,1]$ is $q=(3\sqrt{3}-5)/4$, not the other allowed fixed point $1$. Consequently the large-depth escape probability isFor finite $N$, the exact escape probability is $1-q_N$ and is slightly larger. Indeed ${\varphi }^{\prime }(q)=2-\sqrt{3}<1$, and the mean value theorem on $[q_N,q]$ gives $0\le q-q_N\le q(2-\sqrt{3}{)}^N$. This also quantifies how quickly the finite-depth answer approaches the displayed limit.