•  
  •  
 

Abstract

The pre-asymptotic convergence of Markov chains is a relatively new field of study only two or three decades old and is still an active area of research. One example of a pre-asymptotic behavior is the cutoff phenomenon explored by Diaconis and his collaborators. A Markov chain has a cutoff if it remains far from stationary for a long period, after which it converges within a small number of iterations. As his most famous example, Diaconis showed that seven shuffles is enough to randomize the order of a deck of cards, but after six shuffles the card order is still far from uniformly randomized. Fully understanding the phenomenon would help improve the efficiency of calculating Markov chains in their "long run" states. Though many examples have been analyzed, in general the cutoff phenomenon is still not well understood [1]. Our goal in this paper is to explore the cutoff phenomena for some random walks on one-dimensional lattices. After reviewing some facts about discrete Markov chains in general, we describe spectral and probablistic bounds that describe their convergence.

Author Bio

The paper was completed in October of 2008 in completion of Courant Institute's Summer Undergraduate Research Experience (SURE) program under the tutelage of Doctor David Bindel. I had attended New York University from 2006 to the winter of 2008. As of December 2008, I received my Bachelors in Mathematics. I am currently looking forward to attending graduate school in the northeast for a PHD studying either Number Theory or Dynamical Systems.

Download

Share

COinS