Details

Autor(en) / Beteiligte

• Czumaj, Artur
• Kutyłowski, Mirosław

Titel

Delayed path coupling and generating random permutations

Ist Teil von

• Random structures & algorithms, 2000-10, Vol.17 (3-4), p.238-259

Ort / Verlag

New York: John Wiley & Sons, Inc

Erscheinungsjahr

2000

Link zum Volltext

Quelle

Wiley Online Library - AutoHoldings Journals

Beschreibungen/Notizen

• 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 O(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