Mixing time refers to the rate at which a discrete time Markov chain converges to a fixed stationary distribution from an initial probability distribution over its state space. Finding a Markov chain that mixes quickly to a given distribution is of great importance in Markov chain Monte Carlo algorithms which are used to efficiently sample large sets of data in order to get numerical results. On a connected graph, the fastest convergence can be obtained through convex optimization, as shown in the paper Fastest Mixing Markov Chain on a Graph by Boyd, Diaconis, and Xiao. However, their results apply only to a symmetric random walk on a connected graph, which satisfies the reversibility criterion with respect to its stationary distribution, and thus the transition matrix defining the Markov chain is symmetric and optimization constraints can be put on its spectral gap.  

 

In the case where such the Markov chain is not restricted to be a symmetric random walk, such analysis of the spectral gap is not possible and other methods need to be considered. The present research looks at both reversible and non-reversible Markov chains in order to find algorithms that define heuristically good, or potentially, optimally mixing non-reversible Markov chains chains.