The Cut-Off Phenomenon for Random Walks on Hamming Graphs with Variable Growth Conditions

Abstract

The cut-off phenomenon is a remarkable critical phenomenon observed in the process of convergence to equilibrium in a wide variety of Markov chains. Diaconis-Graham-Morrison [3] established the first precise evaluation around the critical time for Ehrenfests' urn model concerning 2 urns and d balls, i.e. nearest neighbor random walks on hypercube Zd. They showed that deviation from the equilibrium state is described well by using the error function. In this article, we work out the evaluation around the critical time for simple random walks on Hamming graphs H(d,n), which coincide with an extended Ehrenfests' urn model concerning n urns and d balls. In our case, not only d but also n can grow in several manners. If n/d tends to 0, the similar result to [3] remains valid and microscopic deviation from the equilibrium state is described by the error function. If n/d tends to a nonzero constant, however, it is shown that the error function has to be replaced by an expression involving Poisson distributions.