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.