Analysis of non-reversible Markov chains

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 $L^2$-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