Markov chains: Hitting time of random walk on Sierpinski triangle

Question

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?

Answer 1

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)

Answer 2

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?