Random walks on finite groups
The author presents a survey on random walks on finite groups, an area of research which was very active during the last decade. In fact, the emphasis of this article is laid on quantitative results, in particular on rates of convergence to uniform distribution. Of course, in a survey most proofs have to be omitted, the author explains the results and their importance by concrete examples, the most prominent are card shuffling problems. The paper is divided into ten sections. The titles may serve as a list of contents: Introduction; Background and notations (including general Markov chain techniques); Shuffling cards and cut-off phenomenon; Probabilistic methods; Spectrum and singular values (eigenvalue bounds for general Markov chains and in particular for random walks); Eigenvalue bounds using paths (i.e., paths in the corresponding Caley graph); Volume growth conditions; Representation theory for finite groups (and rates for convergence to the uniform distribution); comparsion techniques (comparsion of two random walks via corresponding Dirichlet forms). An introduction to this field and a first survey reflecting the investigations up to 1988 is found in the stimulating booklet of \textit{P. Diaconis} [``Group representations in probability and statistics (1988; Zbl 0695.60012)]. In the present survey the list of references contains 146 items, showing the activity of the research field. It should be noted that many important contributions of the last decade are due to the author and to P. Diaconis. For the entire collection see [Zbl 1025.60001].
- A survey of results on random random walks on finite groups
- scientific article; zbMATH DE number 1303224
- scientific article; zbMATH DE number 736278
- Random Walks on Infinite Groups
- Groups, graphs and random walks. Selected papers of the workshop, Cortona, Italy, June 2--6, 2014 on the occasion of the 60th birthday of Wolfgang Woess
- Random shuffles and group representations
- Random Walks on Infinite Graphs and Groups
- Commutation relations and Markov chains
- Cutoff time based on generalized divergence measure
- An explicit integral polynomial whose splitting field has Galois group \(W(E_8)\)
- Random walks on groups. Applications to Fuchsian groups
- First hitting times for some random walks on finite groups
- Finite range random walk on free groups and homogeneous trees
- Comparison techniques for random walk on finite groups
- Moderate growth and random walk on finite groups
- Characters and random walks on finite classical groups
- Random walk in random groups.
- Random walks on finite rank solvable groups.
- The minimal subgroup of a random walk
- Cutoffs for product chains
- On the mixing time of Kac's walk and other high-dimensional Gibbs samplers with constraints
- Spectral analysis of random-to-random Markov chains
- Cayley graphs and complexity geometry
- Deterministic encryption with the Thorp shuffle
- Mixing times for random walks on finite lamplighter groups
- Sandpile models
- Algebras of probability distributions on finite sets
- Random walks on wreath products of groups
- A super-class walk on upper-triangular matrices
- Cutoff for the Ising model on the lattice
- Splitting fields of characteristic polynomials of random elements in arithmetic groups
- Abrupt convergence for a family of Ornstein-Uhlenbeck processes
- Random walks on the BMW monoid: an algebraic approach
- An exercise(?) in Fourier analysis on the Heisenberg group
- Harry Kesten's work in probability theory
- On mixing behavior of a family of random walks determined by a linear recurrence
- On sums of Bernoulli random variables modulo 3
- Random walks on finite nilpotent groups driven by long-jump measures
- Cutoff on Ramanujan complexes and classical groups
- Shuffling cards by spatial motion
- Cut-off phenomenon for Ornstein-Uhlenbeck processes driven by Lévy processes
- Random motion on finite rings. I: commutative rings
- Cutoff for the warp-transpose top with random shuffle
- Total variation cutoff for the transpose top-2 with random shuffle
- Random walks on Ramanujan complexes and digraphs
- Cutoff for a one-sided transposition shuffle
- On necessary conditions of probability limit theorems in finite algebras
- The cutoff phenomenon in total variation for nonlinear Langevin systems with small layered stable noise
- Products of random walks on finite groups with moderate growth
- The random \((n-k)\)-cycle to transpositions walk on the symmetric group
- Diaconis-Shahshahani upper bound lemma for finite quantum groups
- Lumpings of algebraic Markov chains arise from subquotients
- \(L^1\)-Poincaré inequality for discrete time Markov chains
- Abelian groups yield many large families for the diamond problem
- Convergence of some time inhomogeneous Markov chains via spectral techniques
- Abrupt convergence and escape behavior for birth and death chains
- The loop-erased random walk and the uniform spanning tree on the four-dimensional discrete torus
- Random walk on sparse random digraphs
- Permutation statistics of products of random permutations
- Communication constraints in the average consensus problem
- A large deviation inequality for vector functions on finite reversible Markov chains
- Cut-off for large sums of graphs
- Convergence rates of random walk on irreducible representations of finite groups
- Modified logarithmic Sobolev inequalities for some models of random walk
- Analysis of top to bottom-\(k\) shuffles
- Enumeration and random walks on finite groups
- Thermalisation for small random perturbations of dynamical systems
- Sandpile groups of random bipartite graphs
- Information percolation and cutoff for the stochastic Ising model
- Abrupt convergence for stochastic small perturbations of one dimensional dynamical systems
- The random k cycle walk on the symmetric group
- Approximate randomized benchmarking for finite groups
- scientific article; zbMATH DE number 3844712 (Why is no real title available?)
- scientific article; zbMATH DE number 3848354 (Why is no real title available?)
- The cutoff phenomenon for randomized riffle shuffles
- Random Walks on Infinite Graphs and Groups
- A sharp diameter bound for unipotent groups of classical type over ℤ/pℤ
- Some things we've learned (about Markov chain Monte Carlo)
- Random walks in compact groups
- scientific article; zbMATH DE number 4062235 (Why is no real title available?)
- scientific article; zbMATH DE number 4082591 (Why is no real title available?)
- scientific article; zbMATH DE number 1210292 (Why is no real title available?)
- Random walks on finite semigroups
- The cutoff phenomenon for Ehrenfest chains
- scientific article; zbMATH DE number 2070153 (Why is no real title available?)
- Random generators of the symmetric group: diameter, mixing time and spectral gap.
- Random Walks on Infinite Graphs and Groups
- Total variation cutoff for the flip-transpose top with random shuffle
- Conditions of convergence of a random walk on a finite group
- No cutoff for circulants: an elementary proof
- Aldous's spectral gap conjecture for normal sets
- A non-local random walk on the hypercube
- Mixing time and eigenvalues of the abelian sandpile Markov chain
- On the interplay between Černý and Babai's conjectures
- Harmonic analysis on finite groups. Representation theory, Gelfand pairs and Markov chains
- Cut-off and hitting times of a sample of Ornstein-Uhlenbeck processes and its average
- The hit-and-run version of top-to-random
- Double coset Markov chains
- Spatio-temporal dynamics of random transmission events: from information sharing to epidemic spread
- On finite algebras with probability limit laws
- Cutoff phenomenon for the warp-transpose top with random shuffle
- Random walks generated by the Ewens distribution on the symmetric group
- Abelian sandpiles on Sierpiński gasket graphs
- Noise sensitivity of random walks on groups
- Cutoff profile of the metropolis biased card shuffling
- Capacity of the range of random walks on groups
- Mixing times for random \(k\)-cycles and coalescence-fragmentation chains
This page was built for publication: Random walks on finite groups
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4450069)
