The cut-off phenomenon for random walks on Hamming graphs with variable growth conditions (Q1387738)

Summary: The cut-off phenomenon is a remarkable critical phenomenon observed in the process of convergence to equilibrium in a wide variety of Markov chains. \textit{P. Diaconis}, \textit{R. L. Graham} and \textit{J. A. Morrison} [Random Struct. Algorithms 1, No. 1, 51-72 (1990; Zbl 0723.60085)] established the first precise evaluation around the critical time for Ehrenfest's urn model concerning two urns and \(d\) balls, i.e. nearest neighbor random walks on hypercube \(\mathbb{Z}^d_2\). They showed that deviation from the equilibrium state is described well by using the error function. We work out the evaluation around the critical time for simple random walks on Hamming graphs \(H(d,n)\), which coincide with an extended Ehrenfest's 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 the paper quoted above 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.