{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,4]],"date-time":"2025-05-04T04:03:36Z","timestamp":1746331416444,"version":"3.40.4"},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662439470"},{"type":"electronic","value":"9783662439487"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-43948-7_29","type":"book-chapter","created":{"date-parts":[[2014,6,11]],"date-time":"2014-06-11T16:10:36Z","timestamp":1402503036000},"page":"344-355","source":"Crossref","is-referenced-by-count":5,"title":["Thorp Shuffling, Butterflies, and Non-Markovian Couplings"],"prefix":"10.1007","author":[{"given":"Artur","family":"Czumaj","sequence":"first","affiliation":[]},{"given":"Berthold","family":"V\u00f6cking","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"29_CR1","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1007\/BFb0068322","volume-title":"S\u00e9minaire de Probabilit\u00e9s XVII, 1981\/82","author":"D. Aldous","year":"1983","unstructured":"Aldous, D.: Random walks of finite groups and rapidly mixing Markov chains. In: S\u00e9minaire de Probabilit\u00e9s XVII, 1981\/82, pp. 243\u2013297. Springer, Berlin (1983)"},{"key":"29_CR2","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/0196-8858(87)90006-6","volume":"8","author":"D. Aldous","year":"1987","unstructured":"Aldous, D., Diaconis, P.: Strong uniform times and finite random walks. Advances in Applied Mathematics\u00a08, 69\u201397 (1987)","journal-title":"Advances in Applied Mathematics"},{"issue":"6","key":"29_CR3","doi-asserted-by":"publisher","first-page":"1350","DOI":"10.1137\/S009753970444435X","volume":"35","author":"P. Berenbrink","year":"2006","unstructured":"Berenbrink, P., Czumaj, A., Steger, A., V\u00f6cking, B.: Balanced allocations: The heavily loaded case. SIAM Journal on Computing\u00a035(6), 1350\u20131385 (2006)","journal-title":"SIAM Journal on Computing"},{"key":"29_CR4","doi-asserted-by":"crossref","unstructured":"Bubley, R., Dyer, M.: Path coupling: A technique for proving rapid mixing in Markov chains. In: 38th IEEE FOCS, pp. 223\u2013231 (1997)","DOI":"10.1109\/SFCS.1997.646111"},{"key":"29_CR5","unstructured":"Czumaj, A., Kanarek, P., Kuty\u0142owski, M., Lory\u015b, K.: Delayed path coupling and generating random permutations via distributed stochastic processes. In: SODA, pp. 271\u2013280 (1999)"},{"issue":"3-4","key":"29_CR6","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1002\/1098-2418(200010\/12)17:3\/4<238::AID-RSA4>3.0.CO;2-E","volume":"17","author":"A. Czumaj","year":"2000","unstructured":"Czumaj, A., Kuty\u0142owski, M.: Delayed path coupling and generating random permutations. Random Structures and Algorithms\u00a017(3-4), 238\u2013259 (2000)","journal-title":"Random Structures and Algorithms"},{"key":"29_CR7","series-title":"Lecture Notes - Monograph Series","doi-asserted-by":"crossref","DOI":"10.1007\/BFb0086177","volume-title":"Group Representations in Probability and Statistics","author":"P. Diaconis","year":"1988","unstructured":"Diaconis, P.: Group Representations in Probability and Statistics. Lecture Notes - Monograph Series, vol.\u00a011. Institute of Mathematical Statistics, Hayward (1988)"},{"key":"29_CR8","first-page":"101","volume-title":"Surveys in Combinatorics","author":"M. Dyer","year":"1999","unstructured":"Dyer, M., Greenhill, C.: Random walks on combinatorial objects. In: Surveys in Combinatorics, pp. 101\u2013136. Cambridge University Press, UK (1999)"},{"key":"29_CR9","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/BF00539434","volume":"31","author":"D. Griffeath","year":"1975","unstructured":"Griffeath, D.: A maximal coupling for Markov chains. Zeitschrift f\u00fcr Wahrscheinlichkeitstheorie und verwandte Gebiete\u00a031, 95\u2013106 (1975)","journal-title":"Zeitschrift f\u00fcr Wahrscheinlichkeitstheorie und verwandte Gebiete"},{"key":"29_CR10","doi-asserted-by":"publisher","first-page":"466","DOI":"10.1002\/rsa.20131","volume":"29","author":"J. H\u00e5stad","year":"2006","unstructured":"H\u00e5stad, J.: The square lattice shuffle. Random Struct. and Algorithms\u00a029, 466\u2013474 (2006)","journal-title":"Random Struct. and Algorithms"},{"key":"29_CR11","doi-asserted-by":"crossref","unstructured":"Hayes, T.P., Vigoda, E.: A non-Markovian coupling for randomly sampling colorings. In: 44th IEEE FOCS, pp. 618\u2013627 (2003)","DOI":"10.1109\/SFCS.2003.1238234"},{"key":"29_CR12","doi-asserted-by":"crossref","unstructured":"Jerrum, M.: Mathematical foundations of the Markov chain Monte Carlo method. In: Probabilistic Methods for Algorithmic Discrete Mathematics, pp. 116\u2013165. Springer (1998)","DOI":"10.1007\/978-3-662-12788-9_4"},{"key":"29_CR13","unstructured":"Knuth, D.E.: The Art of Computer Programming, Volume 3: Sorting and Searching. Section 5.3.4: Networks for Sorting, 3rd edn., pp. 219\u2013247. Addison-Wesley (1997)"},{"issue":"3","key":"29_CR14","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1561\/0400000003","volume":"1","author":"R. Montenegro","year":"2006","unstructured":"Montenegro, R., Tetali, P.: Mathematical aspects of mixing times in Markov chains. Foundations and Trends in Theoretical Computer Science\u00a01(3), 237\u2013354 (2006)","journal-title":"Foundations and Trends in Theoretical Computer Science"},{"key":"29_CR15","doi-asserted-by":"crossref","unstructured":"Morris, B.: The mixing time of the Thorp shuffle. In: 37th ACM STOC, pp. 403\u2013412 (2005)","DOI":"10.1145\/1060590.1060651"},{"issue":"2","key":"29_CR16","doi-asserted-by":"publisher","first-page":"484","DOI":"10.1137\/050636231","volume":"38","author":"B. Morris","year":"2008","unstructured":"Morris, B.: The mixing time of the Thorp shuffle. SIAM Journal on Computing\u00a038(2), 484\u2013504 (2008); This is the full, corrected, and updated version of [15]","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"29_CR17","doi-asserted-by":"publisher","first-page":"453","DOI":"10.1214\/08-AOP409","volume":"37","author":"B. Morris","year":"2009","unstructured":"Morris, B.: Improved mixing time bounds for the Thorp shuffle and L-reversal chain. Annals of Probabability\u00a037(2), 453\u2013477 (2009)","journal-title":"Annals of Probabability"},{"key":"29_CR18","doi-asserted-by":"crossref","unstructured":"Morris, B.: Improved mixing time bounds for the Thorp shuffle. arXiv 0912.2759 (2009)","DOI":"10.1214\/08-AOP409"},{"key":"29_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"286","DOI":"10.1007\/978-3-642-03356-8_17","volume-title":"Advances in Cryptology - CRYPTO 2009","author":"B. Morris","year":"2009","unstructured":"Morris, B., Rogaway, P., Stegers, T.: How to Encipher Messages on a Small Domain. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol.\u00a05677, pp. 286\u2013302. Springer, Heidelberg (2009)"},{"key":"29_CR20","doi-asserted-by":"crossref","unstructured":"Rackoff, C., Simon, D.R.: Cryptographic defense against traffic analysis. In: 25th ACM STOC, pp. 672\u2013681 (1993)","DOI":"10.1145\/167088.167260"},{"key":"29_CR21","doi-asserted-by":"publisher","first-page":"842","DOI":"10.1080\/01621459.1973.10481434","volume":"68","author":"E.O. Thorp","year":"1973","unstructured":"Thorp, E.O.: Nonrandom shuffling with applications to the game of Faro. Journal of the American Statistical Association\u00a068, 842\u2013847 (1973)","journal-title":"Journal of the American Statistical Association"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-43948-7_29","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,3]],"date-time":"2025-05-03T09:31:04Z","timestamp":1746264664000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-43948-7_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662439470","9783662439487"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-43948-7_29","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}