Portal de Periódicos da CAPES

Delayed path coupling and generating random permutations

2000; Wiley; Volume: 17; Issue: 3-4 Linguagem: Inglês

10.1002/1098-2418(200010/12)17

1098-2418

Artur Czumaj, Miros aw Kuty owski,

Random Matrices and Applications

Random Structures & AlgorithmsVolume 17, Issue 3-4 p. 238-259 Delayed path coupling and generating random permutations † Artur Czumaj, Artur Czumaj [email protected] Department of Computer and Information Science, New Jersey Institute of Technology, Newark, NJ 07102Search for more papers by this authorMirosław Kutyłowski, Corresponding Author Mirosław Kutyłowski [email protected] Department of Mathematics and Computer Science, University of Poznań, Matejki 48/49, PL-60-769 Poznań, PolandDepartment of Mathematics and Computer Science, University of Poznań, Matejki 48/49, PL-60-769 Poznań, PolandSearch for more papers by this author Artur Czumaj, Artur Czumaj [email protected] Department of Computer and Information Science, New Jersey Institute of Technology, Newark, NJ 07102Search for more papers by this authorMirosław Kutyłowski, Corresponding Author Mirosław Kutyłowski [email protected] Department of Mathematics and Computer Science, University of Poznań, Matejki 48/49, PL-60-769 Poznań, PolandDepartment of Mathematics and Computer Science, University of Poznań, Matejki 48/49, PL-60-769 Poznań, PolandSearch for more papers by this author First published: 03 November 2000 https://doi.org/10.1002/1098-2418(200010/12)17:3/4 3.0.CO;2-ECitations: 15 † Part of this work was done while the authors were with the University of Paderborn and the second author was with the University of Wrocław. Research partially supported by KBN grant 8 T11C 032 15, ALCOM EU ESPRIT Long Term Research Project 20244 (ALCOM-IT), DFG-Sonderforschungsbereich 376 "Massive Parallelität", and DFG Leibniz Grant Me872/6-1. A preliminary report on this research appeared in Delayed path coupling and generating random permutations via distributed stochastic processes, A. Czumaj, P. Kanarek, M. Kutyłowski, and K. Loryś, Proceedings of the 10th ACM-SIAM Symposium on Discrete Algorithms, pp. 271–280, SIAM, 1999 AboutPDF ToolsRequest permissionExport citationAdd to favoritesTrack citation ShareShare Give accessShare full text accessShare full-text accessPlease review our Terms and Conditions of Use and check box below to share full-text version of article.I have read and accept the Wiley Online Library Terms and Conditions of UseShareable LinkUse the link below to share a full-text version of this article with your friends and colleagues. Learn more.Copy URL Share a linkShare onEmailFacebookTwitterLinkedInRedditWechat Abstract 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 , 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 References 1 D. Aldous, " Random walks of finite groups and rapidly mixing Markov chains," in Séminaire de Probabilités XVII, 1981/82, Volume 986 of Lecture Notes in Mathematics, J. Azéma and M. Yor (Editors), Springer-Verlag, Berlin, 1983, pp. 243–297. 2 D. Aldous and P. Diaconis, Shuffling cards and stopping times, Am Math Month 93 ( 1986), 333–347. 3 R. Anderson, " Parallel algorithms for generating random permutations on a shared memory machine," in Proceedings of the 2nd Annual ACM Symposium on Parallel Algorithms and Architectures, Island of Crete, Greece, 2–6 July 1990. ACM Press, New York, NY, 1990, pp. 95–102. 4 R.J. Anderson and G.L. Miller, Optical communication for pointer based algorithms, Tech. Rep. CRI 88-14, University of Southern California, 1988. 5 R. Bubley and M. Dyer, " Path coupling: A technique for proving rapid mixing in Markov chains," in Proceedings of the 38th Symposium on Foundations of Computer Science, Miami Beach, FL, 19–22 October 1997. IEEE Computer Society Press, Los Alamitos, CA, pp. 223–231. 6 R. Bubley and M. Dyer, " Faster random generation of linear extensions," in Proceedings of the 9th ACM-SIAM Symposium on Discrete Algorithms, San Francisco, CA, 25–27 January 1998. SIAM, Philadelphia, PA, pp. 355–363. 7 R. Bubley, M. Dyer, and C. Greenhill, " Beating the 2Δ bound for approximately counting colourings: A computer-assisted proof of rapid mixing," in Proceedings of the 9th ACM-SIAM Symposium on Discrete Algorithms, San Francisco, CA, 25–27 January 1998. SIAM, Philadelphia, PA, pp. 355–363. 8 A. Czumaj, " Recovery time of dynamic allocation processes," in Proceedings of the 10th Annual ACM Symposium on Parallel Algorithms and Architectures, Puerto Vallarta, Mexico, 28 June–2 July 1998. ACM Press, New York, NY, pp. 202–211. 9 A. Czumaj, P. Kanarek, M. Kutyłowski, and K. Loryś, Fast generation of random permutations via network simulation, Algorithmica, 21( 1) ( 1998) 2–20. A preliminary version appeared in Proceedings of the 4th Annual European Symposium on Algorithms, Volume 1136 of Lecture Notes in Computer Science, Barcelona, Spain, 25–27 September 1996, J. Diaz and M. Serna (Editors), Springer-Verlag, Berlin, pp. 246–260. 10 A. Czumaj, P. Kanarek, M. Kutyłowski, and K. Loryś, " Delayed path coupling and generating random permutations via distributed stochastic processes," in Proceedings of the 10th ACM-SIAM Symposium on Discrete Algorithms, Baltimore, MD, 17–19 January 1999, SIAM, Philadelphia, PA, pp. 271–280. 11 P. Diaconis, Group Representations in Probability and Statistics, Volume 11 of Lecture Notes-Monograph Series. Institute of Mathematical Statistics, Hayward, CA, 1988. 12 P. Diaconis, M. Mc Grath, and J. Pitman, Riffle shuffles, cycles, and descents, Combinatorica, 15( 1) ( 1995), 11–29. 13 P. Diaconis and M. Shahshahani, Generating a random permutation with random transpositions, Zeitschrift Wahrscheinlichkeitstheorie verwandte Gebiete, 57 ( 1981), 159–179. 14 M. Dyer, A. Frieze, and R. Kannan, A random polynomial-time algorithm for approximating the volume of convex bodies, J ACM 38( 1) ( 1991), 1–17. A preliminary version appeared in Proceedings of the 21st ACM Symposium on Theory of Computing, Seattle, Washington, 15–17 May 1989, ACM Press, New York, NY, pp. 297–307. 15 M. Dyer and C. Greenhill, " A genuinely polynomial-time algorithm for sampling two-rowed contingency tables," in Proceedings of the 25th Annual International Colloquium on Automata, Languages and Programming, Volume 1443 of Lecture Notes in Computer Science, K.G. Larsen, S. Skyum, and G. Winskel (Editors), Aalborg, Denmark, 13–17 July 1998. Springer-Verlag, Berlin, pp. 339–350. 16 M. Dyer and C. Greenhill, A more rapidly mixing Markov chain for graph colourings, Ran Struct Algorith 13( 3–4) ( 1998), 285–317. 17 M. Dyer and C. Greenhill, " Random walks on combinatorial objects," in Surveys in Combinatorics, Volume 267 of London Mathematical Society Lecture Note Series, J.D. Lamb and D.A. Preece (Editors), Cambridge University Press, 1999, pp. 101–136. 18 P.B. Gibbons, Y. Matias, and V. Ramachandran, Efficient low-contention parallel algorithms, J Comput Syst Sci 53( 3) ( 1996), 417–442. A preliminary version appeared in Proceedings of the 6th ACM Symposium on Parallel Algorithms and Architectures, Padua, Italy, 24–26 June 1996, ACM Press, New York, NY, pp. 236–247. 19 P. Gibbons, Y. Matias, V. Ramachandran, The QRQW PRAM: Accounting for contention in parallel algorithms, SIAM J Comput 28( 2) ( 1999), 733–769. A preliminary version appeared in Proceedings of the 5th ACM Symposium on Discrete Algorithms, Philadelphia, PA, 23–25 January 1994, SIAM, Philadelphia, PA, pp. 638–648. 20 L.A. Goldberg, M. Jerrum, T. Leighton, and S. Rao, Doubly logarithmic communication algorithms for optical-communication parallel computers, SIAM J Comput 26( 4) ( 1997), 1100–1119. A preliminary version appeared in Proceedings of the 5th ACM Symposium on Parallel Algorithms and Architectures, Velen, Germany, 30 June–2 July 1993, ACM Press, New York, NY, pp. 300–309. 21 T. Hagerup, " Fast parallel generation of random permutations," in Proceedings of the 18th Annual International Colloquium on Automata, Languages and Programming, Volume 510 of Lecture Notes in Computer Science, J.L. Albert, B. Monien, and M. Rodriguez-Artalejo (Editors), Madrid, Spain, 8–12 July 1991, Springer-Verlag, Berlin, pp. 405–416. 22 M. Jerrum and A. Sinclair, " The Markov chain Monte Carlo method: An approach to approximate counting and integration," in Approximation Algorithms for 𝒩𝒫-Hard Problems, Chapter 12, D.S. Hochbaum (Editor), PWS Publishing Company, Boston, MA, 1996, pp. 482–520. 23 R. Kannan, " Markov chains and polynomial time algorithms," in Proceedings of the 35th Symposium on Foundations of Computer Science, Santa Fe, NM, 20–22 November 1994, IEEE Computer Society Press, Los Alamitos, CA, pp. 656–671. 24 T. Lindvall, Lectures on the Coupling Method, John Wiley & Sons, New York, NY, 1992. 25 Y. Matias and U. Vishkin, " Converting high probability into nearly-constant time—with applications to parallel hashing," in Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, New Orleans, LA, 6–8 May 1991, ACM Press, New York, NY, pp. 307–316. 26 G.L. Miller and J.H. Reif, " Parallel tree contraction," in Proceedings of the 26th Symposium on Foundations of Computer Science, Portland, OR, 21–23 October 1985, IEEE Computer Society Press, Los Alamitos, CA, pp. 478–489. 27 G.L. Miller and J.H. Reif, Parallel tree contraction, Part 1: Fundamentals, Adv Comput Res 5 ( 1989), 47–72. 28 R. Motwani and P. Raghavan, Randomized algorithms. Cambridge University Press, Cambridge, 1995. 29 C. Rackoff and D.R. Simon, " Cryptographic defense against traffic analysis," in Proceedings of the 25th Annual ACM Symposium on Theory of Computing, San Diego, CA, 16–18 May 1993, ACM Press, New York, NY, pp. 672–681. 30 S. Rajasekaran and J.H. Reif, Optimal and sublogarithmic time randomized parallel sorting algorithms, SIAM J Comput 19 ( 1989), 594–607. 31 J.H. Reif, " An optimal parallel algorithm for integer sorting," in Proceedings of the 26th Symposium on Foundations of Computer Science, Portland, OR, 21–23 October 1985, IEEE Computer Society Press, Los Alamitos, CA, pp. 496–504. 32 A. Sinclair, Algorithms for Random Generation and Counting: A Markov Chain Approach, Birkhäuser, Boston, MA, 1993. 33 E. Vigoda, " Improved bounds for sampling colorings," in Proceedings of the 40th Symposium on Foundations of Computer Science, New York City, NY, 17–19 October 1999, IEEE Computer Society Press, Los Alamitos, CA. 34 M. Zito, I. Pu, M. Amos, and A. Gibbons, " ℛ𝒩𝒞 algorithms for the uniform generation of combinatorial structures," in Proceedings of the 7th ACM-SIAM Symposium on Discrete Algorithms, Atlanta, GA, 28–30 January 1996, SIAM, Philadelphia, PA, pp. 429–437. Citing Literature Volume17, Issue3-4Special Issue: Proceedings of the Ninth International Conference "Random Structures and Algorithms"October ‐ December 2000Pages 238-259 ReferencesRelatedInformation