Back to search

Cal Poly

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

Abstract

dc:description.abstract

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}}4n\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.

Degree

thesis:*
Name thesis:degree_name
MS in Computer Science
Discipline thesis:degree_discipline
Computer Science

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Gotlieb, Roy
Contributors dc:contributor
  • Daniel Frishberg
  • Computer Science
  • College of Engineering

Subjects

dc:subject × 7

Identifiers

dc:identifier.*
Repository record dc:identifier
https://digitalcommons.calpoly.edu/theses/2933

Chain of custody

source
Harvested from
Cal Poly
Base URL
digitalcommons.calpoly.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Gotlieb, Roy. Counting Catalan: An Experimental Evaluation of the Mixing Time for the Triangulation Markov Chain. https://digitalcommons.calpoly.edu/theses/2933