Exact Rates of Convergence for Some Non-reversible Markov Chains

Elizabeth Wilmer

Oberlin College

May 12,
refreshments at 3:45pm


While extensive work has been done bounding rates of convergence of symmetric and/or reversible Markov chains, less is known about the convergence behavior of arbitrary non-reversible chains. We give detailed descriptions of the long-term behavior of some simple families of non-reversible chains; these families have many deterministic transitions and underlying graphs ``close'' to a one-way cycle. We obtain local limit theorems for the distributions of these chains prior to stationarity. In all cases considered, the time to arrive at a fixed distance from stationarity is asymptotically O(n^3/m(n)), where n is the total number of states and m(n) is the number of states with more than one possible successor.

Speaker's Contact Info: elizabeth.wilmer(at-sign)oberlin.edu

Return to seminar home page

Combinatorics Seminar, Mathematics Department, MIT, sara(at-sign)math.mit.edu

Page loaded on May 08, 2000 at 11:05 AM. Copyright © 1998-99, Sara C. Billey. All rights reserved.