UC Berkeley

The aim of this thesis is to present several (co-authored) works of the author concerning applications of maximal inequalities to the theory of Markov chains and put them in a unifying context. Using maximal inequalities we show that different notions of convergence of a Markov chain to its stationary distribution are in some quantitative sense equivalent to some seemingly weaker notions of convergence. In particular, it is shown that the convergence to stationarity of an ergodic reversible Markov chain w.r.t. the $L_p$ distances ($p \in [1,\infty] $) and the relative-entropy distance can be understood (up to a constant factor) in terms of hitting time distributions. We present several applications of these characterizations, mostly ones concerning the cutoff phenomenon and robustness of mixing times.

A sequence of Markov chains is said to exhibit (total variation) cutoff if the convergence to stationarity in total variation distance is abrupt. Though many families of chains are believed to exhibit cutoff, proving the

occurrence of this phenomenon is often an extremely challenging task. Verifying the occurrence of the cutoff phenomenon is a major area of modern probability,

and despite remarkable progress over the last three decades, there are still only relatively few examples which are completely understood.

Although drawing much attention, the progress made in the investigation

of the cutoff phenomenon was done mostly through understanding examples and

the field suffers from a lack of general theory.

The cutoff phenomenon was given its name by Aldous and Diaconis

in their seminal paper \cite{aldous1986shuffling} from 1986 in which they

suggested the following open problem (re-iterated in \cite{diaconis1996cutoff}), which they refer to as ``the most interesting problem":

``\textit{Find abstract conditions which ensure that the cutoff phenomenon occurs}".

In a joint work with Riddhipratim Basu and Yuval Peres \cite{cutoff} we showed that under reversibility, $t_{\mathrm{mix}}(\epsilon)$ (the $\epsilon$ total variation mixing time) can be approximated up to an additive term, proportional to the inverse of the spectral gap, by the minimal time required for the chain to escape from every (fixed) set of stationary probability at most $1/2$ w.p. at least $1-\epsilon$. This substantially refines earlier works which only characterized $t_{\mathrm{mix}}$ up to a constant factor. As a consequence, (under reversibility) we derive a necessary and sufficient condition for cutoff in terms of concentration of hitting times of large sets which are ``worst" in some sense.

As an application, we show that a sequence of (possibly weighted) nearest neighbor random walks on finite trees exhibits cutoff if and only if it satisfies a spectral condition known as the product condition. We obtain an optimal bound on the size of the cutoff window, and establish sub-gaussian convergence within it. Our proof is robust, allowing us to extend the analysis to weighted random walks with bounded jumps on intervals.

There are several works characterizing the total-variation mixing time of a reversible Markov chain in term of natural probabilistic concepts such as stopping times and hitting times. In contrast, there is no known analog for the $L_{2}$ mixing time, $\tau_{2}$ (while there are sophisticated analytic tools to bound $ \tau_2$, in general they do not determine $\tau_2$ up to a constant factor and they lack a probabilistic interpretation). We show that $\tau_2$ can be characterized up to a constant factor using hitting times distributions. We also derive a new extremal characterization of the Log-Sobolev constant, $c_{\mathrm{LS}}$, as a weighted version of the spectral gap. This characterization yields a probabilistic interpretation of $c_{\mathrm{LS}}$ in terms of a hitting time version of hypercontractivity. As applications of our results, we show that (1) for every reversible Markov chain, $\tau_2$ is robust under addition of self-loops with bounded weights, and (2) for weighted nearest neighbor random walks on trees, $\tau_2 $ is robust under bounded perturbations of the edge weights.

Let $(X_t)_{t = 0 }^{\infty}$ be an irreducible reversible discrete-time Markov chain on a finite state space $\Omega $. Denote its transition matrix by $P$. To avoid periodicity issues one often considers the continuous-time version of the chain, whose kernel is given by $H_t:=e^{-t}\sum_k \frac{1}{k!} (tP)^k $. Since reversible chains are either aperiodic or have period 2, it is plausible that a single lazy step suffices to eliminate near periodicity issues. This motivates looking at the associated averaged chain, whose distribution at time $t \ge 1 $ is obtained by replacing $P^{t}$ with $A_t:=\frac{1}{2}(P^{t-1}+P^{t})$. We confirm a conjecture by Aldous and Fill \cite[Open Problem 4.17]{aldous2000reversible} by showing that under reversibility, for all $t,M>e$ and $x \in \Omega$

\begin{equation*}

\label{eq:AFeasy}

\|H_{t+M \sqrt{t}}(x,\cdot) -\pi(\cdot)\|_{\mathrm{TV}}-e^{-cM^2} \le \|A_{t }(x,\cdot) -\pi (\cdot) \|_{\mathrm{TV}} \le \|H_{t-( M \log M) \sqrt{t}}(x,\cdot) -\pi(\cdot)\|_{\mathrm{TV}} + C/M.

\end{equation*}

We deduce that given a sequence of irreducible reversible discrete-time Markov chains, the sequence of the continuous-time chains exhibits cutoff around time $t_n$ iff the same holds for the sequence of averaged chains. Moreover, we show that the size of the cutoff window of the sequence of averaged chains is at most that of the sequence of the continuous-time chains and that the latter can be determined in terms of the former.