Bounds on Biased and Unbiased Random Walks

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