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 <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$t = \lfloor (n\log {n})/2 \rfloor $</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>t</mi> <mo>=</mo> <mo>⌊</mo> <mo stretchy="false">(</mo> <mi>n</mi> <mo>log</mo> <mi>n</mi> <mo stretchy="false">)</mo> <mo stretchy="false">/</mo> <mn>2</mn> <mo>⌋</mo> </mrow> </math></EquationSource> </InlineEquation>. Confirming a conjecture of N. Berestycki, we prove the definitive “hitting time” version of this result: let <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\tau $</EquationSource> <EquationSource Format="MATHML"><math> <mi>τ</mi> </math></EquationSource> </InlineEquation> denote the first time at which all cards have been touched. The total variation distance between the stopped distribution at <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$\tau $</EquationSource> <EquationSource Format="MATHML"><math> <mi>τ</mi> </math></EquationSource> </InlineEquation> and the uniform distribution on permutations is o(1); this is best possible, since at time <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$\tau -1$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>τ</mi> <mo>-</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>, the total variation distance is at least <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$(1+o(1))e^{-1}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <mo stretchy="false">(</mo> <mn>1</mn> <mo>+</mo> <mi>o</mi> <mrow> <mo stretchy="false">(</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> <mo stretchy="false">)</mo> </mrow> <msup> <mi>e</mi> <mrow> <mo>-</mo> <mn>1</mn> </mrow> </msup> </mrow> </math></EquationSource> </InlineEquation>.

Hitting time mixing for the random transposition walk

期刊论文
出版模式：

开放获取
发表日期：

2026年3月16日

查看全文

Vishesh Jain,
Mehtaab Sawhney

摘要

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 = \lfloor (n\log {n})/2 \rfloor $ $t = ⌊ (n log n) / 2 ⌋$ . Confirming a conjecture of N. Berestycki, we prove the definitive “hitting time” version of this result: let $\tau $ $τ$ denote the first time at which all cards have been touched. The total variation distance between the stopped distribution at $\tau $ $τ$ and the uniform distribution on permutations is o(1); this is best possible, since at time $\tau -1$ $τ - 1$ , the total variation distance is at least $(1+o(1))e^{-1}$ $(1 + o (1)) e^{- 1}$ .