The random k cycle walk on the symmetric group

被引：6
作者：
Hough, Bob [1 ]
机构：
[1] Stanford Univ, Dept Math, 450 Serra Mall, Stanford, CA 94305 USA
来源：
PROBABILITY THEORY AND RELATED FIELDS | 2016年 / 165卷 / 1-2期
基金：
欧洲研究理事会;
关键词：
Random walk on a group; Character bounds; Symmetric group; Cut-off phenomenon; FINITE-GROUPS; CHARACTERS; BOUNDS;
D O I：
10.1007/s00440-015-0636-6
中图分类号：
O21 [概率论与数理统计]; C8 [统计学];
学科分类号：
020208 ; 070103 ; 0714 ;
摘要：
We study the random walk on the symmetric group generated by the conjugacy class of cycles of length k. We show that the convergence to uniform measure of this walk has a cut-off in total variation distance after steps, uniformly in as . The analysis follows from a new asymptotic estimation of the characters of the symmetric group evaluated at cycles.
引用
收藏
页码：447 / 482
页数：36
相关论文
共 20 条
[1]  
[Anonymous], 2000, COLLOQ MATH-WARSAW
[2]   MIXING TIMES FOR RANDOM k-CYCLES AND COALESCENCE-FRAGMENTATION CHAINS [J].
Berestycki, Nathanaeel ;
Schramm, Oded ;
Zeitouni, Ofer .
ANNALS OF PROBABILITY, 2011, 39 (05) :1815-1843
[3]   GENERATING A RANDOM PERMUTATION WITH RANDOM TRANSPOSITIONS [J].
DIACONIS, P ;
SHAHSHAHANI, M .
ZEITSCHRIFT FUR WAHRSCHEINLICHKEITSTHEORIE UND VERWANDTE GEBIETE, 1981, 57 (02) :159-179
[4]   COMPARISON TECHNIQUES FOR RANDOM-WALK ON FINITE-GROUPS [J].
DIACONIS, P ;
SALOFFCOSTE, L .
ANNALS OF PROBABILITY, 1993, 21 (04) :2131-2156
[5]  
DIACONIS P., 1988, Lect. Notes-Monogr. Ser., V11
[6]   RANDOM SHUFFLES AND GROUP-REPRESENTATIONS [J].
FLATTO, L ;
ODLYZKO, AM ;
WALES, DB .
ANNALS OF PROBABILITY, 1985, 13 (01) :154-178
[7]  
Frobenius F. G., 1900, SITZUNGSBERICHTE PRE
[8]  
Fulton W., 1991, GRADUATE TEXTS MATH
[9]  
Hough B., 2012, ARXIV12112031
[10]  
Ingram S.J., 1950, P AM MATH SOC, V1, P358
12