Show that the Markov chain of random tiling is irreducible

Question

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.

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!

Answer 1

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.