Likelihood orders for the \(p\)-cycle walks on the symmetric group
type: Item
instance of: scholarly article
title: Likelihood orders for the \(p\)-cycle walks on the symmetric group
zbMATH Open document ID: 1380.05194
author: Megan Bernstein
published in: The Electronic Journal of Combinatorics
publication date: 2018-02-22T00:00:00Z
full work available at URL: v25i1p25
review text: Summary: Consider for a random walk on a group, the order from most to least likely element of the walk at each step, called the likelihood order. Up to periodicity issues, this order stabilizes after a sufficient number of steps. Here discrete Fourier analysis and the representations of the symmetric group, particularly formulas for the characters, are used to find the order after sufficient time for the random walks on the symmetric group generated by \(p\)-cycles for any \(p\) fixed, \(n\) sufficiently large. For the transposition walk, generated by all the \(2\)-cycles, at various levels of laziness, it is shown that order \(n^2\) steps suffice for the order to stabilize. Likelihood orders can aid in finding the total variation or separation distance mixing times.
Mathematics Subject Classification ID: 05E10
Mathematics Subject Classification ID: 05E05
Mathematics Subject Classification ID: 20C30
Mathematics Subject Classification ID: 60J10
zbMATH DE Number: 6841869
zbMATH Keywords: random walks
zbMATH Keywords: symmetric groups
zbMATH Keywords: character polynomial
zbMATH Keywords: likelihood order
MaRDI profile type: Publication
cites work: Strong uniform times and finite random walks
cites work: Cutoff for random to random card shuffle
cites work: Q3995195
cites work: Supercharacters and superclasses for algebra groups
cites work: Generating a random permutation with random transpositions
cites work: Random shuffles and group representations
cites work: Character polynomials, their \(q\)-analogs and the Kronecker product.
cites work: Q4057549
cites work: Q3549475
cites work: Q5797085
cites work: Q4328336
cites work: Q5775434
cites work: Some Characters of the Symmetric Group
cites work: Q4236280
cites work: Q3225387
Recommended article: The random \(k\) cycle walk on the symmetric group
Recommended article: The random \((n-k)\)-cycle to transpositions walk on the symmetric group
Recommended article: The generalized weighted probability measure on the symmetric group and the asymptotic behavior of the cycles
Recommended article: A random walk on the symmetric group generated by random involutions
Recommended article: Q3763306
Recommended article: Q4890772
Recommended article: Cutoff for conjugacy-invariant random walks on the permutation group
Recommended article: Rapidly mixing random walks and bounds on characters of the symmetric group
description: scientific article; zbMATH DE number 6841869