Prateek Bhakta, CS (advisor: Dana Randall, CS) - Markov Chain Convergence in Discrete and Continuous Spaces

We use a simple markov chain that iteratively selects a pair of adjacent elements i < j, and puts them in sorted order with a given probability p[i,j] > 1/2, and in reverse order with probability 1 - p[i,j]. Despite the simplicity of the model, very little is known about the mixing rate of this chain outside of very specific special cases, and the general problem has been open for over 10 years. We conjecture that the mixing time for this chain is always polynomial in n. One promising approach is to bound the conductance of the markov chain for a general set of p[i,j] between values of the conductance for sets of p[i,j] with known polynomial mixing rates.