{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T00:13:29Z","timestamp":1784160809967,"version":"3.55.0"},"reference-count":74,"publisher":"Emerald","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006,1,15]]},"abstract":"<jats:p>In the past few years we have seen a surge in the theory of finite Markov chains, by way of new techniques to bounding the convergence to stationarity. This includes functional techniques such as logarithmic Sobolev and Nash inequalities, refined spectral and entropy techniques, and isoperimetric techniques such as the average and blocking conductance and the evolving set methodology. We attempt to give a more or less self-contained treatment of some of these modern techniques, after reviewing several preliminaries. We also review classical and modern lower bounds on mixing times. There have been other important contributions to this theory such as variants on coupling techniques and decomposition methods, which are not included here; our choice was to keep the analytical methods as the theme of this presentation. We illustrate the strength of the main techniques by way of simple examples, a recent result on the Pollard Rho random walk to compute the discrete logarithm, as well as with an improved analysis of the Thorp shuffle.<\/jats:p>","DOI":"10.1561\/0400000003","type":"journal-article","created":{"date-parts":[[2006,6,2]],"date-time":"2006-06-02T08:46:34Z","timestamp":1149237994000},"page":"237-354","source":"Crossref","is-referenced-by-count":165,"title":["Mathematical Aspects of Mixing Times in Markov Chains"],"prefix":"10.1108","volume":"1","author":[{"given":"Ravi","family":"Montenegro","sequence":"first","affiliation":[{"name":"University of Massachusetts Lowell , Lowell, Massachusetts 01854,","place":["USA"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Prasad","family":"Tetali","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology , Atlanta, Georgia 30332,","place":["USA"]}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"140","published-online":{"date-parts":[[2006,1,15]]},"reference":[{"key":"2026041706435012400_ref001","unstructured":"D. J.\n              Aldous\n             and J.Fill, Reversible Markov Chains and Random Walks on Graphs, (book to appear). URL for draft at http:\/\/stat-www.berkeley.edu\/users\/aldous\/RWG\/book.html."},{"key":"2026041706435012400_ref002","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1007\/s000390050062","article-title":"An asymptotic isoperimetric inequality","volume":"8","author":"Alon","year":"1998","journal-title":"Geom. and Funct. Anal."},{"key":"2026041706435012400_ref003","first-page":"177","volume-title":"S\u00e9minaire de Proba- bilit\u00e9s XIX, Lecture Notes in Math. 1123","author":"Bakry","year":"1985"},{"key":"2026041706435012400_ref004","doi-asserted-by":"crossref","first-page":"609","DOI":"10.1007\/s002220100139","article-title":"Manifolds and graphs with slow heat kernel decay","volume":"144","author":"Barlow","year":"2001","journal-title":"Invent. Math."},{"key":"2026041706435012400_ref005","doi-asserted-by":"crossref","first-page":"776","DOI":"10.1090\/S0002-9904-1946-08647-4","article-title":"Vector fields and Ricci Curvature","volume":"52","author":"Bochner","year":"1946","journal-title":"Bull. Amer. Math. Soc."},{"key":"2026041706435012400_ref006","volume-title":"Statistical Physics Expansion Methods in Combinatorics and Computer Science","author":"Borgs"},{"key":"2026041706435012400_ref007","first-page":"218","article-title":"Torpid mixing of some MCMC algorithms in statistical physics","volume-title":"Proceedings of the 40th IEEE Symposium on Foundations of Computer Science (FOCS)","author":"Borgs","year":"1999"},{"key":"2026041706435012400_ref008","doi-asserted-by":"crossref","first-page":"222","DOI":"10.1016\/j.jfa.2005.07.012","article-title":"Spectral gap estimates for interacting particle systems via a Bochner type identity","volume":"232","author":"Boudou","year":"2005","journal-title":"Journal of Functional Analysis"},{"issue":"1","key":"2026041706435012400_ref009","doi-asserted-by":"crossref","first-page":"70","DOI":"10.1080\/00029890.2006.11920281","article-title":"Fastest mixing Markov chain on a path","volume":"113","author":"Boyd","year":"2006","journal-title":"The American Mathematical Monthly"},{"issue":"4","key":"2026041706435012400_ref010","doi-asserted-by":"crossref","first-page":"667","DOI":"10.1137\/S0036144503423264","article-title":"Fastest mixing Markov chain on a graph","volume":"46","author":"Boyd","year":"2004","journal-title":"SIAM Review"},{"key":"2026041706435012400_ref011","volume-title":"Walks, Transpositions, and Exclusion","author":"Caputo","year":"2004"},{"issue":"1","key":"2026041706435012400_ref012","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s00026-005-0237-z","article-title":"Laplacians and the Cheeger inequality for directed graphs","volume":"9","author":"Chung","year":"2005","journal-title":"Annals of Combinatorics"},{"key":"2026041706435012400_ref013","doi-asserted-by":"crossref","first-page":"510","DOI":"10.1006\/jfan.1996.0140","article-title":"Ultracontractivity and Nash-type inequalities","volume":"141","author":"Coulhon","year":"1996","journal-title":"J. Funct. Anal."},{"key":"2026041706435012400_ref014","doi-asserted-by":"crossref","first-page":"1763","DOI":"10.5802\/aif.1874","article-title":"A geometric approach to on- diagonal heat kernel lower bound on groups","volume":"51","author":"Coulhon","year":"2001","journal-title":"Ann. Inst. Fourier"},{"key":"2026041706435012400_ref015","volume-title":"Elements of Information Theory","author":"Cover","year":"1991"},{"key":"2026041706435012400_ref016","first-page":"413","article-title":"Approximately Counting Integral Flows and Cell-Bounded Contingency Tables","volume-title":"Proc. of the 37th Annual ACM Symp. on Theory of Computing (STOC)","author":"Cryan","year":"2005"},{"key":"2026041706435012400_ref017","volume-title":"Large Deviations","author":"Deuschel","year":"1989"},{"issue":"4","key":"2026041706435012400_ref018","doi-asserted-by":"crossref","first-page":"1483","DOI":"10.1214\/aop\/1176990628","article-title":"Strong stationary times via a new form of duality","volume":"18","author":"Diaconis","year":"1990","journal-title":"The Annals of Probability"},{"issue":"3","key":"2026041706435012400_ref019","doi-asserted-by":"crossref","first-page":"726","DOI":"10.1214\/aoap\/1019487508","article-title":"Analysis of a Non-reversible Markov Chain Sampler","volume":"10","author":"Diaconis","year":"2000","journal-title":"Annals of Applied Probability"},{"issue":"3","key":"2026041706435012400_ref020","doi-asserted-by":"crossref","first-page":"696","DOI":"10.1214\/aoap\/1177005359","article-title":"Comparison Theorems for Reversible Markov Chains","volume":"3","author":"Diaconis","year":"1993","journal-title":"The Annals of Applied Probability"},{"issue":"3","key":"2026041706435012400_ref021","doi-asserted-by":"crossref","first-page":"695","DOI":"10.1214\/aoap\/1034968224","article-title":"Logarithmic Sobolev inequalities for finite Markov chains","volume":"6","author":"Diaconis","year":"1996","journal-title":"The Annals of Applied Probability"},{"key":"2026041706435012400_ref022","doi-asserted-by":"crossref","first-page":"459","DOI":"10.1007\/BF02214660","article-title":"Nash Inequalities for Finite Markov Chains","volume":"9","author":"Diaconis","year":"1996","journal-title":"Journal of Theoretical Probability"},{"issue":"1","key":"2026041706435012400_ref023","doi-asserted-by":"crossref","first-page":"208","DOI":"10.1137\/0518016","article-title":"Time to reach","volume":"18","author":"Diaconis","year":"1987","journal-title":"SIAM J. Math. Anal."},{"key":"2026041706435012400_ref024","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1214\/aoap\/1177005980","article-title":"Geometric bounds for eigenvalues of Markov chains","volume":"1","author":"Diaconis","year":"1991","journal-title":"The Annals of Applied Probability"},{"key":"2026041706435012400_ref025","volume-title":"Markov chain comparison","author":"Dyer","year":"2005"},{"issue":"1","key":"2026041706435012400_ref026","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1214\/aoap\/1177005981","article-title":"Eigenvalue bounds on convergence to stationarity for nonreversible Markov chains, with an application to the exclusion process","volume":"1","author":"Fill","year":"1991","journal-title":"The Annals of Applied Probability"},{"key":"2026041706435012400_ref027","volume-title":"The evolution of the conductance of a random graph","author":"Fountoulakis"},{"key":"2026041706435012400_ref028","article-title":"Survey of Markov Chains for Randomly Sampling Colorings","volume-title":"To appear in Festschrift for Dominic Welsh","author":"Frieze","year":"2006"},{"issue":"1","key":"2026041706435012400_ref029","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1214\/10505160500000062","article-title":"Analysis of top to bottom-k shuffles","volume":"16","author":"Goel","year":"2006","journal-title":"The Annals of Applied Probability"},{"key":"2026041706435012400_ref030","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1214\/EJP.v11-300","article-title":"Mixing time bounds and the spectral profile","volume":"11","author":"Goel","year":"2006","journal-title":"Electronic Journal of Probability"},{"key":"2026041706435012400_ref031","doi-asserted-by":"crossref","first-page":"395","DOI":"10.4171\/rmi\/157","article-title":"Heat kernel upper bounds on a complete non-compact manifold","volume":"10","author":"Grigor\u2019yan","year":"1994","journal-title":"Revista Matema,tica Iberoamericana"},{"key":"2026041706435012400_ref032","doi-asserted-by":"crossref","first-page":"116","DOI":"10.1007\/978-3-662-12788-9_4","volume-title":"Probabilistic Methods for Algorithmic Discrete Mathematics","author":"Jerrum","year":"1998"},{"key":"2026041706435012400_ref033","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-0348-8005-3","volume-title":"Counting, Sampling and Integrating : Algorithms & Complexity","author":"Jerrum","year":"2003"},{"key":"2026041706435012400_ref034","first-page":"235","article-title":"Conductance and the rapid mixing property for Markov chains: the approximation of the permanent resolved","volume-title":"Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC 1988)","author":"Jerrum","year":"1988"},{"key":"2026041706435012400_ref035","volume-title":"Approximation Algorithms for NP-hard Problems","author":"Jerrum","year":"1996"},{"key":"2026041706435012400_ref036","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1145\/1008731.1008738","article-title":"A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries","volume":"51","author":"Jerrum","year":"2004","journal-title":"Journal of the ACM"},{"key":"2026041706435012400_ref037","doi-asserted-by":"crossref","first-page":"721","DOI":"10.1109\/SFCS.2002.1181997","article-title":"Spectral Gap and log-Sobolev constant for balanced matroids","volume-title":"Proc. of the 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2002)","author":"Jerrum","year":"2002"},{"key":"2026041706435012400_ref038","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/0304-3975(86)90174-X","article-title":"Random generation of combinatorial structures from a uniform distribution","volume":"43","author":"Jerrum","year":"1998","journal-title":"Theoretical Computer Science"},{"key":"2026041706435012400_ref039","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1090\/conm\/026\/737400","article-title":"Extensions of Lipschitz maps into a Hilbert space","volume":"26","author":"Johnson","year":"1984","journal-title":"Contemp. Math."},{"key":"2026041706435012400_ref040","first-page":"656","article-title":"Markov chains and polynomial time algorithms","volume-title":"Plenary Talk at Proc. of 35th Annual IEEE Symp. on the Foundations of Computer Science","author":"Kannan","year":"1994"},{"key":"2026041706435012400_ref041","doi-asserted-by":"crossref","DOI":"10.1017\/S0963548306007504","article-title":"Blocking conductance and mixing in random walks","volume-title":"Combinatorics, Probability and Computing","author":"Kannan","year":"2006"},{"key":"2026041706435012400_ref042","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1016\/0024-3795(81)90003-3","article-title":"Bounds for eigenvalues of certain stochastic matrices","volume":"38","author":"Landau","year":"1981","journal-title":"Linear Algebra Appl."},{"key":"2026041706435012400_ref043","first-page":"557","article-title":"Bounds on the L2 spectrum for Markov chains and Markov processes: a generalization of Cheeger\u2019s inequality","volume":"309","author":"Lawler","year":"1988","journal-title":"Transactions of the American Mathematical Society"},{"issue":"4","key":"2026041706435012400_ref044","doi-asserted-by":"crossref","first-page":"1855","DOI":"10.1214\/aop\/1022855885","article-title":"Logarithmic Sobolev inequalities for some models of random walks","volume":"26","author":"Lee","year":"1998","journal-title":"The Annals of Probability"},{"key":"2026041706435012400_ref045","volume-title":"G\u00e9om\u00e9trie des groupes de transformations","author":"Lichn\u00e9rowicz","year":"1958"},{"key":"2026041706435012400_ref046","first-page":"282","article-title":"Faster mixing via average conductance","volume-title":"Proc. of the 31st Annual ACM Symp. on Theory of Computing","author":"Lovasz","year":"1999"},{"key":"2026041706435012400_ref047","article-title":"Simulated annealing in convex bodies and an O \u2217 (n4) volume algorithm","volume-title":"Proc. of the 44th IEEE Found. of Computer Science, Boston","author":"Lovasz","year":"2003"},{"issue":"4","key":"2026041706435012400_ref048","first-page":"985","article-title":"Hit-and-run from a corner","volume":"35","author":"Lovasz","year":"2006","journal-title":"Proc. of the 36th ACM Symp. on the Theory of Computing, Chicago, SIAM J. Computing (STOC \u201804 special issue)"},{"key":"2026041706435012400_ref049","doi-asserted-by":"crossref","first-page":"136","DOI":"10.1007\/BFb0119300","article-title":"Remarques sur l\u2019hypercontractivit\u00e9 et l\u2019\u00e9volution de l\u2019entropie pour des cha\u00eenes de Markov finies","volume":"31","author":"Miclo","year":"1997","journal-title":"S\u00e9minaire de probabilit\u00e9s de Strasbourg"},{"key":"2026041706435012400_ref050","doi-asserted-by":"crossref","first-page":"526","DOI":"10.1109\/SFCS.1989.63529","article-title":"Conductance and Convergence of Markov Chains-A Combinatorial Treatment of Expanders","volume-title":"Proc. of the 30th Annual Symposium on Foundations of Computer Science","author":"Mihail","year":"1989"},{"key":"2026041706435012400_ref051","volume-title":"Proc. of the 7th Algorithmic Number Theory Symposium (ANTS VII) in series Lecture Notes in Computer Science (LNCS)","author":"Miller","year":"2006"},{"key":"2026041706435012400_ref052","doi-asserted-by":"crossref","first-page":"970","DOI":"10.1239\/jap\/1067436094","article-title":"Stability and exponential convergence of continuous-time Markov chains","volume":"40","author":"Mitrophanov","year":"2003","journal-title":"J. Appl. Probab."},{"key":"2026041706435012400_ref053","doi-asserted-by":"crossref","first-page":"1003","DOI":"10.1239\/jap\/1134587812","article-title":"Sensitivity and convergence of uniformly ergodic Markov chains","volume":"42","author":"Mitrophanov","year":"2005","journal-title":"J. Appl. Probab."},{"key":"2026041706435012400_ref054","doi-asserted-by":"crossref","first-page":"632","DOI":"10.1239\/jap\/1127322017","article-title":"Sensitivity of hidden Markov models","volume":"42","author":"Mitrophanov","year":"2005","journal-title":"J. Appl. Probab."},{"issue":"1\u20132","key":"2026041706435012400_ref055","first-page":"52","article-title":"Vertex and edge expansion properties for rapid mixing","volume":"26","author":"Montenegro","journal-title":"Random Structures & Algorithms"},{"key":"2026041706435012400_ref056","volume-title":"Duality and evolving set bounds on mixing times","author":"Montenegro","year":"2006"},{"key":"2026041706435012400_ref057","volume-title":"Eigenvalues of non-reversible Markov chains: their connection to mixing times, reversible Markov chains, and Cheeger inequalities","author":"Montenegro","year":"2006"},{"key":"2026041706435012400_ref058","volume-title":"On the mixing time of the simple random walk and max-degree walk on a directed graph","author":"Montenegro","year":"2006"},{"key":"2026041706435012400_ref059","doi-asserted-by":"crossref","DOI":"10.1214\/105051605000000728","article-title":"The mixing time for simple exclusion","volume-title":"Annals of Applied Probability","author":"Morris","year":"2006"},{"key":"2026041706435012400_ref060","article-title":"The mixing time of the Thorp shuffle","volume-title":"SIAM Journal on Computing (SICOMP)","author":"Morris","year":"2006"},{"issue":"2","key":"2026041706435012400_ref061","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1007\/s00440-005-0434-7","article-title":"Evolving sets, mixing and heat kernel bounds","volume":"133","author":"Morris","year":"2005","journal-title":"Probability Theory and Related Fields"},{"key":"2026041706435012400_ref062","volume-title":"The Fastest Mixing Markov Process and the Subgaussian Constant","author":"Naor","year":"2005"},{"key":"2026041706435012400_ref063","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511810633","volume-title":"Markov Chains","author":"Norris","year":"1997"},{"key":"2026041706435012400_ref064","doi-asserted-by":"crossref","first-page":"825","DOI":"10.1214\/EJP.v9-198","article-title":"Mixing times for random walks on finite lamplighter groups","volume":"9","author":"Peres","year":"2004","journal-title":"Electronic J. on Probab."},{"issue":"2","key":"2026041706435012400_ref065","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1109\/MCSE.2006.30","article-title":"Rapidly mixing Markov chains with applications in computer science and physics","volume":"8","author":"Randall","year":"2006","journal-title":"Computing in Science & Engineering"},{"key":"2026041706435012400_ref066","doi-asserted-by":"crossref","first-page":"1598","DOI":"10.1063\/1.533199","article-title":"Analyzing Glauber dynamics using comparison of Markov chains","volume":"41","author":"Randall","year":"2000","journal-title":"J. Math. Physics"},{"key":"2026041706435012400_ref067","volume-title":"Methods of Modern Mathematical Physics II: Fourier Analysis, Self-Adjointness","author":"Reed","year":"1975"},{"key":"2026041706435012400_ref068","doi-asserted-by":"crossref","first-page":"515","DOI":"10.1515\/9783110198089.2.515","volume-title":"Random walks and geometry","author":"Saloff-Coste","year":"2004"},{"key":"2026041706435012400_ref069","doi-asserted-by":"crossref","first-page":"576","DOI":"10.2307\/1426955","article-title":"Coefficients of ergodicity: structure and applications","volume":"11","author":"Seneta","year":"1979","journal-title":"Adv. Appl. Prob."},{"issue":"4","key":"2026041706435012400_ref070","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1017\/S0963548300000390","article-title":"Improved bounds for mixing rates of Markov chains and multicommodity flow","volume":"1","author":"Sinclair","year":"1992","journal-title":"Combinatorics, Probability and Computing"},{"key":"2026041706435012400_ref071","doi-asserted-by":"crossref","first-page":"482","DOI":"10.1090\/S0002-9947-1956-0082586-0","article-title":"Interpolation of Linear Operators","volume":"83","author":"Stein","year":"1956","journal-title":"Trans. Amer. Math. Soc."},{"key":"2026041706435012400_ref072","doi-asserted-by":"crossref","DOI":"10.1137\/S0036144504443821","article-title":"The fastest mixing Markov process on a graph and a connection to a maximum variance unfolding problem","volume-title":"SIAM Review","author":"Sun","year":"2006"},{"issue":"77\u201385","key":"2026041706435012400_ref073","article-title":"Mixing Time of the Rudvalis Shuffle","volume":"8","author":"Wilson","year":"2003","journal-title":"Electronic Communications in Probability"},{"issue":"1","key":"2026041706435012400_ref074","doi-asserted-by":"crossref","first-page":"274","DOI":"10.1214\/aoap\/1075828054","article-title":"Mixing times of lozenge tiling and card shuffling Markov chains","volume":"14","author":"Wilson","year":"2004","journal-title":"The Annals of Applied Probability"}],"container-title":["Foundations and Trends\u00ae in Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.emerald.com\/fttcs\/article-pdf\/1\/3\/237\/11524765\/0400000003en.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/www.emerald.com\/fttcs\/article-pdf\/1\/3\/237\/11524765\/0400000003en.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T19:01:15Z","timestamp":1777489275000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.emerald.com\/fttcs\/article\/1\/3\/237\/1360406\/Mathematical-Aspects-of-Mixing-Times-in-Markov"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,1,15]]},"references-count":74,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2006,1,15]]}},"URL":"https:\/\/doi.org\/10.1561\/0400000003","relation":{},"ISSN":["1551-305X","1551-3068"],"issn-type":[{"value":"1551-305X","type":"print"},{"value":"1551-3068","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,1,15]]}}}