Comparison techniques for random walk on finite groups

DOI10.1214/aop/1176989013zbMath0790.60011OpenAlexW2065163799MaRDI QIDQ1317235

Laurent Saloff-Coste, Persi Diaconis

Publication date: 20 June 1994

Published in: The Annals of Probability (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1214/aop/1176989013

zbMATH Keywords

eigenvaluessymmetric groupcard shufflingreversible Markov chainsconvergence of a symmetric random walk

Mathematics Subject Classification ID

Discrete-time Markov processes on general state spaces (60J05) Symmetric groups (20B30) Limit theorems in probability theory (60F99) Probability measures on groups or semigroups, Fourier transforms, factorization (60B15)

Related Items

A phase transition for repeated averages, Markov chain decomposition for convergence rate analysis, Network cohesion, No cutoff for circulants: an elementary proof, A super-class walk on upper-triangular matrices, FIXED POINT RATIOS IN EXCEPTIONAL GROUPS OF RANK AT MOST TWO, The random \(k\) cycle walk on the symmetric group, Superinduction for pattern groups., Convergence of some time inhomogeneous Markov chains via spectral techniques, The nearest neighbor random walk on subspaces of a vector space and rate of convergence, Divisibility and laws in finite simple groups., Rate of convergence for shuffling cards by transpositions, Characters and random walks on finite classical groups, Total variation cutoff for the flip-transpose top with random shuffle, Stein’s method and Plancherel measure of the symmetric group, Shuffling cards by spatial motion, Walks on generating sets of Abelian groups, SPEck: mining statistically-significant sequential patterns efficiently with exact sampling, Some things we've learned (about Markov chain Monte Carlo), An averaging process on hypergraphs, Convergence properties of the Gibbs sampler for perturbations of Gaussians, On the mixing time of the Diaconis-Gangolli random walk on contingency tables over \(\mathbb{Z}/q\mathbb{Z} \), Trivial points on towers of curves, Mixing times of Markov chains for self‐organizing lists and biased permutations, Fast algorithms at low temperatures via Markov chains†, Sharp Poincaré and log-Sobolev inequalities for the switch chain on regular bipartite graphs, Tensor product Markov chains, Generating random elements of a finite group, Efficient unitary designs with a system-size independent number of non-Clifford gates, Cutoff for the Ising model on the lattice, Nilprogressions and groups with moderate growth, Comparison theory for Markov chains on different state spaces and application to random walk on derangements, Asymptotic behaviors of random walks on countable groups, Rapid Mixing of \({\boldsymbol{k}}\)-Class Biased Permutations, Expander graphs, gonality, and variation of Galois representations, Unnamed Item, Spectral computations for birth and death chains, Geometric analysis for the Metropolis algorithm on Lipschitz domains, On transience of card shuffling, Aldous’s spectral gap conjecture for normal sets, Unnamed Item, On the diameter of permutation groups., Analysis of convergence rates of some Gibbs samplers on continuous state spaces, The product replacement prospector., Random generators of the symmetric group: diameter, mixing time and spectral gap., Mixing times of lozenge tiling and card shuffling Markov chains, Card shuffling and Diophantine approximation, Uniform mixing time for random walk on lamplighter graphs, Short laws for finite groups and residual finiteness growth, A sharp diameter bound for unipotent groups of classical type over ℤ/pℤ, On the spectral gap and the diameter of Cayley graphs, Analyzing Glauber dynamics by comparison of Markov chains, Nash inequalities for finite Markov chains, Time to reach stationarity in the Bernoulli-Laplace diffusion model with many urns, On the local-global conjecture for integral Apollonian gaskets. With an appendix by Péter P. Varjú, Super-character theory and comparison arguments for a random walk on the upper triangular matrices, Cutoff for General Spin Systems with Arbitrary Boundary Conditions, A comparison theorem on convergence rates of random walks on groups, Modified logarithmic Sobolev inequalities for some models of random walk, Analysis of top to bottom-\(k\) shuffles, Mixing time of critical Ising model on trees is polynomial in the height, Comparing with octopi, Cutoff for random to random card shuffle, Separation cut-offs for birth and death chains, Information percolation and cutoff for the stochastic Ising model, Crested products of Markov chains, Mixing time of the card-cyclic-to-random shuffle, Analytic-geometric methods for finite Markov chains with applications to quasi-stationarity, Supercharacter formulas for pattern groups, Eigenvalues of symmetrized shuffling operators, A non-local random walk on the hypercube, Condensation of a self-attracting random walk, Mixing of permutations by biased transpositions, A sharp log-Sobolev inequality for the multislice, The mean-field quantum Heisenberg ferromagnet via representation theory, Consistent estimation of the spectrum of trace class data augmentation algorithms, Navigating directed Cayley graphs of small diameter: A potent Solovay–Kitaev procedure, Convergence of random walks on the circle generated by an irrational rotation, On random random walks, Logarithmic Sobolev inequalities for finite Markov chains, Mixing time of fractional random walk on finite fields, Hypercontractivity and logarithmic Sobolev inequality for non-primitive quantum Markov semigroups and estimation of decoherence rates, Growth in groups: ideas and perspectives, Generating a random signed permutation with random reversals, The hit-and-run version of top-to-random, Spatio-temporal dynamics of random transmission events: from information sharing to epidemic spread