Cornell University
Library
Cornell UniversityLibrary

eCommons

Help
Log In(current)
  1. Home
  2. Cornell University Graduate School
  3. Cornell Theses and Dissertations
  4. The cutoff phenomenon for finite Markov Chains

The cutoff phenomenon for finite Markov Chains

File(s)
dissertation20060524.pdf (833.07 KB)
Permanent Link(s)
https://hdl.handle.net/1813/3047
Collections
Cornell Theses and Dissertations
Author
Chen, Guan-Yu
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

Date Issued
2006-05-24T17:43:53Z
Keywords
Markov Chain
•
Cutoff phenomenon
•
Mixing time
•
Ergodicity
•
Markov semigroup
Type
dissertation or thesis

Site Statistics | Help

About eCommons | Policies | Terms of use | Contact Us

copyright © 2002-2026 Cornell University Library | Privacy | Web Accessibility Assistance