Delayed path coupling and generating random permutations via distributed stochastic processes

Abstract

We analyze various stochastic processes for generating permutations almost uniformly at random in distributed and parallel systems. All our protocols are simple, elegant and are based on performing disjoint transpositions executed in parallel. The challenging problem of our concern is to prove that the output configurations in our processes reach almost uniform probability distribution very rapidly , i.e. in a (low) polylogarithmic time. For the analysis of the aforementioned protocols we develop a novel technique, called delayed path coupling , for proving rapid mixing of Markov chains. Our approach is an extension of the path coupling method of Bubley and Dyer. We apply delayed path coupling to three stochastic processes for generating random permutations. For one process, we apply standard (though non-trivial) coupling arguments, for the second one we construct a non-Markovian coupling, and for the third one we prove the existence of a non-Markovian coupling. To the best of our kno...