# Markov chains: Hitting time of random walk on Sierpinski triangle

Given a Sierpinski triangle $$G_n$$ and a random walk on $$G_n$$ denoted as $$(X_i)_{i\in\mathbb{N}}$$, I'm attempting to prove that the hitting time $$T_n$$ to go from one corner to any of the other two corners has expectation $$\mathbb{E}(T_n)=5^n$$.

My consideration is that $$G_n$$ is an irreducible and consequently positive recurrent Markov chain, but I'm not exactly sure how to use that information to my advantage. Is the correct approach this problem, or am I completely off from the start? Surely there's some symmetry consideration I'm missing? Is there some induction rule I should be thinking of as well?

• Can you describe the construction of $G_n$ and the nature of the random walk in a little more detail? I take it $G_0$ is supposed to be the clique on $3$ vertices, $G_{n+1}$ is constructed by linking three identical copies of $G_n$ at their corners by a single edge, and the random walk takes $1$ step along any edge from the current vertex, selected uniformly at random? Sep 2, 2023 at 1:33
• @IceTea I've written an extensive comment as an answer (to be deleted once it is resolved). To concisely ask the same question: I think it unambiguous that $G_0$ should have 3 vectices/states. How many vertices/states are there in $G_1$? Is it 6 or 9? Sep 5, 2023 at 22:54

This was an exam question for me!

The idea is to use the strong Markov property in a clever manner: Observe that $$G_n$$ is basically $$G_1$$ embedded inside every upward-oriented triangle in $$G_{n-1}$$. Hence, each traversal in $$G_{n-1}$$ to an adjacent corner corresponds to a traversal in $$G_n$$ between the two nodes with expected time $$5$$ instead (The $$5$$ comes from the expected hitting time on $$G_1$$). Note that the embedding being every upward-oriented triangle is important becomes there's only one $$G_1$$ copy which you can use between the two adjacent nodes. Can you fully rigorise and complete the argument from here using the strong Markov property?

This should be a comment, but they don't support the formatting I need to convey my point. I'll delete this not-really-an-answer-but-rather-a-comment after the issue is clarified.

The comment by @RiversMcForge seems to construct $$G_{n+1}$$ from $$G_n$$ by sticking an edge in between copies of $$G_n$$, as in

      A
/n\
B - C
/     \
D       E
/n\     /n\
F - G - H - J


as opposed to

    A
/n\
B - C
/n\ /n\
D - E - F


as I assume it's intended. In order to get an simple exponential in $$n$$ as the expectation, the latter form is much more plausible to me, but your response to that comment makes it sound like you want the former.

In both diagrams, I've denoted a copy of $$G_n$$ as

  X
/n\
Y - Z


where $$X,Y,Z$$ denote the corner vertices in the graph.

To provide more evidence, we can evaluate $$E(T_1)$$ directly using both constructions. In the latter construction, $$E(T_1) = 5$$, and in the former construction, $$E(T_1) = \frac{32}3$$ (assuming I made no mistake)

• Indeed it should be the latter interpretation (I had interpreted Rivers' comment that way to be honest, that's my bad)! Sep 6, 2023 at 21:15
• Perhaps worth noting: the first object described is an approximation of (or an iterate on the road to) the "Hanoi attractor". Sep 6, 2023 at 21:43