MIXING TIMES FOR RANDOM k-CYCLES AND COALESCENCE-FRAGMENTATION CHAINS

• 成果类型: Article
• 署名作者: Berestycki, Nathanaeel; Schramm, Oded; Zeitouni, Ofer
• 署名单位: University of Cambridge; Weizmann Institute of Science; University of Minnesota System; University of Minnesota Twin Cities
• 刊物名称: ANNALS OF PROBABILITY
• ISSN/ISSBN: 0091-1798
• DOI: 10.1214/10-AOP634
• 发表日期: 2011
• 页码: 1815-1843
• 关键词: random-walks; random transpositions; finite-groups; characters

摘要

Let S(n) be the permutation group on n elements, and consider a random walk on S(n) whose step distribution is uniform on k-cycles. We prove a well-known conjecture that the mixing time of this process is (1/k)n log n, with threshold of width linear in n. Our proofs are elementary and purely probabilistic, and do not appeal to the representation theory of S(n).