Nayantara Bhatnagar, Sam Greenberg, Dana Randall
The Effect of Boundary Conditions on Mixing Rates of Markov Chains

Abstract: Many natural Markov chains undergo a phase transition as a temperature parameter is varied; a chain can be rapidly mixing (polynomial time) at high temperature and slowly mixing (exponential time) at low temperature. Moreover, it is believed that even at low temperature, the rate of convergence is strongly dependent on the environment in which the underlying system is placed.   It is believed that the boundary conditions of a spin system can determine whether a local Markov chain mixes quickly or slowly, but this has only been verified previously for models defined on trees. We demonstrate that the mixing time of Broder's Markov chain for sampling perfect and near-perfect matchings does have such a dependence on the environment when the underlying graph is the square-octagon lattice. We show the same effect occurs for a related chain on the space of Ising and ``near-Ising'' configurations on the two-dimensional Cartesian lattice.