Counting Catalan: An Experimental Evaluation of the Mixing Time for the Triangulation Markov Chain

Monte Carlo Markov chains (MCMCs) are used in many areas as a way to model a system’s behavior. By running a probabilistic simulation on a system’s state space, we can estimate properties of the system that could be untenable to directly compute. It is of interest to determine how quickly a Markov chain mixes\textemdash that is, settles into its stationary distribution. One such chain is induced by taking a binary search tree and performing a rotation or flip on one of its edges. We know that this chain eventually settles into the uniform distribution, but the time complexity bounds on the number of steps it takes to do so are not tight. We showcase an MCMC experiment suggesting that the true mixing time is likely higher than $\Omega(n^{\frac{3}{2}})$, the known lower bound. We also discuss choosing heuristics to approximate the total variation distance from the uniform distribution when a direct calculation is computationally infeasible\textemdash this calculation takes time proportional to the size of the state space, which for the binary tree chain is $\Theta\left(\frac{1}{n^{\frac{3}{2}}}4^n\right)$. Additionally, we discuss scaling the MCMC simulation as a whole to accommodate large state spaces. These findings serve to guide future studies on the direction of theoretical research on mixing times, as well as providing a framework for similar MCMC experiments.