{"id":{"repo_id":"cornell","oai_identifier":"oai:ecommons.cornell.edu:1813/3047"},"canonical_url":"https://search.ndltd.org/etd/cornell/oai:ecommons.cornell.edu:1813/3047","repository":{"repo_id":"cornell","name":"Cornell University","base_url":"https://ecommons.cornell.edu/server/oai/request"},"display":{"title":"The cutoff phenomenon for finite Markov Chains","abstract":"A card player may ask the following question: how many shuffles are needed to mix up a deck of cards? Mathematically, this question falls in the realm of the quantitative study of the convergence of finite Markov chains. Similar convergence rate questions for finite Markov chains are important in many fields including statistical physics, computer science, biology and more. In this dissertation, we discuss a behavior ---the cutoff phenomenon--- that is known to appear in many models. For these models, after a waiting period, the chain abruptly converges to its stationary distribution. Our aim is to develop a theory of this phenomenon and to illustrate this theory with interesting examples. We focus on the case when the convergence is measured at the $\\ell^p$-distance for $1\\le p\\le\\infty$. For $p=1$, one recovers the classical total variation distance. One of the main result of the thesis is that for families of reversible Markov chains and $1<p\\le\\infty$, the existence of an $\\ell^p$-cutoff can be characterized using two parameters: the spectral gap and the mixing time. This fails when $p=1$. The notion of cutoff for a family of Markov chains indexed by $n$ involves a cutoff time sequence $(t_n)_1^\\infty$ and window size sequence $(b_n)_1^\\infty$. Ideally, when a cutoff exists, we would like to determine precisely $t_n$ and $b_n$. When $p=2$, spectral theory allows for a deeper analysis of the cutoff phenomenon producing in some cases the asymptotic behavior of the sequences $(t_n)_1^\\infty$ and $(b_n)_1^\\infty$. Throughout the thesis, examples are provided to illustrate the theoretical results. In particular, the last chapter is devoted to the study of the cutoff for the randomized riffle shuffle.","abstract_html":"A card player may ask the following question: how many shuffles are needed to mix up a deck of cards? Mathematically, this question falls in the realm of the quantitative study of the convergence of finite Markov chains. Similar convergence rate questions for finite Markov chains are important in many fields including statistical physics, computer science, biology and more. In this dissertation, we discuss a behavior ---the cutoff phenomenon--- that is known to appear in many models. For these models, after a waiting period, the chain abruptly converges to its stationary distribution. Our aim is to develop a theory of this phenomenon and to illustrate this theory with interesting examples. We focus on the case when the convergence is measured at the <span class=\"etd-inline-math\">\\ell<sup>p</sup></span>-distance for $1\\le p\\le\\infty$. For $p=1$, one recovers the classical total variation distance. One of the main result of the thesis is that for families of reversible Markov chains and $1&lt;p\\le\\infty$, the existence of an <span class=\"etd-inline-math\">\\ell<sup>p</sup></span>-cutoff can be characterized using two parameters: the spectral gap and the mixing time. This fails when $p=1$. The notion of cutoff for a family of Markov chains indexed by $n$ involves a cutoff time sequence <span class=\"etd-inline-math\">(t<sub>n</sub>)<sub>1</sub><sup>\\</sup>infty</span> and window size sequence <span class=\"etd-inline-math\">(b<sub>n</sub>)<sub>1</sub><sup>\\</sup>infty</span>. Ideally, when a cutoff exists, we would like to determine precisely <span class=\"etd-inline-math\">t<sub>n</sub></span> and <span class=\"etd-inline-math\">b<sub>n</sub></span>. When $p=2$, spectral theory allows for a deeper analysis of the cutoff phenomenon producing in some cases the asymptotic behavior of the sequences <span class=\"etd-inline-math\">(t<sub>n</sub>)<sub>1</sub><sup>\\</sup>infty</span> and <span class=\"etd-inline-math\">(b<sub>n</sub>)<sub>1</sub><sup>\\</sup>infty</span>. Throughout the thesis, examples are provided to illustrate the theoretical results. In particular, the last chapter is devoted to the study of the cutoff for the randomized riffle shuffle.","abstract_has_math":true,"creators":["Chen, Guan-Yu"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2006,"date_issued":"2006-05-24T17:43:53Z","date_published":"2006-05-24T17:43:53Z","updated_at":"2026-11-19T03:15:03Z","subjects":["Markov Chain","Cutoff phenomenon","Mixing time","Ergodicity","Markov semigroup"],"languages":["en"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier.bibid","label":"Dc Identifier Bibid","values":["6475842"],"render_values":[{"text":"6475842","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/1813/3047","outbound_label":"Handle","outbound_source":"dc:identifier.uri","record_url":"https://hdl.handle.net/1813/3047","record_label":"Repository record","record_kind":"handle","record_source":"dc:identifier.uri","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://ecommons.cornell.edu/server/oai/request?verb=GetRecord&metadataPrefix=dim&identifier=oai%3Aecommons.cornell.edu%3A1813%2F3047","prefix":"dim"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Chen, Guan-Yu"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2006-05-24T17:43:53Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2006-05-24T17:43:53Z"]},{"key":"dc:date.issued","label":"Date","values":["2006-05-24T17:43:53Z"]},{"key":"dc:type","label":"Dc Type","values":["dissertation or thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Markov Chain","Cutoff phenomenon","Mixing time","Ergodicity","Markov semigroup"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["en"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.bibid","label":"Dc Identifier Bibid","values":["6475842"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/1813/3047"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"cerif:openaire","label":"Cerif Openaire","values":["<Publication xmlns=\"https://www.openaire.eu/cerif-profile/1.1/\" id=\"70e66e76-16d1-44af-8ebf-2ee6f36d4365\"> <Type xmlns=\"https://www.openaire.eu/cerif-profile/vocab/COAR_Publication_Types\">http://purl.org/coar/resource_type/c_1843</Type> <Language>en</Language> <Title>The cutoff phenomenon for finite Markov Chains</Title> <PublishedIn> <Publication> </Publication> </PublishedIn> <PublicationDate>2006-05-24T17:43:53Z</PublicationDate> <Authors> <Author> <DisplayName>Chen, Guan-Yu</DisplayName> <Affiliation> <OrgUnit> </OrgUnit> </Affiliation> </Author> </Authors> <Editors> </Editors> <Publishers> <Publisher> <OrgUnit /> </Publisher> </Publishers> <Keyword>Markov Chain</Keyword> <Keyword>Cutoff phenomenon</Keyword> <Keyword>Mixing time</Keyword> <Keyword>Ergodicity</Keyword> <Keyword>Markov semigroup</Keyword> <Abstract>A card player may ask the following question: how many shuffles are needed to mix up a deck of cards? Mathematically, this question falls in the realm of the quantitative study of the convergence of finite Markov chains. Similar convergence rate questions for finite Markov chains are important in many fields including statistical physics, computer science, biology and more. In this dissertation, we discuss a behavior ---the cutoff phenomenon--- that is known to appear in many models. For these models, after a waiting period, the chain abruptly converges to its stationary distribution. Our aim is to develop a theory of this phenomenon and to illustrate this theory with interesting examples. We focus on the case when the convergence is measured at the $\\ell^p$-distance for $1\\le p\\le\\infty$. For $p=1$, one recovers the classical total variation distance. One of the main result of the thesis is that for families of reversible Markov chains and $1<p\\le\\infty$, the existence of an $\\ell^p$-cutoff can be characterized using two parameters: the spectral gap and the mixing time. This fails when $p=1$. The notion of cutoff for a family of Markov chains indexed by $n$ involves a cutoff time sequence $(t_n)_1^\\infty$ and window size sequence $(b_n)_1^\\infty$. Ideally, when a cutoff exists, we would like to determine precisely $t_n$ and $b_n$. When $p=2$, spectral theory allows for a deeper analysis of the cutoff phenomenon producing in some cases the asymptotic behavior of the sequences $(t_n)_1^\\infty$ and $(b_n)_1^\\infty$. Throughout the thesis, examples are provided to illustrate the theoretical results. In particular, the last chapter is devoted to the study of the cutoff for the randomized riffle shuffle.</Abstract> <Access xmlns=\"http://purl.org/coar/access_right\" > </Access> </Publication>"]},{"key":"cris:virtual.author","label":"Cris Virtual Author","values":["Chen, Guan-Yu"]},{"key":"cris:virtualsource.collection","label":"Cris Virtualsource Collection","values":["5893a6ea-7af3-41d7-abc6-04bcd26ab5df"]},{"key":"dc:description.abstract","label":"Abstract","values":["A card player may ask the following question: how many shuffles are needed to mix up a deck of cards? Mathematically, this question falls in the realm of the quantitative study of the convergence of finite Markov chains. Similar convergence rate questions for finite Markov chains are important in many fields including statistical physics, computer science, biology and more. In this dissertation, we discuss a behavior ---the cutoff phenomenon--- that is known to appear in many models. For these models, after a waiting period, the chain abruptly converges to its stationary distribution. Our aim is to develop a theory of this phenomenon and to illustrate this theory with interesting examples. We focus on the case when the convergence is measured at the $\\ell^p$-distance for $1\\le p\\le\\infty$. For $p=1$, one recovers the classical total variation distance. One of the main result of the thesis is that for families of reversible Markov chains and $1<p\\le\\infty$, the existence of an $\\ell^p$-cutoff can be characterized using two parameters: the spectral gap and the mixing time. This fails when $p=1$. The notion of cutoff for a family of Markov chains indexed by $n$ involves a cutoff time sequence $(t_n)_1^\\infty$ and window size sequence $(b_n)_1^\\infty$. Ideally, when a cutoff exists, we would like to determine precisely $t_n$ and $b_n$. When $p=2$, spectral theory allows for a deeper analysis of the cutoff phenomenon producing in some cases the asymptotic behavior of the sequences $(t_n)_1^\\infty$ and $(b_n)_1^\\infty$. Throughout the thesis, examples are provided to illustrate the theoretical results. In particular, the last chapter is devoted to the study of the cutoff for the randomized riffle shuffle."]},{"key":"dc:description.collection","label":"Dc Description Collection","values":["Cornell Theses and Dissertations"]},{"key":"dc:format.extent","label":"Dc Format Extent","values":["853059 bytes"]},{"key":"dc:format.mimetype","label":"Dc Format Mimetype","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["The cutoff phenomenon for finite Markov Chains"]},{"key":"dspace:entity.type","label":"Dspace Entity Type","values":["Publication"]},{"key":"others:access_status","label":"Others Access Status","values":["open.access"]}]}],"canonical_facts":{"cerif:openaire":["<Publication xmlns=\"https://www.openaire.eu/cerif-profile/1.1/\" id=\"70e66e76-16d1-44af-8ebf-2ee6f36d4365\"> <Type xmlns=\"https://www.openaire.eu/cerif-profile/vocab/COAR_Publication_Types\">http://purl.org/coar/resource_type/c_1843</Type> <Language>en</Language> <Title>The cutoff phenomenon for finite Markov Chains</Title> <PublishedIn> <Publication> </Publication> </PublishedIn> <PublicationDate>2006-05-24T17:43:53Z</PublicationDate> <Authors> <Author> <DisplayName>Chen, Guan-Yu</DisplayName> <Affiliation> <OrgUnit> </OrgUnit> </Affiliation> </Author> </Authors> <Editors> </Editors> <Publishers> <Publisher> <OrgUnit /> </Publisher> </Publishers> <Keyword>Markov Chain</Keyword> <Keyword>Cutoff phenomenon</Keyword> <Keyword>Mixing time</Keyword> <Keyword>Ergodicity</Keyword> <Keyword>Markov semigroup</Keyword> <Abstract>A card player may ask the following question: how many shuffles are needed to mix up a deck of cards? Mathematically, this question falls in the realm of the quantitative study of the convergence of finite Markov chains. Similar convergence rate questions for finite Markov chains are important in many fields including statistical physics, computer science, biology and more. In this dissertation, we discuss a behavior ---the cutoff phenomenon--- that is known to appear in many models. For these models, after a waiting period, the chain abruptly converges to its stationary distribution. Our aim is to develop a theory of this phenomenon and to illustrate this theory with interesting examples. We focus on the case when the convergence is measured at the $\\ell^p$-distance for $1\\le p\\le\\infty$. For $p=1$, one recovers the classical total variation distance. One of the main result of the thesis is that for families of reversible Markov chains and $1<p\\le\\infty$, the existence of an $\\ell^p$-cutoff can be characterized using two parameters: the spectral gap and the mixing time. This fails when $p=1$. The notion of cutoff for a family of Markov chains indexed by $n$ involves a cutoff time sequence $(t_n)_1^\\infty$ and window size sequence $(b_n)_1^\\infty$. Ideally, when a cutoff exists, we would like to determine precisely $t_n$ and $b_n$. When $p=2$, spectral theory allows for a deeper analysis of the cutoff phenomenon producing in some cases the asymptotic behavior of the sequences $(t_n)_1^\\infty$ and $(b_n)_1^\\infty$. Throughout the thesis, examples are provided to illustrate the theoretical results. In particular, the last chapter is devoted to the study of the cutoff for the randomized riffle shuffle.</Abstract> <Access xmlns=\"http://purl.org/coar/access_right\" > </Access> </Publication>"],"cris:virtual.author":["Chen, Guan-Yu"],"cris:virtualsource.collection":["5893a6ea-7af3-41d7-abc6-04bcd26ab5df"],"dc:creator":["Chen, Guan-Yu"],"dc:date.accessioned":["2006-05-24T17:43:53Z"],"dc:date.available":["2006-05-24T17:43:53Z"],"dc:date.issued":["2006-05-24T17:43:53Z"],"dc:description.abstract":["A card player may ask the following question: how many shuffles are needed to mix up a deck of cards? Mathematically, this question falls in the realm of the quantitative study of the convergence of finite Markov chains. Similar convergence rate questions for finite Markov chains are important in many fields including statistical physics, computer science, biology and more. In this dissertation, we discuss a behavior ---the cutoff phenomenon--- that is known to appear in many models. For these models, after a waiting period, the chain abruptly converges to its stationary distribution. Our aim is to develop a theory of this phenomenon and to illustrate this theory with interesting examples. We focus on the case when the convergence is measured at the $\\ell^p$-distance for $1\\le p\\le\\infty$. For $p=1$, one recovers the classical total variation distance. One of the main result of the thesis is that for families of reversible Markov chains and $1<p\\le\\infty$, the existence of an $\\ell^p$-cutoff can be characterized using two parameters: the spectral gap and the mixing time. This fails when $p=1$. The notion of cutoff for a family of Markov chains indexed by $n$ involves a cutoff time sequence $(t_n)_1^\\infty$ and window size sequence $(b_n)_1^\\infty$. Ideally, when a cutoff exists, we would like to determine precisely $t_n$ and $b_n$. When $p=2$, spectral theory allows for a deeper analysis of the cutoff phenomenon producing in some cases the asymptotic behavior of the sequences $(t_n)_1^\\infty$ and $(b_n)_1^\\infty$. Throughout the thesis, examples are provided to illustrate the theoretical results. In particular, the last chapter is devoted to the study of the cutoff for the randomized riffle shuffle."],"dc:description.collection":["Cornell Theses and Dissertations"],"dc:format.extent":["853059 bytes"],"dc:format.mimetype":["application/pdf"],"dc:identifier.bibid":["6475842"],"dc:identifier.uri":["https://hdl.handle.net/1813/3047"],"dc:language.iso":["en"],"dc:subject":["Markov Chain","Cutoff phenomenon","Mixing time","Ergodicity","Markov semigroup"],"dc:title":["The cutoff phenomenon for finite Markov Chains"],"dc:type":["dissertation or thesis"],"dspace:entity.type":["Publication"],"others:access_status":["open.access"]},"updated_at":"2026-11-19T03:15:03Z"}