A generalized @math puzzle' consists of an @math numbered grid, with one missing number. A move in the game switches the position of the empty square with the position of one of its neighbors. We solve Diaconis' 15 puzzle problem' by proving that the asymptotic total variation mixing time of the board is at least order @math when the board is given periodic boundary conditions and when random moves are made. We demonstrate that for any @math with @math , the number of fixed points after @math moves converges to a Poisson distribution of parameter 1. The order of total variation mixing time for this convergence is @math without cut-off. We also prove an upper bound of order @math for the total variation mixing time.
 Let g, h be a random pair of generators of G=Sym(n) or G=Alt(n). We show that, with probability tending to 1 as n→∞, (a) the diameter of G with respect to S= g,h,g−1,h−1 is at most O(n2(log⁡n)c), and (b) the mixing time of G with respect to S is at most O(n3(log⁡n)c). (Both c and the implied constants are absolute.) These bounds are far lower than the strongest worst-case bounds known (in Helfgott–Seress, 2013); they roughly match the worst known examples. We also give an improved, though still non-constant, bound on the spectral gap. Our results rest on a combination of the algorithm in (Babai–Beals–Seress, 2004) and the fact that the action of a pair of random permutations is almost certain to act as an expander on l-tuples, where l is an arbitrary constant (, 1998). By symmetry, P has eigenvalues 1 = I03 > I381 > ?> I 31xI- 1 2 -1. This paper develops methods for getting upper and lower bounds on 8i3 by comparison with a second reversible chain on the same state space. This extends the ideas introduced in Diaconis and Saloff-Coste (1993), where random walks on finite groups were considered. The bounds involve geometric properties such as the diameter and covering number of an associated graph along the lines of Diaconis and Stroock (1991). The main application gives a sharp upper bound on the second eigenvalue of the symmetric exclusion process. Thus, let S0 be a connected undirected graph with n vertices. For simplicity, we assume in this introduction that SW is regular. To start, r unlabelled particles are placed in an initial configuration, 1 < r < n. At each step, a particle is chosen at random; then one of the neighboring sites of this particle is chosen at random. If the neighboring site is unoccupied, the chosen particle is moved there; if the neighboring site is occupied, the system stays as it was. This is a reversible Markov chain on the r-sets of 1, 2, . . ., n with uniform stationary distribution. Liggett (1985) gives background and motivation (he focuses on infinite systems). Fill (1991) gives bounds on the second eigenvalue of the labeled exclusion process on the finite circle ZZn 1 We study this chain by comparison with a second Markov chain on r-sets that proceeds by picking a particle at random, picking an unoccupied site at random (not necessarily a neighboring site) and moving the particle to the unoccupied site. This is a well studied chain (the Bernoulli-Laplace model for diffusion). Its eigenvalues are known. We show that the comparison techniques apply to give upper bounds on the eigenvalues of the exclusion We study the random walk on the symmetric group (S_n ) generated by the conjugacy class of cycles of length k. We show that the convergence to uniform measure of this walk has a cut-off in total variation distance after ( n k n ) steps, uniformly in (k = o(n) ) as (n ). The analysis follows from a new asymptotic estimation of the characters of the symmetric group evaluated at cycles.  We prove a conjecture raised by the work of Diaconis and Shahshahani (1981) about the mixing time of random walks on the permutation group induced by a given conjugacy class. To do this we exploit a connection with coalescence and fragmentation processes and control the Kantorovitch distance by using a variant of a coupling due to Oded Schramm. Recasting our proof in the language of Ricci curvature, our proof establishes the occurrence of a phase transition, which takes the following form in the case of random transpositions: at time @math , the curvature is asymptotically zero for @math and is strictly positive for @math .