5
$\begingroup$

Consider a Markov chain on a state-space which is slightly weird: It is the space of all tilings of a hexagon as shown in the left-hand side of the figure below with three types of rhombi: yellow, purple and cyan(a tiling means we cover the hexagon exactly with no empty space). The Markov chain picks one hexagon consisting of all three types of rhombi uniformly at random and flips it as is shown in the right-hand side of the figure. This is a finite-state Markov chain.

Show that this Markov chain is irreducible.

enter image description here

The question does not ask for precise mathematical expression.

My idea: W.L.O.G. the original tilings of a hexagon have three cases denoted by $\{1, 2, 3\}$ which the probability of each one is $1/3$. Then after flipping each one, we get three new tilings denoted by $4, 5, 6$ where state $4$ got from flipping the state $1$ and $5$ got from $2$, $3$ got from $6$. So there are two elements of the state space is $\{1, 2, 3, 4, 5, 6\}$.

It is clear that state $1, 4$ communicate each other by flipping the state $1$ or $4$. Similar with $2, 5$ and $3, 6$. But how to get the $2$ from the other states except for $5$

Is there any idea? Thanks!

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ Why, Love, did you edit out all the information needed to understand your question? I have rolled back to the original version. $\endgroup$
    – Gerry Myerson
    Oct 9, 2019 at 22:16
  • 1
    $\begingroup$ Your latest batch of edits have rendered the question once again incomprehensible. I am rolling back to Version 1 $\endgroup$
    – Yemon Choi
    Oct 18, 2019 at 22:05
  • $\begingroup$ The original formulation seems to indicate this is an exercise: would you care to tell us where this question comes from? $\endgroup$
    – Yemon Choi
    Oct 18, 2019 at 22:07
  • 1
    $\begingroup$ Please reread your question as stated and notice that it does not make sense, because you have removed the information needed to describe the situation which you want to solve. If you keep removing this information then this amounts to vandalism of your own post $\endgroup$
    – Yemon Choi
    Oct 19, 2019 at 3:39
  • 1
    $\begingroup$ The fact that you are deliberately deleting specific words from the title of your question gives the strong impression that you are seeking to hide something from searches, or acting in poor faith. Please explain why you insist on editing your question in this way $\endgroup$
    – Yemon Choi
    Oct 19, 2019 at 3:40

1 Answer 1

Reset to default
6
$\begingroup$

Suppose the sidelengths of your hexagon are $k, \ell, m$. A standard way of looking at this is to turn the picture by 30 degrees to the left and to view the yellow / cyan tiles as $m$ functions $f_i \colon \{1,\ldots,k+\ell\}$ into $\mathbb{Z}$ with the following constraints: $f_i(1) = i$, $f_i(k+\ell) = i-k+\ell$, $f_{i+1}(n) \ge f_i(n)+1$ and $f_i(n+1)-f_i(n) \in \{\pm 1\}$. The Markov chain then boils down to choosing $i$, $n$ and $\delta \in \{\pm 2\}$ at random and to change $f_i(n)$ into $f_i(n) + \delta$ whenever this can be done without breaking the above constraints. In other words, it turns local maxima of the $f_i$ into local minima and vice-versa, as long as this can be done by preserving the order between the functions.

It is now easy to see that the minimal element of this state space can be reached from every starting point: first turn local maxima of $f_1$ into local minima until you've reached the minimal configuration for $f_1$, then do the same for $f_2$, etc.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ @LoveGQY More or less. A natural height function $h(n,m)$ would rather be $h(n,m) = \sup\{i\,:\, f_i(n) \le m\}$ with the convention that it is $0$ if the set is empty, so the $f_i$ are the level lines of $h$. $\endgroup$
    – Martin Hairer
    Oct 5, 2019 at 9:39
  • $\begingroup$ Thanks a lot. I see. $\endgroup$
    – user102900
    Oct 9, 2019 at 18:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.