Hitting time mixing for the random transposition walk

• 成果类型: Article; Early Access
• 署名作者: Jain, Vishesh; Sawhney, Mehtaab
• 署名单位: University of Illinois System; University of Illinois Chicago; University of Illinois Chicago Hospital; Columbia University
• 刊物名称: PROBABILITY THEORY AND RELATED FIELDS
• ISSN/ISSBN: 0178-8051; 1432-2064
• DOI: 10.1007/s00440-026-01479-9
• 发表日期: 2026-03-16
• 关键词: permutation

摘要

Consider shuffling a deck of n cards, labeled 1 through n, as follows: at each time step, pick one card uniformly with your right hand and another card, independently and uniformly with your left hand; then swap the cards. How long does it take until the deck is close to random? Diaconis and Shahshahani showed that this process undergoes cutoff in total variation distance at time t=& LeftFloor;(nlogn)/2 & RightFloor;\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$t = \lfloor (n\log {n})/2 \rfloor $$\end{document}. Confirming a conjecture of N. Berestycki, we prove the definitive hitting time version of this result: let tau\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\tau $$\end{document} denote the first time at which all cards have been touched. The total variation distance between the stopped distribution at tau\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\tau $$\end{document} and the uniform distribution on permutations is o(1); this is best possible, since at time tau-1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\tau -1$$\end{document}, the total variation distance is at least (1+o(1))e-1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(1+o(1))e<^>{-1}$$\end{document}.