Comparison techniques for random walk on finite groups
From MaRDI portal
Publication:1317235
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
eigenvaluessymmetric groupcard shufflingreversible Markov chainsconvergence of a symmetric random walk
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 (86)
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
This page was built for publication: Comparison techniques for random walk on finite groups
