Estimating mixing times: Techniques and applications

2005 2005

Other formats: Order a copy

Abstract (summary)

How many times do you have to shuffle a deck of n cards before it is close to random? log n? n? n3? Similar convergence rate questions for finite Markov chains are central to solving applied problems in diverse fields including physics, computer science and biology. This thesis investigates two general techniques for estimating mixing times for finite Markov chains: modified logarithmic Sobolev inequalities and Faber-Krahn inequalities; and analyzes the convergence behavior of a specific family of random walks: the top to bottom shuffles.

Logarithmic Sobolev inequalities are a well-studied technique for estimating convergence rates for Markov chains. In contrast to continuous state spaces, there are several distinct modified log Sobolev inequalities in the discrete setting. Here we derive modified log Sobolev inequalities for several models of random walk, including the random transposition shuffle. These results lead to tight mixing time estimates, and additionally, yield concentration inequalities.

Faber-Krahn inequalities have been used to estimate the rate of decay of the heat kernel on complete, non-compact manifolds and infinite graphs. We develop this technique in the setting of finite Markov chains, proving upper and lower L mixing time bounds via the spectral profile. This approach lets us recover previous conductance-based bounds of mixing time, and in general leads to sharper estimates of convergence rates. We apply this method to several models, including groups with moderate growth, the fractal-like Viscek graphs, and the product group [special characters omitted], and obtain tight bounds on the corresponding mixing times.

A deck of n cards is shuffled by repeatedly moving the top card to one of the bottom kn positions of the deck uniformly at random. We give upper and lower bounds on the total variation mixing time for this shuffle as kn ranges from a constant to n. We also consider a symmetric variant of this walk which at each step either inserts the top card randomly into the bottom kn positions or moves a random card from the bottom kn positions to the top. For this reversible shuffle we derive L2 mixing time bounds.

Indexing (details)

0405: Mathematics
Identifier / keyword
Pure sciences; Card shuffling; Finite Markov chains; Log-Sobolev inequalities; Mixing times
Estimating mixing times: Techniques and applications
Goel, Sharad Chandra
Number of pages
Publication year
Degree date
School code
DAI-B 66/09, Dissertation Abstracts International
Place of publication
Ann Arbor
Country of publication
United States
0542350556, 9780542350559
Saloff-Coste, Laurent
Cornell University
University location
United States -- New York
Source type
Dissertations & Theses
Document type
Dissertation/thesis number
ProQuest document ID
Database copyright ProQuest LLC; ProQuest does not claim copyright in the individual underlying works.
Document URL
Access the complete full text

You can get the full text of this document if it is part of your institution's ProQuest subscription.

Try one of the following:

  • Connect to ProQuest through your library network and search for the document from there.
  • Request the document from your library.
  • Go to the ProQuest login page and enter a ProQuest or My Research username / password.