Generating a random permutation with random transpositions

From MaRDI portal

Publication:3945280

Jump to:navigation, search

DOI10.1007/BF00535487zbMath0485.60006WikidataQ97613636 ScholiaQ97613636MaRDI QIDQ3945280

Persi Diaconis, Mehrdad M. Shahshahani

Publication date: 1981

Published in: Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete (Search for Journal in Brave)

zbMATH Keywords

group representations convolution powers probabilities on groups

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Stochastic matrices (15B51) Probability measures on groups or semigroups, Fourier transforms, factorization (60B15)

Related Items

An Erdős-Ko-Rado theorem for finite 2-transitive groups, On the partitions associated with the smallest eigenvalues of certain Cayley graphs on symmetric group generated by cycles, Perfect sampling using bounding chains., Mixing time and cutoff for the adjacent transposition shuffle and the simple exclusion, Hypergroup deformations and Markov chains, The random \(k\) cycle walk on the symmetric group, Determination of the spectral gap for Kac's master equation and related stochastic evolution., A spectral radius formula for the Fourier transform on compact groups and applications to random walks, Fuchsian groups, coverings of Riemann surfaces, subgroup growth, random quotients and random walks., Precise estimates on the rate at which certain diffusions tend to equilibrium, Strong uniform times and finite random walks, Total variation cutoff in birth-and-death chains, On a likely shape of the random Ferrers diagram, Rate of convergence for shuffling cards by transpositions, Random walks and orthogonal functions associated with highly symmetric graphs, Characters and random walks on finite classical groups, Poisson-Dirichlet distribution for random Belyi surfaces, Interactions between Ehrenfest's urns arising from group actions, Expansion properties of Cayley graphs of the alternating groups, Cutoff on all Ramanujan graphs, The probability of long cycles in interchange processes, Modified logarithmic Sobolev inequalities in discrete settings, Analysis of casino shelf shuffling machines, On the number of rim hook tableaux, Mixing of the upper triangular matrix walk, On the chromatic number of structured Cayley graphs, Some things we've learned (about Markov chain Monte Carlo), A new large \(N\) phase transition in \(\text{YM}_2\), Concentration of Haar measures, with an application to random matrices, On the eigenvalues of Cayley graphs on the symmetric group generated by a complete multipartite set of transpositions, Spectral analysis of random-to-random Markov chains, Integral Cayley multigraphs over abelian and Hamiltonian groups, The Erdős-Ko-Rado property for some 2-transitive groups, Cutoff phenomenon for random walks on Kneser graphs, Random walks and approximate integration on compact homogeneous spaces, Uniformity of the uncovered set of random walk and cutoff for lamplighter chains, On a surface formed by randomly gluing together polygonal discs, Cutoff for the Ising model on the lattice, The spectrum of eigenvalues for certain subgraphs of the \(k\)-point fixing graph, Likelihood orders for the \(p\)-cycle walks on the symmetric group, The smallest eigenvalues of the 1-point fixing graph, Mixing and concentration by Ricci curvature, Stability for intersecting families in \(\mathrm{PGL}(2,q)\), Painting a graph with competing random walks, Prescribed absolute values, character sums and spectrum integrality., Two-dimensional gauge theories of the symmetric group \(S_n\) in the large-\(N\) limit, On the dynamical behavior of the ABC model, Mixing times for random \(k\)-cycles and coalescence-fragmentation chains, Exponential decay of entropy in the random transposition and Bernoulli-Laplace models, Mixing and generation in simple groups., Random generators of the symmetric group: diameter, mixing time and spectral gap., Mixing times of lozenge tiling and card shuffling Markov chains, Cutoff at the ``entropic time for sparse Markov chains, Words and mixing times in finite simple groups., On groups all of whose undirected Cayley graphs of bounded valency are integral, An Erdős-Ko-Rado theorem for the group \(\mathrm{PSU}(3, q)\), Finite Gel'fand pairs and their applications to probability and statistics, Cutoff for conjugacy-invariant random walks on the permutation group, A Markov chain on the symmetric group and Jack symmetric functions, Nash inequalities for finite Markov chains, Time to reach stationarity in the Bernoulli-Laplace diffusion model with many urns, On the cycle structure of Mallows permutations, An affine walk on the hypercube, A random walk on the symmetric group generated by random involutions, Card shuffling and a transformation on \(S_ n\), A quasi-stability result for dictatorships in \(S_n\), Ergodic properties of folding maps on spheres, A probabilistic interpretation of the Macdonald polynomials, Generating random elements in \(SL_ n(F_ q)\) by random transvections, Erdős-Ko-Rado theorem for irreducible imprimitive reflection groups, The second eigenvalue of some normal Cayley graphs of highly transitive groups, Merging for inhomogeneous finite Markov chains. II: Nash and log-Sobolev inequalities, The distance spectra of Cayley graphs of Coxeter groups, Comment on ``Random quantum circuits are approximate 2-designs by A.W. Harrow and R.A. Low (Commun. Math. Phys. 291, 257-302 (2009)), A comparison theorem on convergence rates of random walks on groups, Exact solution for a class of random walk on the hypercube, Stein's method, Jack measure, and the Metropolis algorithm, A rule of thumb for riffle shuffling, Cutoff phenomena for random walks on random regular graphs, Separation cut-offs for birth and death chains, Spectra of Cayley graphs of complex reflection groups, Largest independent sets of certain regular subgraphs of the derangement graph, Characters of symmetric groups: sharp bounds and applications., Hecke graphs, Ramanujan graphs and generalized duality transformations for lattice spin systems, Mixing time of the card-cyclic-to-random shuffle, Improved mixing time bounds for the Thorp shuffle and \(L\)-reversal chain, A strong uniform time for random transpositions, Reversal and transposition medians, Mixing and covering in the symmetric groups, On the random Young diagrams and their cores, Rank and duality in representation theory, Random walks on finite quantum groups, Comparing eigenvalue bounds for Markov chains: When does Poincaré beat Cheeger?, Transition distributions of Young diagrams under periodically weighted Plancherel measures, An ergodic theorem for read-once non-uniform deterministic finite automata, Faster random generation of linear extensions, Logarithmic Sobolev inequality for some models of random walks, Two-dimensional gauge theories of the symmetric group \(S_n\) and branched \(n\)-coverings of Riemann surfaces in the large-\(n\) limit, Rapidly mixing random walks and bounds on characters of the symmetric group, Another conversation with Persi Diaconis, On the spectrum of finite Cayley graphs, ON THE SPECTRUM OF DERANGEMENT GRAPHS OF ORDER A PRODUCT OF THREE PRIMES, Antiduality and Möbius monotonicity: generalized coupon collector problem, COMPUTING THE EIGENVALUES OF CAYLEY GRAPHS OF ORDER p2q, Some Erdös-Ko-Rado results for linear and affine groups of degree two, Generation of the symmetric group Sn2, Total variation cutoff for the flip-transpose top with random shuffle, Stein’s method and Plancherel measure of the symmetric group, On the spectrum of Cayley graphs, Mixing times of Markov chains for self‐organizing lists and biased permutations, CUTOFF AT THE ENTROPIC TIME FOR RANDOM WALKS ON COVERED EXPANDER GRAPHS, Recurrence and Transience for a Card Shuffling Model, Cutoff phenomenon for the warp-transpose top with random shuffle, Fundamental weight systems are quantum states, Sharp Poincaré and log-Sobolev inequalities for the switch chain on regular bipartite graphs, Random feedback shift registers and the limit distribution for largest cycle lengths, Random walks generated by the Ewens distribution on the symmetric group, On random walks and switched random walks on homogeneous spaces, Modified log-Sobolev inequalities for strong-Rayleigh measures, G-Circulant Quantum Markov Semigroups, Character estimates for finite simple groups and applications, Stein's method and random character ratios, Character levels and character bounds for finite classical groups, Cutoff profile of the metropolis biased card shuffling, On the second eigenvalue of certain Cayley graphs on the symmetric group, Finite length spectra of random surfaces and their dependence on genus, Upgrading MLSI to LSI for reversible Markov chains, Cutoff for the non reversible SSEP with reservoirs, Cutoff in the Bernoulli-Laplace urn model with swaps of order \(n\), Geometric bounds on the fastest mixing Markov chain, Rapid Mixing of \({\boldsymbol{k}}\)-Class Biased Permutations, Unnamed Item, Quantum reflections, random walks and cut-off, Unnamed Item, Unnamed Item, Character ratios for finite groups of Lie type, and applications, Conjugacy classes, growth and complexity, LOW-DEGREE BOOLEAN FUNCTIONS ON , WITH AN APPLICATION TO ISOPERIMETRY, The closure of a random braid is a hyperbolic link, Step Size in Stein's Method of Exchangeable Pairs, Analyzing Glauber dynamics by comparison of Markov chains, The ergodic theorem for random walks on finite quantum groups, Intersecting families of permutations, Cutoff for General Spin Systems with Arbitrary Boundary Conditions, Proof of Aldous’ spectral gap conjecture, Unnamed Item, Some relations on prefix reversal generators of the symmetric and hyperoctahedral group, Delayed path coupling and generating random permutations, On random walks on affine group, Mixing time and local exponential ergodicity of the east-like process in \(\mathbb{Z}^d\), An exposition to information percolation for the Ising model, Discrete Ricci curvature bounds for Bernoulli-Laplace and random transposition models, Information percolation and cutoff for the stochastic Ising model, A Few Remarks on the Octopus Inequality and Aldous’ Spectral Gap Conjecture, On finite groups all of whose cubic Cayley graphs are integral, Unnamed Item, The Markov chain Monte Carlo revolution, CHARACTER LEVELS AND CHARACTER BOUNDS, Efficient Computation of the Fourier Transform on Finite Groups, Martingales and character ratios, ON THE PARTIAL DIFFERENCE SETS IN CAYLEY DERANGEMENT GRAPHS, Unnamed Item, Rapid Mixing and Markov Bases, FKN theorem for the multislice, with applications, Random doubly stochastic tridiagonal matrices, On the energy and Estrada index of Cayley graphs, Markov chains, ${\mathscr R}$-trivial monoids and representation theory, A stability result for balanced dictatorships in S_n, Growth in groups: ideas and perspectives, Self-intersections of random walks on discrete groups, The hit-and-run version of top-to-random, On the spectrum of Cayley graphs related to the finite groups, Double coset Markov chains, A phase transition for repeated averages, Cutoff for random lifts of weighted graphs, Log-Sobolev inequality for the multislice, with applications, The spectrum and convergence rates of exclusion and interchange processes on the complete graph, Character theory of symmetric groups, subgroup growth of Fuchsian groups, and random walks., Online card games, Convergence of some time inhomogeneous Markov chains via spectral techniques, Exact convergence analysis of the independent Metropolis-Hastings algorithms, No cutoff in spherically symmetric trees, Eigenvalues of Cayley graphs, An isoperimetric inequality for conjugation-invariant sets in the symmetric group, Cutoff profile of ASEP on a segment, Another proof of the Harer-Zagier formula, The topology and geometry of random square-tiled surfaces, Spectral analysis of finite Markov chains with spherical symmetries, Groups all of whose undirected Cayley graphs are integral, Compositions of random transpositions, Cutoff profiles for quantum Lévy processes and quantum random transpositions, Sorting by shuffling methods and a queue, The eigenvalues of the graphs \(D(4,q)\), Cutoff on Ramanujan complexes and classical groups, A threshold for cutoff in two-community random graphs, Mixing time and cutoff for the weakly asymmetric simple exclusion process, Mixing properties of stochastic quantum Hamiltonians, The bead process for beta ensembles, Random surfaces with boundary, On the mixing time of the Diaconis-Gangolli random walk on contingency tables over \(\mathbb{Z}/q\mathbb{Z} \), Tensor powers of the defining representation of \(S_n\), Random walk on sparse random digraphs, Approximation by juntas in the symmetric group, and forbidden intersection problems, Random motion on finite rings. I: commutative rings, Limit distributions for Euclidean random permutations, The spectrum of Cayley graphs on symmetric group generated by certain subset of \(r\)-cycles, Tensor product Markov chains, Cutoff for permuted Markov chains, Upper bound on the characters of the symmetric groups for balanced Young diagrams and a generalized Frobenius formula., Cutoff for the warp-transpose top with random shuffle, Efficient generation of random derangements with the expected distribution of cycle lengths, Total variation cutoff for the transpose top-2 with random shuffle, Aldous' spectral gap property for normal Cayley graphs on symmetric groups, Permutation statistics of products of random permutations, Limit profile for random transpositions, On the eigenvalues of certain Cayley graphs and arrangement graphs, On the error bound in the normal approximation for Jack measures, Solving the Ku-Wales conjecture on the eigenvalues of the derangement graph, Random walks on Ramanujan complexes and digraphs, Asymptotically liberating sequences of random unitary matrices, Forbidding just one intersection, for permutations, A general lower bound for mixing of single-site dynamics on graphs, The Erdős-Ko-Rado theorem for 2-pointwise and 2-setwise intersecting permutations, The interchange process on high-dimensional products, Cutoff for a one-sided transposition shuffle, Convergence rates of random walk on irreducible representations of finite groups, Zero-temperature 2D stochastic Ising model and anisotropic curve-shortening flow, Random walk on the symplectic forms over a finite field, The law of the iterated logarithm for character ratios, All 2-transitive groups have the EKR-module property, Modified logarithmic Sobolev inequalities for some models of random walk, Cayley graph on symmetric group generated by elements fixing \(k\) points, The spectra of arrangement graphs, Analysis of top to bottom-\(k\) shuffles, Remarks on singular Cayley graphs and vanishing elements of simple groups, Cutoff for the Bernoulli-Laplace urn model with \(o(n)\) swaps, Comparing with octopi, The random transposition dynamics on random regular graphs and the Gaussian free field, Cutoff for the mean-field zero-range process, Cutoff for random to random card shuffle, Mixing time trichotomy in regenerating dynamic digraphs, On the spectral gap of some Cayley graphs on the Weyl group \(W(B_n)\), Phase transition for the interchange and quantum Heisenberg models on the Hamming graph, The full spectrum of random walks on complete finite \(d\)-ary trees, Signal processing on the permutahedron: tight spectral frames for ranked data analysis, Integral Cayley graphs, Fast initial conditions for Glauber dynamics, Isoperimetric profiles and random walks on some groups defined by piecewise actions, Eigenvalues of symmetrized shuffling operators, Cut-off phenomenon for random walks on free orthogonal quantum groups, The random \((n-k)\)-cycle to transpositions walk on the symmetric group, The second largest eigenvalues of some Cayley graphs on alternating groups, Mixing times for exclusion processes on hypergraphs, Limit profiles for reversible Markov chains, Comparing mixing times on sparse random graphs, Mixing of permutations by biased transpositions, Modified log-Sobolev inequalities, Beckner inequalities and moment estimates, The geometry of random minimal factorizations of a long cycle via biconditioned bitype random trees, A sharp log-Sobolev inequality for the multislice, The mean-field quantum Heisenberg ferromagnet via representation theory, Spectrum of the transposition graph, Diaconis-Shahshahani upper bound lemma for finite quantum groups, Logarithmic Sobolev inequalities for finite Markov chains, Lumpings of algebraic Markov chains arise from subquotients, A version of Aldous' spectral-gap conjecture for the zero range process, Fast and memory-optimal dimension reduction using Kac's walk, On mixing behavior of a family of random walks determined by a linear recurrence, A conversation with David J. Aldous, Cutoff for the East process, Generating a random signed permutation with random reversals, On the intersection density of primitive groups of degree a product of two odd primes, Mixing time of Metropolis chain based on random transposition walk converging to multivariate Ewens distribution, On the partition associated to the smallest eigenvalues of the \(k\)-point fixing graph

Cites Work

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:3945280&oldid=17641442"