Back to search

Cornell University

Analysis of non-reversible Markov chains

Abstract

dc:description.abstract

The analysis of non-reversible Markov chains is of great theoretical and applied interest. In this thesis, we summarize our contributions in this direction into four parts. In the first part, titled ``Skip-free Markov chains'', we aim at developing a general theory for the class of skip-free Markov chains on denumerable state space. This encompasses their potential theory via an explicit characterization of their potential kernel expressed in terms of family of fundamental excessive functions, which are defined by means of the theory of Martin boundary. We also describe their fluctuation theory generalizing the celebrated fluctuations identities that were obtained by using the Wiener-Hopf factorization for the specific skip-free random walks. We proceed by resorting to the concept of similarity to identify the class of skip-free Markov chains whose transition operator has only real and simple eigenvalues. We manage to find a set of sufficient and easy-to-check conditions on the one-step transition probability for a Markov chain to belong to this class. We also study several properties of this class including their spectral expansions given in terms of Riesz basis, derive a necessary and sufficient condition for this class to exhibit a separation cutoff, and give a tighter bound on its convergence rate to stationarity than existing results. In the second part, titled ``Analysis of non-reversible Markov chains via similarity orbit'', we examine the spectral theory of Markov chains on a denumerable state space from a similarity orbit perspective. In particular, we study the class of Markov chains that are in the similarity orbit of Markov chains with normal transition kernels such as birth-death chains or reversible Markov chains. This allows us to derive spectral expansions and offer a detailed analysis on the convergence rate, separation cutoff and L2-cutoff of this class of non-reversible Markov chains. We also look into the problem of estimating the integral functionals from discrete observations for this class. In the last part of this Chapter, we investigate three particular similarity orbits of reversible Markov kernels, that we call the permutation, pure birth and random walk orbit, and analyze various possibly non-reversible variants of classical birth-death processes in these orbits. In the third part, titled ``Metropolis-Hastings reversiblizations of non-reversible Markov chains'', we study two types of Metropolis-Hastings (MH) reversiblizations for non-reversible Markov chains with transition kernel $P$. While the first type is the classical Metropolised version of $P$, we introduce a new self-adjoint kernel which captures the opposite transition effect of the first type, that we call the second MH kernel. We investigate the spectral relationship between $P$ and the two MH kernels. Along the way, we state a version of Weyl's inequality for the spectral gap of $P$ (and hence its additive reversiblization), as well as an expansion of $P$. Both results are expressed in terms of the spectrum of the two MH kernels. In the spirit of \citet{Fill91} and \citet{Paulin15}, we define a new pseudo-spectral gap based on the two MH kernels, and show that the total variation distance from stationarity can be bounded by this gap. We give variance bounds of the Markov chain in terms of the proposed gap, and offer spectral bounds in metastability and Cheeger's inequality in terms of the two MH kernels by comparison of Dirichlet form and Peskun ordering. Finally, in the fourth part, titled ``Estimation of the log-Sobolev constant and Eigenspace of reversible Markov chain via a single sample path'', we build upon the results of \citet{Hsu15} to consider the problem of estimating the log-Sobolev constant and the eigenspace of transition matrix via a single sample path from a reversible and ergodic Markov chain. This allows us to have a tighter mixing time estimate by Wilson's method and the log-Sobolev upper bound. We prove statistical guarantees for our proposed estimators, and demonstrate that the idea can be used to estimate other functional constants such as the modified log-Sobolev constant and the Cheeger constant of the Markov chain.

Degree

thesis:*
Name thesis:degree_name
Ph. D., Operations Research
Level thesis:degree_level
Doctor of Philosophy
Discipline thesis:degree_discipline
Operations Research
Grantor
Cornell University
Year dc:date.issued
2017

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Choi, Chek Hin
Chair dc:contributor.chair
  • Patie, Pierre
Committee members dc:contributor.committeemember
  • Dai, Jiangang
  • Saloff-Coste, Laurent Pascal

Subjects

dc:subject × 9

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Dc Identifier Bibid
10361407
Dc Identifier Other
ProQuest Submission ID: 10321
ProQuest Publication ID: 10288022

Chain of custody

source
Harvested from
Cornell University
Base URL
ecommons.cornell.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Choi, Chek Hin. Analysis of non-reversible Markov chains. Doctor of Philosophy thesis, Cornell University, 2017. https://hdl.handle.net/1813/56730