Past exam of the mathematics course of the University of Cambridge / 2021 / iii / Paper 220 / 2 / c

Consider an occurrence counted by $G_m$. Before the next counted occurrence, the exploration must first take a downward step of the simple symmetric random walk, which has probability $1/2$, and then choose the decrement $-1$ among the three equally likely values of $\xi$, which has probability $1/3$. Thus it terminates the visits to the current record value with probabilityThe Strong Markov property at successive counted occurrences makes these trials independent. Therefore $G_m$ has the geometric distribution on $\{1,2,\dots \}$ with parameter $1/6$, andfor every $j\ge 1$.

In the standard labelled encoding of a pointed planar quadrangulation, incidences at the distinguished vertex are represented by visits counted by the record variables $G_m$. Consequently its degree of a vertex is bounded by the largest such count encountered before the coding walk first reaches $-1$.

Before time $2n+1$ there are at most $2n+1$ possible record levels. The union bound and part i therefore implyConditioning on $\sigma =2n+1$ and using the supplied lower bound givesSet $r=C\log n$. If $C>5/(2\log (6/5))$, the right-hand side tends to zero. Hence for some constant $C>0$,