Empirical Support for Algorithmic Conjectures

Our project focuses on a particular Markov Chain Monte Carlo algorithm, with applications in statistical physics, known as hardcore model Glauber dynamics. The target distribution of Glauber dynamics is a distribution of all of the independent sets within a graph. An independent set is a set of vertices within a graph with no two vertices in the set containing an edge between them. Our goal is to find whether or not the Glauber dynamics for sampling independent sets on trees mixes in time O(nlogn), and determining how the mixing time changes if we bias the algorithm in favor of larger or smaller sets. We did this by writing C++ code that approximately counts the number of independent sets in random trees of size n. This approximation is done by taking many samples using Glauber dynamics. We then compared the approximation against an exact dynamic programming algorithm to see how accurate it was, and repeated for different parameter values for Glauber dynamics. We used these different parameter values to get an idea of the mixing time of Glauber dynamics.