The Open Collections website will be undergoing maintenance on Wednesday December 7th from 9pm to 11pm PST. The site may be temporarily unavailable during this time.

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Bipartitness in reversible Markov chains Langer, Benjamin

Abstract

Let (Xₜ )ₜ∈𝕫₊ be an irreducible, aperiodic, reversible Markov chain on a finite state space Ω. Let M := 𝑡mix/𝑡L, where 𝑡mix and 𝑡L are the total variation mixing times of the chain and its lazy version, respectively. We show - in a precise quantitative sense - that if M is sufficiently large, then the chain is ”near-bipartite”. That is, there exists a bipartition (A, B) of Ω such that π(A) and π(B) are both close to 1/2, and the Markov chain rarely spends two consecutive time steps within the same set of the bipartition. In particular, we show that for 𝑡 ≫ 𝑡L, the distribution of Xₜ is very close to a mixture of πᴀ and πᴃ.

Item Media

Item Citations and Data

Rights

Attribution-NonCommercial-NoDerivatives 4.0 International