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.