Past exam of the mathematics course of the University of Cambridge / 2022 / ib / Paper 1 / 19H (Markov Chains)

Let $D,E,F$ be the midpoints of $AB,AC,BC$. WriteFirst-step analysis for the simple random walk givesbecause $A$ has neighbours $D,E$;because $D$ has neighbours $A,B,E,F$; andbecause $F$ has neighbours $B,C,D,E$. Solving,

View each of the three level-one triangles in $G_2$ as a copy of $G_1$. Observe the walk only when it moves from one corner of such a copy to a different corner. By symmetry, the next of the two other corners is equally likely, so this embedded chain is the simple random walk on the coarse graph $G_1$. Part (a) says it makes an expected five coarse transitions before reaching $B$ or $C$.

Within each level-one copy, the mean time for one coarse transition is again five by part (a). The Strong Markov property at successive coarse-corner hitting times therefore gives

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