{"id":{"repo_id":"calpoly","oai_identifier":"oai:digitalcommons.calpoly.edu:theses-4595"},"canonical_url":"https://search.ndltd.org/etd/calpoly/oai:digitalcommons.calpoly.edu:theses-4595","repository":{"repo_id":"calpoly","name":"Cal Poly","base_url":"https://digitalcommons.calpoly.edu/do/oai/"},"display":{"title":"Counting Catalan: An Experimental Evaluation of the Mixing Time for the Triangulation Markov Chain","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}}}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.","abstract_html":"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 <span class=\"etd-inline-math\">\\Omega(n<sup>\\frac{3}{2}</sup>)</span>, 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 <span class=\"etd-inline-math\">\\Theta\\left(\\frac{1}{n<sup>\\frac{3}{2}</sup>}4<sup>n</sup>\\right)</span>. 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.","abstract_has_math":true,"creators":["Gotlieb, Roy"],"institution":null,"degree_name":"MS in Computer Science","degree_level":null,"degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Daniel Frishberg","Computer Science","College of Engineering"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":null,"date_issued":"","date_published":null,"updated_at":"2026-11-19T07:12:29Z","subjects":["Markov Chain","Mixing Time","Triangulation","Binary Tree","Catalan Structure","Experimental Heuristic","Theory and Algorithms"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[],"person_identifier_entries":[]},"links":{"outbound_url":"https://digitalcommons.calpoly.edu/theses/2933","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://digitalcommons.calpoly.edu/theses/2933","record_label":"Repository record","record_kind":"record","record_source":"dc:identifier","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://digitalcommons.calpoly.edu/do/oai/?verb=GetRecord&metadataPrefix=oai_etdms&identifier=oai%3Adigitalcommons.calpoly.edu%3Atheses-4595","prefix":"oai_etdms"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Daniel Frishberg","Computer Science","College of Engineering"]},{"key":"dc:creator","label":"Author","values":["Gotlieb, Roy"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.available","label":"Dc Date Available","values":["2024-12-05T08:00:00Z"]},{"key":"dc:date.created","label":"Dc Date Created","values":["2024-12-01T08:00:00Z"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_name","label":"Degree Name","values":["MS in Computer Science"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Markov Chain","Mixing Time","Triangulation","Binary Tree","Catalan Structure","Experimental Heuristic","Theory and Algorithms"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://digitalcommons.calpoly.edu/theses/2933"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:title","label":"Title","values":["Counting Catalan: An Experimental Evaluation of the Mixing Time for the Triangulation Markov Chain"]}]}],"canonical_facts":{"dc:contributor":["Daniel Frishberg","Computer Science","College of Engineering"],"dc:creator":["Gotlieb, Roy"],"dc:date.available":["2024-12-05T08:00:00Z"],"dc:date.created":["2024-12-01T08:00:00Z"],"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}}}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."],"dc:identifier":["https://digitalcommons.calpoly.edu/theses/2933"],"dc:subject":["Markov Chain","Mixing Time","Triangulation","Binary Tree","Catalan Structure","Experimental Heuristic","Theory and Algorithms"],"dc:title":["Counting Catalan: An Experimental Evaluation of the Mixing Time for the Triangulation Markov Chain"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_name":["MS in Computer Science"]},"updated_at":"2026-11-19T07:12:29Z"}