Time to reach stationarity in the Bernoulli-Laplace diffusion model with many urns (Q678614): Difference between revisions

Consider \(m\) urns labelled 1 through \(m\) and \(nm\) balls labelled 1 through \(nm\). Put the balls labelled 1 through \(n\) in the first urn, the balls labelled \(n+1\) through \(2n\) in the second urn, and so on. Then, at each time, choose at random two balls that belong to different urns and switch them. This model for \(m=2\) was introduced by Bernoulli and Laplace. \textit{P. Diaconis} and \textit{M. Shahshahani} [SIAM J. Math. Anal. 18, 208-218 (1987; Zbl 0617.60009)] studied this model and gave an upper and lower bound for the variation distance of the probability distribution after \(k\) steps from the stationary distribution. He showed that for such a model \(k=(1/4) n\log n\) switches are necessary and sufficient to reach stationarity, i.e. to mix the urns. The author presently shows that for every \(n\), \(m>2\) the model reaches stationarity after \((1/4) n(m-1)/ \log(nm^2)\) switches.