On the mixing time of the Diaconis--Gangolli random walk on contingency tables over ℤ/ q ℤ

2018/08/19 by Evita Nestoridi, Oanh Nguyen, Nestoridi, Evita +1
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR) #math.CO #math.PR

paper · pdf · doi:10.48550/arxiv.1808.06157

arxiv created 2018/08/19 · arxiv updated 2018/08/21

Abstract

The Diaconis--Gangolli random walk is an algorithm that generates an almost uniform random graph with prescribed degrees. In this paper, we study the mixing time of the Diaconis--Gangolli random walk restricted on n× n contingency tables over ℤ/qℤ. We prove that the random walk exhibits cutoff at \fracn²4(1- cos(2 π)/(q)) log n, when log q=o ((√(log n))/(log log n) ).

Related

• Cutoff for Contingency Table Random Walks
• Cutoff for random to random card shuffle
• Random walks on the random graph
• The Evolution of the Mixing Rate
• Random walks on dynamic configuration models: a trichotomy