On the mixing time of the Diaconis-Gangolli random walk on contingency tables over Z/qZ

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 x n contingency tables over Z/qZ. We prove that the random walk exhibits cutoff at n(2)/4(1-cos 2 pi/q) log n, when log q = o(root log n/log log n).