Spectral gap and cut-off in Markov chains

In this paper we consider an example of a family of Markov chains with a spectral gap and show that it exhibits O(n) cut-off in the sense of Diaconis. We argue that this, and bandedness, is what lies at the heart of the O(n) phase transition in the k-SAT problem. 1 Introduction Consider a collection fA n g of n \Theta n, transition matrices corresponding to a family of Markov chains with n states, n = 1; : : :. Assume that each of these has a stationary distribution oe n (the eigenvector of A n corresponding to the eigenvalue 1). Let f(n) be an increasing function of n and, for an arbitrary vector n assume that the limit g(c) = lim n!1 k n A cf(n) \Gamma oe n k (1.1) exists for all c ? 0. If we have that g(c) = ae ff 6= 0 for c ! c 0 for c ? c , we say that the family of Markov chains has a cut-off of order f(n) with critical value c . For example, in riffle shuffling of cards [2, 3], in which case oe n [k] = 1=n, k = 1; : : : ; n, the cut-off is O(log n) with c = 3=2. F..