Premium
Delayed path coupling and generating random permutations
Author(s) -
Czumaj Artur,
Kutyłowski Mirosław
Publication year - 2000
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/1098-2418(200010/12)17:3/4<238::aid-rsa4>3.0.co;2-e
Subject(s) - mixing (physics) , permutation (music) , computer science , coupling (piping) , markov chain , simple (philosophy) , path (computing) , markov process , convergence (economics) , algorithm , mathematics , statistical physics , physics , statistics , quantum mechanics , mechanical engineering , philosophy , epistemology , machine learning , acoustics , economics , programming language , economic growth , engineering
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 Θ(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 (log log n ) and ${\cal 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. © 2000 John Wiley & Sons, Inc. Random Struct. Alg., 17: 238–259, 2000