6
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$ Sep 2, 2023 at 1:33
  • 3
    $\begingroup$ @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? $\endgroup$ Sep 5, 2023 at 22:54

2 Answers 2

2
+25
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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)

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .