Likelihood orders for the \(p\)-cycle walks on the symmetric group
The electronic journal of combinatorics, Tome 25 (2018) no. 1
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.
DOI :
10.37236/7373
Classification :
05E10, 05E05, 20C30, 60J10
Mots-clés : random walks, symmetric groups, character polynomial, likelihood order
Mots-clés : random walks, symmetric groups, character polynomial, likelihood order
Affiliations des auteurs :
Megan Bernstein 1
@article{10_37236_7373,
author = {Megan Bernstein},
title = {Likelihood orders for the \(p\)-cycle walks on the symmetric group},
journal = {The electronic journal of combinatorics},
year = {2018},
volume = {25},
number = {1},
doi = {10.37236/7373},
zbl = {1380.05194},
url = {http://geodesic.mathdoc.fr/articles/10.37236/7373/}
}
Megan Bernstein. Likelihood orders for the \(p\)-cycle walks on the symmetric group. The electronic journal of combinatorics, Tome 25 (2018) no. 1. doi: 10.37236/7373
Cité par Sources :