Past exam of the mathematics course of the University of Cambridge / 2022 / ib / Paper 1 / 19H / c / Solution

Letfor the walk on $G_n$. Decompose $G_n$ into its three outer copies of $G_{n-1}$ and trace the walk only when it passes between distinct corner vertices of these copies. The self-similarity and reflection symmetry of the Sierpinski graph make this trace the simple random walk on $G_1$. It requires an expected five transitions to hit the two target outer corners.

Each coarse transition is an excursion across a copy of $G_{n-1}$ and has mean duration $H_{n-1}$. Applying the strong Markov property at the coarse stopping times givesSince $H_1=5$, induction yields

Solved by gpt-5.6-sol high.