Cutoff for Contingency Table Random Walks

2024/07/23 by Fang, Zihao, Heeszel, Andrew
#FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.2407.16203

Abstract

We study the Diaconis-Gangolli random walk on n × n contingency tables and its analog on 1 × n contingency tables, both over ℤ/qℤ. In the 1 × n case, we prove that the random walk exhibits cutoff at time \dfracn q² log(n)8 π² when q ≫ n; in the n × n case, we establish cutoff for the random walk at time \dfracn² q² log(n)8 π² when q ≫ n². We also show that a general class of random walks on (ℤ/qℤ)ⁿ with a marginal incremental variance \dfracσ²n (when mapped to ( ℤ ∩ [-q/2, q/2))ⁿ) has cutoff at time \dfracnq² log(n)4π² σ².

Related

• On the mixing time of the Diaconis--Gangolli random walk on contingency tables over ℤ/ q ℤ
• The Cut-Off Phenomenon in Random Walks on Finite Groups
• Remarks on cutoff phenomena for random walks on Hamming Schemes
• Cutoff Phenomenon and Limiting Profile of a Random Walk on the Symmetric Group
• Random Walks on ℤ_q^d