Delayed Path Coupling and Generating Random Permutations
Artur Czumaj, Miroslaw Kutylowski
We consider the problem of generating permutations almost uniformly at
random in distributed and parallel systems. We propose a simple
distributed scheme for permuting at random, which we call distributed
mixing, and provide its precise stochastic analysis. Our main result is
that distributed mixing needs Theta(log n) simple point-to-point
communication rounds to generate a permutation almost uniformly at
random. We further apply distributed mixing to design very fast parallel
algorithms for OCPC and QRQW parallel computers (with runtimes O(loglog
n) and O(sqrt(log n)) respectively).
Our analysis of distributed mixing is based on the analysis of the
mixing time of the Markov chain governing the process. The main
technical tool developed in the paper is a novel method of analyzing
convergence of Markov chains. Our method, called delayed path coupling,
is a refinement of the classical coupling technique and the path
coupling technique of Bubley and Dyer, and its main, novel feature is
the use of possible non-Markovian coupling.