# Information divergences of Markov chains and their applications

Youjia Wang Email<EMAIL_ADDRESS>Department of Statistics and Data
Science, National University of Singapore, Singapore  Michael C.H. Choi Email:
<EMAIL_ADDRESS>Department of Statistics and Data Science and Yale-NUS
College, National University of Singapore, Singapore

###### Abstract

In this paper, we first introduce and define several new information
divergences in the space of transition matrices of finite Markov chains which
measure the discrepancy between two Markov chains. These divergences offer
natural generalizations of classical information-theoretic divergences, such
as the $f$-divergences and the Rényi divergence between probability measures,
to the context of finite Markov chains. We begin by detailing and deriving
fundamental properties of these divergences and notably gives a Markov chain
version of the Pinsker’s inequality and Chernoff information. We then utilize
these notions in a few applications. First, we investigate the binary
hypothesis testing problem of Markov chains, where the newly defined Rényi
divergence between Markov chains and its geometric interpretation play an
important role in the analysis. Second, we propose and analyze information-
theoretic (Cesàro) mixing times and ergodicity coefficients, along with
spectral bounds of these notions in the reversible setting. Examples of the
random walk on the hypercube, as well as the connections between the critical
height of the low-temperature Metropolis-Hastings chain and these proposed
ergodicity coefficients, are highlighted.
Keywords: Markov chains; $f$-divergences; Rényi divergence; ergodicity
coefficients; mixing times; Metropolis-Hastings
AMS 2020 subject classification: 60J10, 60J20, 94A15, 94A17

##  1 Introduction

Given two Markov chains with transition matrices $M,L$ on a common finite
state space $\mathcal{X}$, how to measure their information-theoretic
discrepancies? The present manuscript is largely motivated by this question
and one of the main aims is to systematically analyze various natural notions
of information divergences of Markov chains and to present some interesting
and important applications, particularly in the context of mixing times,
convergence towards equilibrium and hypothesis testing of Markov chains.

Let us begin by briefly recalling several established notions of information
divergences of Markov chains in the literature. In [22], the total variation
distance between $M,L$ with respect to a given probability distribution $\pi$
is introduced and investigated for Metropolis-Hastings chains, namely

$\mathrm{TV}(M,L):=\dfrac{1}{2}\sum_{x,y\in\mathcal{X}}\pi(x)\left|M(x,y)-L(x,y)\right|,$

while the Kullback-Leibler (KL) divergence from $L$ to $M$ with respect to
$\pi$, as studied in [36], is given by

$D_{KL}(M\|L):=\sum_{x,y\in\mathcal{X}}\pi(x)M(x,y)\ln\left(\dfrac{M(x,y)}{L(x,y)}\right).$

These two divergences are in fact special cases of $f$-divergences. Let
$f:\mathbb{R}^{+}\to\mathbb{R}$ be a convex function with $f(1)=0$ that we
call it as the generator of $f$-divergence. The $f$-divergence from $L$ to $M$
with respect to $\pi$ is defined to be

$D_{f}(M\|L):=\sum_{x\in\mathcal{X}}\pi(x)\sum_{y\in\mathcal{X}}L(x,y)f\left(\dfrac{M(x,y)}{L(x,y)}\right).$

Note that by taking $f(t)=\frac{1}{2}|t-1|$ and $f(t)=t\ln t$, we recover
respectively the total variation distance and KL divergence introduced
earlier.

An important family of $f$-divergences is known as the $\alpha$-divergence,
that we denote by $D_{\alpha}$, for $\alpha\in(0,1)\cup(1,+\infty)$ by taking
$f(t)=\frac{t^{\alpha}-1}{\alpha-1}$. The Rényi divergence from $L$ to $M$ of
the order $\alpha\in(0,1)\cup(1,+\infty)$ can be defined to be

$\displaystyle R_{\alpha}(M\|L)$
$\displaystyle:=\dfrac{1}{\alpha-1}\ln\left(1+(\alpha-1)D_{\alpha}(M\|L)\right).$

All these divergences shall be introduced in a more precise manner in Section
2.

With the above notations in mind, we proceed to highlight several important
and interesting achievements of this manuscript. The first major achievements
lie in introducing and analyzing fundamental properties of $D_{f},D_{\alpha}$
and $R_{\alpha}$ in the context of discrete-time Markov chains. While these
divergences are frequently utilized to quantify the information divergences of
probability measures, to the best of our knowledge these divergences have not
been systematically investigated in finite Markov chains. Notable highlights
include

  * •

Markov chain Pinsker’s inequality (Proposition 3.5): for $0<\alpha\leq 1$,

$\dfrac{\alpha}{2}\mathrm{TV}^{2}(M,L)\leq R_{\alpha}(M\|L).$

  * •

Chernoff information of Markov chain (Proposition 3.8): for $\alpha>0$,

$(1-\alpha)R_{\alpha}(M\|L)=\inf_{P\in\mathcal{L}}\left\\{\alpha
D_{KL}(P\|M)+(1-\alpha)D_{KL}(P\|L)\right\\},$

where $\mathcal{L}=\mathcal{L}(\mathcal{X})$ is the set of all transition
matrices on $\mathcal{X}$.

  * •

Ergodicity coefficients in the space of finite transition matrices, and their
properties (Proposition 3.9): given $P\in\mathcal{L}$ and
$\alpha\in(0,1)\cup(1,+\infty)$, we define

$\displaystyle\eta^{f}(P)=\eta^{f}(P,\pi):=\sup_{M,L\in\mathcal{L};~{}M\neq
L}\dfrac{D_{f}(MP\|LP)}{D_{f}(M\|L)},$
$\displaystyle\eta^{(R_{\alpha})}(P)=\eta^{(R_{\alpha})}(P,\pi):=\sup_{M,L\in\mathcal{L};~{}M\neq
L}\dfrac{R_{\alpha}(MP\|LP)}{R_{\alpha}(M\|L)}.$

In the remaining of this section, let us assume that $P$ is ergodic and admits
$\pi$ as its stationary distribution. Let $\Pi$ be a matrix with each row
being $\pi$ for all rows. To quantify and assess the convergence rate of
$P^{t}$ towards $\Pi$, we define the $\pi$-weighted $\alpha$-divergence mixing
time to be

$\displaystyle\bar{t}_{\mathrm{mix}}^{(D_{\alpha})}(\varepsilon,P)$
$\displaystyle:=\inf\left\\{t>0:D_{\alpha}(P^{t}\|\Pi)<\varepsilon\right\\}.$

Analogously we shall define Rényi divergence mixing times. In this vein, one
of our major achievements in this direction lie in proposing and analyzing new
information-theoretic mixing times, in which We offer spectral bounds on these
mixing times:

######  Theorem 1.1 (Informal presentation of Theorem 4.3).

Let $P$ be an irreducible, aperiodic and $\pi$-reversible transition matrix,
and we denote $\pi_{\mathrm{min}}:=\min_{x}\pi(x)>0$. For
$\alpha\in(0,1)\cup(1,+\infty)$ and sufficiently small $\varepsilon$, we have

$\displaystyle\bar{t}_{\mathrm{mix}}^{(D_{\alpha})}(\varepsilon,P)$
$\displaystyle\leq\begin{cases}\dfrac{1}{\gamma_{*}}\left(\ln\dfrac{2\alpha}{(\alpha-1)\pi_{\mathrm{min}}}+\ln\dfrac{1}{\varepsilon}\right),\quad\textrm{if
}\,\alpha>1,\\\
\dfrac{1}{\gamma_{*}}\left(\ln\dfrac{8\alpha}{(1-\alpha)\pi_{\mathrm{min}}}+\ln\dfrac{1}{\varepsilon}\right),\quad\textrm{if
}\,0<\alpha<1,\end{cases}$

and

$\displaystyle\bar{t}_{\mathrm{mix}}^{(D_{\alpha})}(\varepsilon,P)$
$\displaystyle\geq\begin{cases}\dfrac{1}{2\ln\frac{1}{1-\gamma_{*}}}\left(\ln\dfrac{\pi_{\mathrm{min}}^{2}}{8}+\ln\dfrac{1}{\varepsilon}\right),\quad\textrm{if
}\,\alpha>1,\\\
\dfrac{1}{2\ln\frac{1}{1-\gamma_{*}}}\left(\ln\dfrac{\pi_{\mathrm{min}}^{2}\alpha}{16}+\ln\dfrac{1}{\varepsilon}\right),\quad\textrm{if
}\,0<\alpha<1,\end{cases}$

where $\gamma_{*}$ is the absolute spectral gap of $P$.

On the other hand, the worst-case mixing time based upon $\alpha$-divergence
is defined to be, for $\varepsilon>0$,

$\displaystyle t_{\mathrm{mix}}^{(\mathrm{D_{\alpha}})}(\varepsilon,P)$
$\displaystyle:=\inf\left\\{t>0:\max_{x\in\mathcal{X}}\widetilde{D}_{\alpha}(P^{t}(x,\cdot)\|\pi)=\max_{x\in\mathcal{X}}\dfrac{1}{\alpha-1}\left(\sum_{y\in\mathcal{X}}\pi(y)\left(\dfrac{P^{t}(x,y)}{\pi(y)}\right)^{\alpha}-1\right)<\varepsilon\right\\}.$

To compare the average mixing time
$\bar{t}_{\mathrm{mix}}^{(D_{\alpha})}(\varepsilon,P)$ and the worst-case
mixing time $t_{\mathrm{mix}}^{(\mathrm{D_{\alpha}})}(\varepsilon,P)$, in the
following result we prove that these two mixing times are of the same order
under very mild assumptions on the absolute spectral gap of $P$ (which are for
instance satisfied in low-temperature Metropolis-Hastings chain or the random
walk on hypercube):

######  Theorem 1.2 (Informal presentation of Theorem 4.4).

Under the same assumptions and notations as in Theorem 1.1, and in addition
$\gamma_{*}(P)$ satisfies some mild assumptions, we have

$\dfrac{1}{5}t_{\mathrm{mix}}^{(D_{\alpha})}(\varepsilon,P)\leq\bar{t}_{\mathrm{mix}}^{(D_{\alpha})}(\varepsilon,P)\leq
t_{\mathrm{mix}}^{(D_{\alpha})}(\varepsilon,P).$

Analogous results comparing the average and the worst-case mixing time based
upon Rényi divergence and total variation distance are also provided in
Theorem 4.4. We also remark on the series of work that compare the order of
various mixing times and hitting times of Markov chains or Markov processes,
see for example [19, 20, 27, 21, 26, 30, 31, 34] and the references therein.

The rest of this paper is organized as follows. In Section 2, we formally
introduce various information divergences and ergodicity coefficients of
Markov chains. Their fundamental properties are stated and proved in Section
3, followed by applications in binary hypothesis testing of Markov chains in
Section 4.1. The information-theoretic mixing times and their spectral bounds
are discussed in Section 4.2. Finally, we elucidate on the relationship
between Cesàro mixing times, ergodicity coefficients and the critical height
of the low-temperature Metropolis-Hastings chain in Section 4.3.

##  2 Basic definitions

On a finite state space $\mathcal{X}$, we define
$\mathcal{L}=\mathcal{L}(\mathcal{X})$ as the set of transition matrices of
discrete-time Markov chains. We denote by $\mathcal{P}(\mathcal{X})$ to be the
set of probability masses on $\mathcal{X}$. Let $\pi\in\mathcal{P}$ is any
given positive probability distribution on $\mathcal{X}$, and denote
$\mathcal{L}(\pi)\subset\mathcal{L}$ as the set of $\pi$-reversible transition
matrices, where a transition matrix $P\in\mathcal{L}$ is said to be
$\pi$-reversible if $\pi(x)P(x,y)=\pi(y)P(y,x)$ for all $x,y\in\mathcal{X}$.
We also say that $P\in\mathcal{L}$ is $\pi$-stationary if it satisfies $\pi
P=\pi$.

First, we give the definition of $f$-divergence of Markov chains and recall
that of probability measures.

######  Definition 2.1 ($f$-divergence of Markov chains and of probability
measures).

Let $f:\mathbb{R}^{+}\mapsto\mathbb{R}$ be a convex function and $f(1)=0$. For
given $\pi\in\mathcal{P}(\mathcal{X})$ and transition matrices
$M,L\in\mathcal{L}$, we define the $f$-divergence from $L$ to $M$ as

$D_{f}(M\|L):=\sum_{x\in\mathcal{X}}\pi(x)\sum_{y\in\mathcal{X}}L(x,y)f\left(\dfrac{M(x,y)}{L(x,y)}\right).$
(1)

For two probability measures $\mu,\nu\in\mathcal{P}(\Omega)$ with $\Omega$
finite, the $f$-divergence from $\nu$ to $\mu$ is defined to be

$\widetilde{D}_{f}(\mu\|\nu):=\sum_{x\in\Omega}\nu(x)f\left(\frac{\mu(x)}{\nu(x)}\right),$
(2)

where we apply the usual convention that $0f(\frac{0}{0}):=0$ and
$0f(\frac{a}{0}):=af^{\prime}(+\infty)$ with $f^{\prime}(+\infty):=\lim_{x\to
0^{+}}xf(\frac{1}{x})$ for $a>0$ in the two definitions above.

Note that $D_{f}(M\|L)$ can be understood as a $\pi$-weighted average of
$\widetilde{D}_{f}(M(x,\cdot)\|L(x,\cdot))$, since we have

$\displaystyle
D_{f}(M\|L)=\sum_{x\in\mathcal{X}}\pi(x)\widetilde{D}_{f}(M(x,\cdot)\|L(x,\cdot)).$
(3)

In the sequel, a majority of our focus is devoted to the special case of
$\alpha$-divergences, where we take $f(t)=\frac{t^{\alpha}-1}{\alpha-1}$ with
$\alpha\in(0,1)\cup(1,+\infty)$ in Definition 2.1. As a result, this yields

$\displaystyle D_{\alpha}(M\|L)$
$\displaystyle:=\dfrac{1}{\alpha-1}\left(\sum_{x\in\mathcal{X}}\pi(x)\sum_{y\in\mathcal{X}}L(x,y)\left(\dfrac{M(x,y)}{L(x,y)}\right)^{\alpha}-1\right),$
(4) $\displaystyle\widetilde{D}_{\alpha}(\mu\|\nu)$
$\displaystyle:=\dfrac{1}{\alpha-1}\left(\sum_{x\in\Omega}\nu(x)\left(\dfrac{\mu(x)}{\nu(x)}\right)^{\alpha}-1\right),$
(5)

where the same convention as in Definition 2.1 still applies in the equations
above. Using $\widetilde{D}_{\alpha}(\mu\|\nu)$, we now introduce the Rényi
divergence between probability measures as systematically investigated in
[35].

######  Definition 2.2 (Rényi divergence of probability measures).

For probability measures $\mu,\nu\in\mathcal{P}(\Omega)$ and $\Omega$ is
finite, the Rényi divergence from $\nu$ to $\mu$ of the order
$\alpha\in(0,1)\cup(1,+\infty)$ is given by

$\displaystyle\widetilde{R}_{\alpha}(\mu\|\nu)$
$\displaystyle:=\dfrac{1}{\alpha-1}\ln\sum_{x\in\Omega}\nu(x)\left(\dfrac{\mu(x)}{\nu(x)}\right)^{\alpha}$
$\displaystyle=\dfrac{1}{\alpha-1}\ln\left(1+(\alpha-1)\widetilde{D}_{\alpha}(\mu\|\nu)\right).$
(6)

Using simple convexity arguments, it can readily be shown that
$\widetilde{R}_{\alpha}(\mu\|\nu)\geq 0$ (see for example [35]), from which we
see that $1+(\alpha-1)\widetilde{D}_{\alpha}(\mu\|\nu)\geq 0$. In the case for
Markov chains however, the definition for Rényi divergence from $L$ to $M$ is
more involved, as we cannot directly define it in the form (6) via simply
replacing $\widetilde{D}_{\alpha}(\mu\|\nu)$ with $D_{\alpha}(M\|L)$, since
such definition can be ill-defined as it is a priori unclear whether
$1+(\alpha-1)D_{\alpha}(M\|L)\geq 0$ when $\alpha<1$. To give a meaningful
definition in this case, one possible remedy is to instead consider the
divergence of the edge measure of the two chains.

######  Definition 2.3 (Edge measure of a Markov chain with respect to $\pi$).

For $x,y\in\mathcal{X}$, $M\in\mathcal{L}$ and
$\pi\in\mathcal{P}(\mathcal{X})$, if we write

$\displaystyle\widetilde{M}(x,y)$ $\displaystyle:=\pi(x)M(x,y),$

then
$\widetilde{M}=\left(\widetilde{M}(x,y)\right)_{\mathcal{X}\times\mathcal{X}}$
is a probability measure on $\mathcal{X}\times\mathcal{X}$. $\widetilde{M}$ is
known as the edge measure of $M$ with respect to $\pi$, see [36]. Analogously
we can define the edge measure of $L$ with respect to $\pi$, denoted by
$\widetilde{L}$.

Using Definition 2.3 and (5), this immediately yields an important equality
which will play a key role in the following sections:

$\widetilde{D}_{\alpha}(\widetilde{M}\|\widetilde{L})=\dfrac{1}{\alpha-1}\left(\sum_{x,y\in\mathcal{X}}\pi(x)L(x,y)\left(\dfrac{M(x,y)}{L(x,y)}\right)^{\alpha}-1\right)=D_{\alpha}(M\|L).$
(7)

Intuitively, it means that the $\alpha$-divergence from the edge measure
$\widetilde{L}$ to $\widetilde{M}$ equals to the $\alpha$-divergence from the
chain $L$ to $M$. Thus, to analyze the property of $D_{\alpha}(M\|L)$, it
suffices to investigate the corresponding property of
$\widetilde{D}_{\alpha}(\widetilde{M}\|\widetilde{L})$. With equality (7), we
can proceed to give a well-defined Rényi divergence $R_{\alpha}(M\|L)$.

######  Definition 2.4 (Rényi divergence of Markov chains).

Given $M,L\in\mathcal{L}$, the Rényi divergence from $L$ to $M$ of the order
$\alpha\in(0,1)\cup(1,+\infty)$ is given by

$\displaystyle R_{\alpha}(M\|L)$
$\displaystyle:=\widetilde{R}_{\alpha}(\widetilde{M}\|\widetilde{L})$ (8)
$\displaystyle=\dfrac{1}{\alpha-1}\ln\left(1+(\alpha-1)\widetilde{D}_{\alpha}(\widetilde{M}\|\widetilde{L})\right)$
$\displaystyle=\dfrac{1}{\alpha-1}\ln\left(1+(\alpha-1)D_{\alpha}(M\|L)\right).$
(9)

Note that for $t\geq 0$ (resp. $0\leq t\leq 1/(1-\alpha)$) and $\alpha>1$
(resp. $\alpha\in(0,1)$), the mapping
$t\mapsto\frac{1}{\alpha-1}\ln(1+(\alpha-1)t)$ is concave (resp. convex), and
hence by Jensen’s inequality and (3), this yields

$\displaystyle
R_{\alpha}(M\|L)\begin{cases}\geq\sum_{x\in\mathcal{X}}\pi(x)\widetilde{R}_{\alpha}(M(x,\cdot)\|L(x,\cdot)),\quad\textrm{if
}\,\alpha>1,\\\
\leq\sum_{x\in\mathcal{X}}\pi(x)\widetilde{R}_{\alpha}(M(x,\cdot)\|L(x,\cdot)),\quad\textrm{if
}\,0<\alpha<1,\end{cases}$ (10)

where the right hand side above can be understood as the $\pi$-weighted
average of the Rényi divergence
$\widetilde{R}_{\alpha}(M(x,\cdot)\|L(x,\cdot))$. These two inequalities also
contrast with the equality in (3).

In addition to $D_{\alpha}$ and $R_{\alpha}$ as discussed earlier, we next
introduce some $f$-divergences of Markov chains. Their counterparts in
probability measures are well-studied in the literature, see for example [35,
Eq.5-7].

######  Definition 2.5 (Some common $f$-divergences of Markov chains).

For $M,L\in\mathcal{L}$ and $\pi\in\mathcal{P}(\mathcal{X})$, by taking $f(t)$
to be respectively $(\sqrt{t}-1)^{2},(t-1)^{2},|t-1|/2$ in Definition 2.1, we
define

$\displaystyle(\mathbf{Hellinger\enspace distance})\quad\mathrm{Hel}^{2}(M,L)$
$\displaystyle:=\sum_{x,y\in\mathcal{X}}\pi(x)\left(\sqrt{M(x,y)}-\sqrt{L(x,y)}\right)^{2},$
(11) $\displaystyle(\mathbf{\chi^{2}-divergence})\quad\chi^{2}(M\|L)$
$\displaystyle:=\sum_{L>0}\pi(x)\dfrac{\left(M(x,y)-L(x,y)\right)^{2}}{L(x,y)},$
(12) $\displaystyle(\mathbf{Total\enspace variation\enspace
distance})\quad\mathrm{TV}(M,L)$
$\displaystyle:=\dfrac{1}{2}\sum_{x,y\in\mathcal{X}}\pi(x)\left|M(x,y)-L(x,y)\right|.$
(13)

The next definition concerns the closest $\pi$-reversible transition matrix to
any given transition matrix $L$ as measured by the Rényi divergence of the
order $\alpha$:

######  Definition 2.6 ($\alpha$-projection).

For $L\in\mathcal{L}$ and $\alpha\in(0,1)\cup(1,+\infty)$, we say that
$L^{(R_{\alpha})}$ is an $\alpha$-projection of $L$ to $\mathcal{L}(\pi)$, if

$L^{(R_{\alpha})}=L^{(R_{\alpha})}(L,\pi)\in\mathop{\arg\min}\limits_{M\in\mathcal{L}(\pi)}R_{\alpha}(M\|L),$

where we recall that $\mathcal{L}(\pi)$ denotes the set of $\pi$-reversible
transition matrices.

Note that the set $\mathcal{L}(\pi)$ is a compact subset of
$\mathbb{R}^{|\mathcal{X}|\times|\mathcal{X}|}$ and the mapping $M\mapsto
R_{\alpha}(M\|L)$ is clearly continuous, and hence $L^{(R_{\alpha})}$ exists.
We shall investigate the uniqueness of $\alpha$-projection later using the
Pythagorean inequality (14) in Proposition 3.7.

The final definition of the section introduces new ergodicity coefficients of
$P$ on the space of transition matrices $\mathcal{L}$ based upon information
divergences. These can be used to assess the contraction rate of $P$.

######  Definition 2.7 (Ergodicity coefficients of Markov chains based on
$D_{f}$ and $R_{\alpha}$).

Given $P\in\mathcal{L}$, $\pi\in\mathcal{P}(\mathcal{X})$ and
$\alpha\in(0,1)\cup(1,+\infty)$, we define

$\displaystyle\eta^{f}(P)=\eta^{f}(P,\pi):=\sup_{M,L\in\mathcal{L};~{}M\neq
L}\dfrac{D_{f}(MP\|LP)}{D_{f}(M\|L)},$
$\displaystyle\eta^{(R_{\alpha})}(P)=\eta^{(R_{\alpha})}(P,\pi):=\sup_{M,L\in\mathcal{L};~{}M\neq
L}\dfrac{R_{\alpha}(MP\|LP)}{R_{\alpha}(M\|L)}.$

Their classical counterparts on the space of probability measures
$\mathcal{P}(\mathcal{X})$ are defined analogously to be

$\displaystyle\widetilde{\eta}^{f}(P):=\sup_{\mu,\nu\in\mathcal{P}(\mathcal{X});~{}\mu\neq\nu}\dfrac{\widetilde{D}_{f}(\mu
P\|\nu P)}{\widetilde{D}_{f}(\mu\|\nu)},$
$\displaystyle\widetilde{\eta}^{(R_{\alpha})}(P):=\sup_{\mu,\nu\in\mathcal{P}(\mathcal{X});~{}\mu\neq\nu}\dfrac{\widetilde{R}_{\alpha}(\mu
P\|\nu P)}{\widetilde{R}_{\alpha}(\mu\|\nu)}.$

In the special cases of total variation distance and $\alpha$-divergence, we
shall write the corresponding ergodicity coefficients of $P$ to be
$\eta^{(\mathrm{TV})}(P),\widetilde{\eta}^{(\mathrm{TV})}(P)$ for
$f(t)=|t-1|/2$ and $\eta^{(D_{\alpha})}(P),\widetilde{\eta}^{(D_{\alpha})}(P)$
for $f(t)=\frac{t^{\alpha}-1}{\alpha-1}$ respectively. In the literature,
$\eta^{(\mathrm{TV})}(P)$ is also called the Dobrushin contraction
coefficient, see [24].

##  3 Properties of $D_{\alpha}(M\|L)$ and $R_{\alpha}(M\|L)$

In this section, we present some fundamental and important properties of the
$\alpha$-divergence $D_{\alpha}(M\|L)$ and the Rényi divergence
$R_{\alpha}(M\|L)$ for $M,L\in\mathcal{L}$, which follows readily from the
analogous results [35] in the context of probability measures. For
$M,L\in\mathcal{L}$, we give a roadmap of the major results and new notions
that we introduce in this section as follows. We shall see that many of these
properties are inherited from their counterparts of
$\widetilde{D}_{\alpha},\widetilde{R}_{\alpha}$:

  * •

Non-negativity of $D_{\alpha}(M\|L)$ and $R_{\alpha}(M\|L)$: Proposition 3.1

  * •

Convexity of the mappings $(M,L)\mapsto D_{\alpha}(M\|L)$ and $(M,L)\mapsto
R_{\alpha}(M\|L)$: Proposition 3.2

  * •

Monotonicity in $\alpha$ of $R_{\alpha}(M\|L)$: Proposition 3.3

  * •

Pinsker’s inequality of Markov chains and various relationships with other
divergences: Proposition 3.5

  * •

Pythagorean inequality and weak triangle inequality of the Rényi divergence:
Proposition 3.7

  * •

Chernoff information of Markov chains: Proposition 3.8

  * •

Properties of various ergodicity coefficients: Proposition 3.9

The first result that we present demonstrates the non-negativity of
$D_{\alpha}(M\|L)$ and $R_{\alpha}(M\|L)$.

######  Proposition 3.1 (Non-negativity of $D_{\alpha}(M\|L)$ and
$R_{\alpha}(M\|L)$).

Given $M,L\in\mathcal{L}$ and $\pi\in\mathcal{P}(\mathcal{X})$ is strictly
positive on $\mathcal{X}$, we have $D_{\alpha}(M\|L)\geq 0$ and
$R_{\alpha}(M\|L)\geq 0$, and the equality holds if and only if $M=L$.

###### Proof.

In view of (3), the non-negativity of $D_{\alpha}$ is clear and inherits from
that of $\widetilde{D}_{\alpha}$, see e.g. [32, Theorem $7.5$]. Since $\pi$ is
strictly positive, the equality holds if and only if
$\widetilde{D}_{\alpha}(M(x,\cdot)\|L(x,\cdot))=0$ for all $x\in\mathcal{X}$
if and only if $M=L$. As to $R_{\alpha}(M\|L)$, since
$R_{\alpha}(M\|L)=\widetilde{R}_{\alpha}\left(\widetilde{M}\|\widetilde{L}\right)$,
it suffices to show
$\widetilde{R}_{\alpha}\left(\widetilde{M}\|\widetilde{L}\right)\geq 0$, which
is a classic result as in [35, Theorem 8]. ∎

The second result proves the convexity of the $\alpha$-divergence and Rényi
divergence for suitable $\alpha$ choices:

######  Proposition 3.2 (Convexity of $D_{\alpha}(M\|L)$ and
$R_{\alpha}(M\|L)$).

For $M,L\in\mathcal{L}$ and $\pi\in\mathcal{P}(\mathcal{X})$, the following
statements hold:

  1. (i).

For $\alpha\in(0,1)$, both of $D_{\alpha}(M\|L)$ and $R_{\alpha}(M\|L)$ are
jointly convex in $(M,L)$.

  2. (ii).

For $\alpha\in(1,+\infty)$, $D_{\alpha}(M\|L)$ is jointly convex in $(M,L)$,
and $R_{\alpha}(M\|L)$ is convex in $L$.

  3. (iii).

For $\alpha\in(0,1)\cup(1,+\infty)$, $R_{\alpha}(M\|L)$ is jointly quasi-
convex in (M,L), i.e. for $\lambda\in(0,1)$ and $(M_{1},L_{1}),(M_{2},L_{2})$,
we have

$R_{\alpha}(\lambda M_{1}+(1-\lambda)M_{2}\|\lambda
L_{1}+(1-\lambda)L_{2})\leq\max\left\\{R_{\alpha}(M_{1}\|L_{1}),R_{\alpha}(M_{2}\|L_{2})\right\\}.$

###### Proof.

We first prove that for $\alpha>0$ and $\alpha\neq 1$, $D_{\alpha}(M\|L)$ is
jointly convex in $(M,L)$, i.e. for $\lambda\in(0,1)$ and
$(M_{1},L_{1}),(M_{2},L_{2})\in\mathcal{L}\times\mathcal{L}$, we need to prove

$D_{\alpha}\left(\lambda M_{1}+(1-\lambda)M_{2}\|\lambda
L_{1}+(1-\lambda)L_{2}\right)\leq\lambda
D_{\alpha}(M_{1}\|L_{1})+(1-\lambda)D_{\alpha}(M_{2}\|L_{2}).$

This can be readily verified: as $f(t)=\frac{t^{\alpha}-1}{\alpha-1}$ is
convex, which implies that $L(x,y)f\left(\frac{M(x,y)}{L(x,y)}\right)$ is
convex in $(M(x,y),L(x,y))$, since

$\displaystyle
L_{\lambda}(x,y)f\left(\dfrac{M_{\lambda}(x,y)}{L_{\lambda}(x,y)}\right)$
$\displaystyle\leq\lambda
L_{1}(x,y)f\left(\dfrac{M_{1}(x,y)}{L_{1}(x,y)}\right)+(1-\lambda)L_{2}(x,y)f\left(\dfrac{M_{2}(x,y)}{L_{2}(x,y)}\right)$
$\displaystyle\iff f\left(\dfrac{M_{\lambda}(x,y)}{L_{\lambda}(x,y)}\right)$
$\displaystyle\leq\lambda\dfrac{L_{1}(x,y)}{L_{\lambda}(x,y)}f\left(\dfrac{M_{1}(x,y)}{L_{1}(x,y)}\right)+(1-\lambda)\dfrac{L_{2}(x,y)}{L_{\lambda}(x,y)}f\left(\dfrac{M_{2}(x,y)}{L_{2}(x,y)}\right),$

where $M_{\lambda}(x,y)=\lambda M_{1}(x,y)+(1-\lambda)M_{2}(x,y)$ and
$L_{\lambda}(x,y)=\lambda L_{1}(x,y)+(1-\lambda)L_{2}(x,y)$ are the shorthand
notations, and the last inequality indeed holds from the convexity of $f$.

When $\alpha\in(0,1)$, the mapping
$t\mapsto\frac{1}{\alpha-1}\ln(1+(\alpha-1)t)$ is convex, hence
$R_{\alpha}(M\|L)=\frac{1}{\alpha-1}\ln\left(1+(\alpha-1)D_{\alpha}(M\|L)\right)$
is also convex.

When $\alpha\in(1,+\infty)$, for all $\lambda\in(0,1)$ and
$(M,L_{1}),(M,L_{2})\in\mathcal{L}\times\mathcal{L}$, we need to prove

$R_{\alpha}(M\|\lambda L_{1}+(1-\lambda)L_{2})\leq\lambda
R_{\alpha}(M\|L_{1})+(1-\lambda)R_{\alpha}(M\|L_{2}).$

Note that for $L_{\lambda}=\lambda L_{1}+(1-\lambda)L_{2}$, we have

$\displaystyle R_{\alpha}(M\|L_{\lambda})$
$\displaystyle=\widetilde{R}_{\alpha}\left(\widetilde{M}\|\widetilde{L}_{\lambda}\right)$
$\displaystyle=\widetilde{R}_{\alpha}\left(\widetilde{M}\|\lambda\widetilde{L}_{1}+(1-\lambda)\widetilde{L}_{2}\right)$
$\displaystyle\leq\lambda\widetilde{R}_{\alpha}\left(\widetilde{M}\|\widetilde{L}_{1}\right)+(1-\lambda)\widetilde{R}_{\alpha}\left(\widetilde{M}\|\widetilde{L}_{2}\right)$
$\displaystyle=\lambda R_{\alpha}(M\|L_{1})+(1-\lambda)R_{\alpha}(M\|L_{2}),$

where the inequality follows from the convexity of
$\widetilde{R}_{\alpha}(M\|L)$ in $L$ from [35, Theorem 12], and hence
$R_{\alpha}(M\|L)$ is convex in $L$. Similarly, the last item can also be
proved via using
$R_{\alpha}(M\|L)=\widetilde{R}_{\alpha}(\widetilde{M}\|\widetilde{L})$. ∎

The next result proves the monotonicity of the Rényi divergence in $\alpha$:

######  Proposition 3.3 (Monotonicity in $\alpha$).

For $M,L\in\mathcal{L}$ and $\pi\in\mathcal{P}(\mathcal{X})$,
$R_{\alpha}(M\|L)$ is non-decreasing with respect to
$\alpha\in(0,1)\cup(1,+\infty)$.

###### Proof.

For $\alpha,\beta\in(0,1)\cup(1,+\infty)$ and $\alpha<\beta$, the mapping
$t\mapsto t^{\frac{\alpha-1}{\beta-1}}$ is strictly convex when $\alpha<1$ and
strictly concave when $\alpha>1$, hence we have

$\displaystyle R_{\alpha}(M\|L)$
$\displaystyle=\dfrac{1}{\alpha-1}\ln\left(\sum_{x,y\in\mathcal{X}}\pi(x)L(x,y)\left(\dfrac{M(x,y)}{L(x,y)}\right)^{\alpha}\right)$
$\displaystyle=\dfrac{1}{\alpha-1}\ln\left(\sum_{x,y\in\mathcal{X}}\pi(x)M(x,y)\left(\dfrac{M(x,y)}{L(x,y)}\right)^{\alpha-1}\right)$
$\displaystyle=\dfrac{1}{\alpha-1}\ln\left(\sum_{x,y\in\mathcal{X}}\pi(x)M(x,y)\left(\dfrac{M(x,y)}{L(x,y)}\right)^{(\beta-1)\frac{\alpha-1}{\beta-1}}\right)$
$\displaystyle\leq\dfrac{1}{\alpha-1}\ln\left(\sum_{x,y\in\mathcal{X}}\pi(x)M(x,y)\left(\dfrac{M(x,y)}{L(x,y)}\right)^{(\beta-1)}\right)^{\frac{\alpha-1}{\beta-1}}$
$\displaystyle=\dfrac{1}{\beta-1}\ln\left(\sum_{x,y\in\mathcal{X}}\pi(x)M(x,y)\left(\dfrac{M(x,y)}{L(x,y)}\right)^{(\beta-1)}\right)$
$\displaystyle=R_{\beta}(M\|L).$

∎

We naturally extend the notion of Rényi divergence of Markov chains to order
$0,1,+\infty$ in the next result:

######  Proposition 3.4 (Extension of $R_{\alpha}$ to $\alpha=0,1$ and
$+\infty$).

For $M,L\in\mathcal{L}$ and $\pi\in\mathcal{P}(\mathcal{X})$, we define

$\displaystyle R_{0}(M\|L):=\lim_{\alpha\searrow 0}R_{\alpha}(M\|L),\quad
R_{1}(M\|L):=\lim_{\alpha\nearrow 1}R_{\alpha}(M\|L),\quad
R_{\infty}(M\|L):=\lim_{\alpha\nearrow\infty}R_{\alpha}(M\|L),$

then we have

$\displaystyle R_{0}(M\|L)$
$\displaystyle=-\ln\left(\sum_{x,y;~{}M(x,y)>0}\pi(x)L(x,y)\right),$
$\displaystyle R_{1}(M\|L)$
$\displaystyle=\sum_{x,y;~{}L(x,y)>0}\pi(x)M(x,y)\ln\dfrac{M(x,y)}{L(x,y)},$
$\displaystyle R_{\infty}(M\|L)$
$\displaystyle=\ln\left(\max\limits_{x,y;~{}L(x,y)>0}\dfrac{M(x,y)}{L(x,y)}\right),$

where $R_{1}(M\|L)$ is the Kullback-Leibler (KL) divergence from $L$ to $M$,
and we write $D_{KL}(M\|L):=R_{1}(M\|L)$.

###### Proof.

When $0<\alpha<1$, it is easy to see that
$M(x,y)^{\alpha}L(x,y)^{1-\alpha}\leq\alpha M(x,y)+(1-\alpha)L(x,y)$, then by
the dominated convergence theorem, we have

$\displaystyle\lim_{\alpha\searrow 0}R_{\alpha}(M\|L)$
$\displaystyle=\lim_{\alpha\searrow
0}\dfrac{1}{\alpha-1}\ln\sum_{x,y\in\mathcal{X}}\pi(x)L(x,y)\left(\dfrac{M(x,y)}{L(x,y)}\right)^{\alpha}$
$\displaystyle=-\ln\left(\lim_{\alpha\searrow
0}\sum_{M,L>0}\pi(x)L(x,y)\left(\dfrac{M(x,y)}{L(x,y)}\right)^{\alpha}\right)$
$\displaystyle=-\ln\left(\sum_{M,L>0}\pi(x)L(x,y)\right)$
$\displaystyle=-\ln\left(\sum_{M>0}\pi(x)L(x,y)\right).$

Denote
$x_{\alpha}=\sum_{x,y\in\mathcal{X}}\pi(x)L(x,y)\left(\frac{M(x,y)}{L(x,y)}\right)^{\alpha}$.
Similar to the argument above, by the dominated convergence theorem we have
$\lim_{\alpha\nearrow 1}x_{\alpha}=1$. Therefore, we have

$\displaystyle\lim_{\alpha\nearrow 1}R_{\alpha}(M\|L)$
$\displaystyle=\lim_{\alpha\nearrow 1}\dfrac{\ln x_{\alpha}}{\alpha-1}$
$\displaystyle=\lim_{\alpha\nearrow 1}\dfrac{x_{\alpha}-1}{\alpha-1}$
$\displaystyle=\lim_{\alpha\nearrow
1}\sum_{L>0}\pi(x)M(x,y)\left(\dfrac{\left(\frac{M(x,y)}{L(x,y)}\right)^{\alpha-1}-1}{\alpha-1}\right).$

Given $t>0$, the mapping $g:\beta\mapsto\frac{t^{\beta}-1}{\beta}$ is non-
decreasing for $\beta\in(-1,0)$, since
$g^{\prime}(t)=\frac{t^{\beta}}{\beta^{2}}\left(\beta\ln
t-(1-t^{-\beta})\right)=\frac{t^{\beta}}{\beta^{2}}\left((t^{-\beta}-1)-\ln
t^{-\beta}\right)\geq 0$. Hence by monotone convergence theorem, we have

$\displaystyle\lim_{\alpha\nearrow 1}R_{\alpha}(M\|L)$
$\displaystyle=\lim_{\alpha\nearrow
1}\sum_{L>0}\pi(x)M(x,y)\left(\dfrac{\left(\frac{M(x,y)}{L(x,y)}\right)^{\alpha-1}-1}{\alpha-1}\right)$
$\displaystyle=\sum_{M,L>0}\pi(x)M(x,y)\lim_{\alpha\nearrow
1}\left(\dfrac{\left(\frac{M(x,y)}{L(x,y)}\right)^{\alpha-1}-1}{\alpha-1}\right)$
$\displaystyle=\sum_{M,L>0}\pi(x)M(x,y)\ln\dfrac{M(x,y)}{L(x,y)}.$

As to $R_{\infty}(M\|L)$, we have

$\displaystyle\lim_{\alpha\nearrow\infty}R_{\alpha}(M\|L)$
$\displaystyle=\lim_{\alpha\nearrow\infty}\ln\left(\sum_{L>0}\pi(x)M(x,y)\left(\dfrac{M(x,y)}{L(x,y)}\right)^{\alpha-1}\right)^{\frac{1}{\alpha-1}}$
$\displaystyle=\ln\left(\max\limits_{L>0}\dfrac{M(x,y)}{L(x,y)}\right).$

∎

Building upon Proposition 3.4, in the next result we prove various
inequalities between information divergences of Markov chains, and in
particular we give an analogue of Pinsker’s inequality in this context.

######  Proposition 3.5 (Inequalities with other divergences).

For $M,L\in\mathcal{L}$, $\pi\in\mathcal{P}(\mathcal{X})$ and recall the
$f$-divergences as in Definition 2.5, we have

  1. (i).

$\mathrm{Hel}^{2}(M,L)\leq R_{\frac{1}{2}}(M\|L)\leq R_{1}(M\|L)\leq
R_{2}(M\|L)\leq\chi^{2}(M\|L)$.

  2. (ii).

(Pinsker’s inequality)

For $0<\alpha\leq 1$, we have

$\dfrac{\alpha}{2}\mathrm{TV}^{2}(M,L)\leq R_{\alpha}(M\|L).$

###### Proof.

First we observe that

$\displaystyle R_{\frac{1}{2}}(M\|L)$
$\displaystyle=-2\ln\left(1-\dfrac{\mathrm{Hel}^{2}(M,L)}{2}\right),$
$\displaystyle R_{2}(M\|L)$ $\displaystyle=\ln\left(1+\chi^{2}(M\|L)\right),$

then by $\ln t\leq t-1$ for $t>0$, we have $\mathrm{Hel}^{2}(M,L)\leq
R_{\frac{1}{2}}(M\|L)$ and $R_{2}(M\|L)\leq\chi^{2}(M\|L)$.

For probability measures $\mu,\nu$ on finite state space $\Omega$, we denote
$\widetilde{\mathrm{TV}}(\mu,\nu):=\dfrac{1}{2}\sum_{x\in\Omega}|\mu(x)-\nu(x)|$,
then we have

$\displaystyle
R_{\alpha}(M\|L)=\widetilde{R}_{\alpha}\left(\widetilde{M}\|\widetilde{L}\right)$
$\displaystyle\geq\dfrac{\alpha}{2}\widetilde{\mathrm{TV}}^{2}\left(\widetilde{M}\|\widetilde{L}\right)$
$\displaystyle=\dfrac{\alpha}{8}\left(\sum_{x,y\in\mathcal{X}}\left|\pi(x)M(x,y)-\pi(x)L(x,y)\right|\right)^{2}$
$\displaystyle=\dfrac{\alpha}{2}\mathrm{TV}^{2}(M\|L),$

where the inequality follows from [35, Theorem 31]. ∎

We proceed to prove the skew symmetry of equivalence of Rényi divergence of
Markov chains:

######  Proposition 3.6 (Skew symmetry and equivalence).

Given $M,L\in\mathcal{L}$, $\pi\in\mathcal{P}(\mathcal{X})$ and
$0<\alpha<\beta<1$, we have

  1. (i).

$R_{\alpha}(M\|L)=\dfrac{\alpha}{1-\alpha}R_{1-\alpha}(L\|M)$.

  2. (ii).

$\dfrac{\alpha}{\beta}\dfrac{1-\beta}{1-\alpha}R_{\beta}(M\|L)\leq
R_{\alpha}(M\|L)\leq R_{\beta}(M\|L)$.

###### Proof.

Since

$\displaystyle(1-\alpha)R_{\alpha}(M\|L)$
$\displaystyle=-\ln\left(\sum_{M,L>0}\pi(x)M^{\alpha}(x,y)L^{1-\alpha}(x,y)\right),$
$\displaystyle\alpha R_{1-\alpha}(L\|M)$
$\displaystyle=-\ln\left(\sum_{M,L>0}\pi(x)L^{1-\alpha}(x,y)M^{\alpha}(x,y)\right),$

the first item is verified. The second item follows from
$\frac{1-\beta}{\beta}R_{\beta}(M\|L)=R_{1-\beta}(L\|M)$ and
$\frac{1-\alpha}{\alpha}R_{\alpha}(M\|L)=R_{1-\alpha}(L\|M)$. ∎

We prove the Pythagorean inequality and weak triangle inequality of the Rényi
divergence of Markov chains in the following Proposition:

######  Proposition 3.7 (Pythagorean inequality and weak triangle inequality).

Suppose we are given $L\in\mathcal{L}$ and recall that an $\alpha$-projection
$L^{(R_{\alpha})}\in\mathop{\arg\min}_{M\in\mathcal{L}(\pi)}R_{\alpha}(M\|L)$
is introduced in Definition 2.6 and exists. For any $M\in\mathcal{L}(\pi)$ and
$\alpha>0$, we have the following Pythagorean inequality:

$R_{\alpha}(M\|L)\geq
R_{\alpha}(M\|L^{(R_{\alpha})})+R_{\alpha}(L^{(R_{\alpha})}\|L).$ (14)

In addition, for $\alpha>1$ and any $U,V,W\in\mathcal{L}$, we have the weak
triangle inequality

$R_{\alpha}(U\|V)\leq\dfrac{2\alpha-1}{2\alpha-2}R_{2\alpha}(U\|W)+R_{2\alpha-1}(W\|V).$
(15)

###### Proof.

For $\pi\in\mathcal{P}(\mathcal{X})$, we denote the symmetric edge measure
family on $\mathcal{X}\times\mathcal{X}$ as

$\mathcal{E}(\pi):=\left\\{\pi(x)g(x,y):g(x,y)\geq
0,\sum_{y}g(x,y)=1,\pi(x)g(x,y)=\pi(y)g(y,x)\right\\}.$

Then we will prove $\mathcal{E}(\pi)$ is $\alpha$-convex, i.e. for
$P_{0},P_{1}\in\mathcal{E}(\pi)$, $\alpha>0$ and $\lambda\in(0,1)$, there
exists

$P_{\lambda}(x,y):=\dfrac{\left((1-\lambda)P_{0}^{\alpha}(x,y)+\lambda
P_{1}^{\alpha}(x,y)\right)^{\frac{1}{\alpha}}}{\sum_{x,y}\left((1-\lambda)P_{0}^{\alpha}(x,y)+\lambda
P_{1}^{\alpha}(x,y)\right)^{\frac{1}{\alpha}}}\in\mathcal{E}(\pi).$

Actually, we only need to verify that $P_{\lambda}(x,y)$ is symmetric, after
which $G_{\lambda}(x,y):=P_{\lambda}(x,y)/\pi(x)$ is reversible and hence
satisfies the condition for $\mathcal{E}(\pi)$. Actually, we have

$\displaystyle P_{\lambda}(x,y)$
$\displaystyle=\dfrac{\left((1-\lambda)P_{0}^{\alpha}(x,y)+\lambda
P_{1}^{\alpha}(x,y)\right)^{\frac{1}{\alpha}}}{\sum_{x,y}\left((1-\lambda)P_{0}^{\alpha}(x,y)+\lambda
P_{1}^{\alpha}(x,y)\right)^{\frac{1}{\alpha}}}$
$\displaystyle=\dfrac{\left((1-\lambda)P_{0}^{\alpha}(y,x)+\lambda
P_{1}^{\alpha}(y,x)\right)^{\frac{1}{\alpha}}}{\sum_{x,y}\left((1-\lambda)P_{0}^{\alpha}(y,x)+\lambda
P_{1}^{\alpha}(y,x)\right)^{\frac{1}{\alpha}}}$
$\displaystyle=P_{\lambda}(y,x),$

where the second equality follows from the symmetry of $P_{0},P_{1}$.
Moreover, since $\pi(x)>0$, we can define a bijection
$\phi\in\left(\mathcal{L}(\pi),\mathcal{E}(\pi)\right):M(x,y)\mapsto\pi(x)M(x,y)$,
and therefore we have

$\displaystyle R_{\alpha}(M\|L)\geq
R_{\alpha}\left(L^{(R_{\alpha})}\|L\right),\quad\forall M\in\mathcal{L}(\pi)$
$\displaystyle\iff$
$\displaystyle\widetilde{R}_{\alpha}\left(P\|\widetilde{L}\right)\geq\widetilde{R}_{\alpha}\left(\widetilde{L^{(R_{\alpha})}}\|L\right),\quad\forall
P\in\mathcal{E}(\pi),$

which implies
$\widetilde{L^{(R_{\alpha})}}\in\mathop{\arg\min}_{P\in\mathcal{E}(\pi)}\widetilde{R}_{\alpha}\left(P\|\widetilde{L}\right)$.
Thus by [35, Theorem 14], for $M\in\mathcal{L}(\pi)$ and
$\widetilde{M}(x,y)=\pi(x)M(x,y)\in\mathcal{E}(\pi)$, we have

$\displaystyle R_{\alpha}(M\|L)$
$\displaystyle=\widetilde{R}_{\alpha}\left(\widetilde{M}\|\widetilde{L}\right)\geq
R_{\alpha}\left(\widetilde{M}\|\widetilde{L^{(R_{\alpha})}}\right)+R_{\alpha}\left(\widetilde{L^{(R_{\alpha})}}\|\widetilde{L}\right)$
$\displaystyle=R_{\alpha}(M\|L^{(R_{\alpha})})+R_{\alpha}(L^{(R_{\alpha})}\|L),$

which is (14).

To prove the weak triangle inequality, by Cauchy-Schwarz inequality we have

$\displaystyle\sum_{x,y}\pi(x)U^{\alpha}(x,y)V^{1-\alpha}(x,y)$
$\displaystyle=$
$\displaystyle\sum_{x,y}\pi(x)W(x,y)\left(\dfrac{U(x,y)}{W(x,y)}\right)^{\alpha}\left(\dfrac{W(x,y)}{V(x,y)}\right)^{\alpha-1}$
$\displaystyle\leq$
$\displaystyle\left(\sum_{x,y}\pi(x)W(x,y)\left(\dfrac{U(x,y)}{W(x,y)}\right)^{2\alpha}\right)^{1/2}\left(\sum_{x,y}\pi(x)W(x,y)\left(\dfrac{W(x,y)}{V(x,y)}\right)^{2\alpha-2}\right)^{1/2},$

taking logarithm we have

$(\alpha-1)R_{\alpha}(U\|V)\leq\dfrac{2\alpha-1}{2}R_{2\alpha}(U\|W)+\dfrac{2\alpha-2}{2}R_{2\alpha-1}(W\|V),$

which is (15). ∎

######  Remark 3.1.

Using Proposition 3.7, the uniqueness of $\alpha$-projection can be easily
verified. Suppose $L_{1}^{(R_{\alpha})}$ and $L_{2}^{(R_{\alpha})}$ are two
$\alpha$-projections, then by (14) we have

$R_{\alpha}\left(L_{2}^{(R_{\alpha})}\|L\right)\geq
R_{\alpha}\left(L_{2}^{(R\alpha)}\|L_{1}^{(R_{\alpha})}\right)+R_{\alpha}\left(L_{1}^{(R_{\alpha})}\|L\right),$

which implies
$R_{\alpha}\left(L_{2}^{(R_{\alpha})}\|L_{1}^{(R_{\alpha})}\right)=0$ and
therefore $L_{1}^{(R_{\alpha})}=L_{2}^{(R_{\alpha})}$ by Proposition 3.1.

The next result introduces the notion of Chernoff information of Markov
chains:

######  Proposition 3.8 (Chernoff information).

For $\alpha>0$, $M,L\in\mathcal{L}$ and $\pi\in\mathcal{P}(\mathcal{X})$, we
have

$(1-\alpha)R_{\alpha}(M\|L)=\inf_{P\in\mathcal{L}}\left\\{\alpha
D_{KL}(P\|M)+(1-\alpha)D_{KL}(P\|L)\right\\}.$ (16)

Moreover, if $D_{KL}(M\|L)<\infty$, we have the saddle property

$\displaystyle\sup_{\alpha>0}\inf_{P\in\mathcal{L}}\left\\{\alpha
D_{KL}(P\|M)+(1-\alpha)D_{KL}(P\|L)\right\\}$ (17) $\displaystyle=$
$\displaystyle\inf_{P\in\mathcal{L}}\sup_{\alpha>0}\left\\{\alpha
D_{KL}(P\|M)+(1-\alpha)D_{KL}(P\|L)\right\\},$

where we call (17) as the Chernoff information with respect to $M,L$.

###### Proof.

Following the proof in Proposition 3.7, we denote the edge measure family

$\mathcal{P}_{e}:=\left\\{\pi(x)g(x,y):g(x,y)\geq
0,\sum_{y}g(x,y)=1\right\\},$

then we have $\mathcal{E}(\pi)\subset\mathcal{P}_{e}$, and there exists a
bijection from $\mathcal{L}$ to $\mathcal{P}_{e}$. Therefore, by [35, Theorem
30] we have

$\displaystyle\inf_{P\in\mathcal{L}}\left\\{\alpha
D_{KL}(P\|M)+(1-\alpha)D_{KL}(P\|L)\right\\}$ $\displaystyle=$
$\displaystyle\inf_{P\in\mathcal{L}}\left\\{\alpha\widetilde{R}_{1}\left(\widetilde{P}\|\widetilde{M}\right)+(1-\alpha)\widetilde{R}_{1}\left(\widetilde{P}\|\widetilde{L}\right)\right\\}$
$\displaystyle=$
$\displaystyle\inf_{Q\in\mathcal{P}_{e}}\left\\{\alpha\widetilde{R}_{1}\left(Q\|\widetilde{M}\right)+(1-\alpha)\widetilde{R}_{1}\left(Q\|\widetilde{L}\right)\right\\}$
$\displaystyle=$
$\displaystyle(1-\alpha)\widetilde{R}_{\alpha}\left(\widetilde{M}\|\widetilde{L}\right)$
$\displaystyle=$ $\displaystyle(1-\alpha)R_{\alpha}(M\|L).$

For the saddle property, the proof is similar by using [35, Theorem 32]. ∎

In Section 4.1, we will illustrate the role of Chernoff information in
estimating the Bayesian error of binary hypothesis testing between two
transition matrices.

The final result of this section discusses some properties of the ergodicity
or contraction coefficients as introduced in Definition 2.7. In particular,
these results offer a bridge and connect $\eta^{f},\eta^{(R_{\alpha})}$ with
their counterparts such as
$\widetilde{\eta}^{f},\widetilde{\eta}^{(R_{\alpha})}$, thus transferring
properties from one to another. We shall also see in the proof that many of
the properties of these coefficients are inherited from analogous properties
of their respective information divergences such as $D_{f}$ or $R_{\alpha}$.

######  Proposition 3.9 (Ergodicity coefficients).

Given $P\in\mathcal{L}$, $\pi\in\mathcal{P}(\mathcal{X})$,
$\alpha\in(0,1)\cup(1,+\infty)$ and $f$ being a convex function on
$\mathbb{R}$ with $f(1)=0$, we have

  1. (i).

(Non-negativity and normalization)

$0\leq\eta^{f}(P)\leq\eta^{(\mathrm{TV})}(P)\leq 1$,
$0\leq\eta^{(R_{\alpha})}(P)\leq 1$ and
$0\leq\widetilde{\eta}^{(R_{\alpha})}(P)\leq 1$.

  2. (ii).

(Ergodicity coefficients on the space $\mathcal{P}(\mathcal{X})$ are the same
as that on the space $\mathcal{L}$)

$\eta^{f}(P)=\widetilde{\eta}^{f}(P)$ and
$\eta^{(R_{\alpha})}(P)\geq\widetilde{\eta}^{(R_{\alpha})}(P)$.

  3. (iii).

(Bounds) Suppose that the sequence $(U^{*}_{n},V^{*}_{n})$ approaches
$\eta^{(R_{\alpha})}(P)$, and the sequence $(\mu^{*}_{n},\nu^{*}_{n})$
approaches $\widetilde{\eta}^{R_{\alpha}}(P)$, that is,

$\displaystyle\eta^{(R_{\alpha})}(P)$
$\displaystyle=\lim_{n\to\infty}\dfrac{R_{\alpha}(U^{*}_{n}P\|V^{*}_{n}P)}{R_{\alpha}(U^{*}_{n}\|V^{*}_{n})},\quad\widetilde{\eta}^{(R_{\alpha})}(P)=\lim_{n\to\infty}\dfrac{\widetilde{R}_{\alpha}(\mu^{*}_{n}P\|\nu^{*}_{n}P)}{\widetilde{R}_{\alpha}(\mu^{*}_{n}\|\nu^{*}_{n})},$

and by passing to a subsequence if necessary, we assume that
$(U^{*}_{n},V^{*}_{n})\rightarrow(U^{*},V^{*})$ and
$(\mu^{*}_{n},\nu^{*}_{n})\rightarrow(\mu^{*},\nu^{*})$ pointwise. We then
have, for $\alpha>1$,

$\displaystyle\eta^{(D_{\alpha})}(P)$
$\displaystyle\leq\eta^{(R_{\alpha})}(P)\leq\begin{cases}\dfrac{\ln(1+(\alpha-1)\eta^{(D_{\alpha})}(P)D_{\alpha}(U^{*}\|V^{*}))}{\ln(1+(\alpha-1)D_{\alpha}(U^{*}\|V^{*}))}\leq
1,\quad&\textrm{if }\,U^{*}\neq V^{*},\\\ \eta^{(D_{\alpha})}(P)\leq
1,\quad&\textrm{if }\,U^{*}=V^{*},\end{cases}$
$\displaystyle\widetilde{\eta}^{(D_{\alpha})}(P)$
$\displaystyle\leq\widetilde{\eta}^{(R_{\alpha})}(P)\leq\begin{cases}\dfrac{\ln(1+(\alpha-1)\widetilde{\eta}^{(D_{\alpha})}(P)\widetilde{D}_{\alpha}(\mu^{*}\|\nu^{*}))}{\ln(1+(\alpha-1)\widetilde{D}_{\alpha}(\mu^{*}\|\nu^{*}))}\leq
1,\quad&\textrm{if }\,\mu^{*}\neq\nu^{*},\\\
\widetilde{\eta}^{(D_{\alpha})}(P)\leq 1,\quad&\textrm{if
}\,\mu^{*}=\nu^{*},\end{cases}$

while for $\beta\in(0,1)$, we have

$\displaystyle\eta^{(R_{\beta})}(P)$
$\displaystyle\leq\eta^{(D_{\beta})}(P),\quad\widetilde{\eta}^{(R_{\beta})}(P)\leq\widetilde{\eta}^{(D_{\beta})}(P).$

  4. (iv).

(Convexity)

The mappings $\mathcal{L}\ni P\mapsto\eta^{f}(P)$ and $\mathcal{L}\ni
P\mapsto\eta^{(R_{\alpha})}(P)$ are convex if $\alpha\in(0,1)$.

  5. (v).

(Submultiplicativity)

For $P,Q\in\mathcal{L}$, we have

$\eta^{f}(PQ)\leq\eta^{f}(P)\eta^{f}(Q).$

  6. (vi).

(Symmetry)

If $\alpha\in(0,1)$, then $\eta^{(R_{\alpha})}(P)=\eta^{(R_{1-\alpha})}(P)$
and $\eta^{(D_{\alpha})}(P)=\eta^{(D_{1-\alpha})}(P)$.

  7. (vii).

(Equivalence)

For $0<\alpha<\beta<1$, we have

$\dfrac{\alpha}{\beta}\dfrac{1-\beta}{1-\alpha}\eta^{(R_{\beta})}(P)\leq\eta^{(R_{\alpha})}(P)\leq\dfrac{\beta}{\alpha}\dfrac{1-\alpha}{1-\beta}\eta^{(R_{\beta})}(P).$

  8. (viii).

(Scrambling)

$P$ is scrambling if and only if any one (and hence all) of the following
ergodicity coefficients is less than $1$:

$\eta^{f}(P),\eta^{(D_{\alpha})}(P),\eta^{(R_{\beta})}(P),\widetilde{\eta}^{(D_{\alpha})}(P),\widetilde{\eta}^{(R_{\beta})}(P)<1,$

where $\beta>1$.

  9. (ix).

(Unit rank and independence)

Let $f$ be strictly convex at $1$. Then $P$ has unit rank if and only if any
one (and hence all) of the following ergodicity coefficients equals to $0$:

$\eta^{f}(P),\eta^{(D_{\alpha})}(P),\eta^{(R_{\beta})}(P),\widetilde{\eta}^{(D_{\alpha})}(P),\widetilde{\eta}^{(R_{\beta})}(P)=0,$

where $\beta>1$.

###### Proof.

Item (i).: Using item (ii). and the property that
$0\leq\widetilde{\eta}^{f}(P)\leq\widetilde{\eta}^{(\mathrm{TV})}(P)\leq 1$
from [24, Theorem 4.1], we see that $\eta^{f}(P)\in[0,1]$. By item (iii).,
$\eta^{(R_{\alpha})}(P),\widetilde{\eta}^{(R_{\alpha})}(P)\in[0,1]$.

Item (ii).: We first prove that $\widetilde{\eta}^{f}(P)\geq\eta^{f}(P)$. Fix
$M,L,P\in\mathcal{L}$. Using (3) twice, we see that

$\displaystyle D_{f}(MP\|LP)$
$\displaystyle=\sum_{x\in\mathcal{X}}\pi(x)\widetilde{D}_{f}(MP(x,\cdot)\|LP(x,\cdot))$
$\displaystyle\leq\sum_{x\in\mathcal{X}}\pi(x)\widetilde{\eta}_{f}(P)\widetilde{D}_{f}(M(x,\cdot)\|L(x,\cdot))$
$\displaystyle=\widetilde{\eta}^{f}(P)D_{f}(M\|L),$

where the inequality follows from the definition of $\widetilde{\eta}^{f}(P)$.
Taking supremum over $M,L$ with $M\neq L$ yields the desired result.

Next, we prove the opposite inequality that
$\widetilde{\eta}^{f}(P)\leq\eta^{f}(P)$ and
$\widetilde{\eta}^{(R_{\alpha})}(P)\leq\eta^{(R_{\alpha})}(P)$. Fix
$\mu,\nu\in\mathcal{P}(\mathcal{X})$, and let $U(x,\cdot)=\mu,V(x,\cdot)=\nu$
for all $x\in\mathcal{X}$. Using the definitions of $D_{f}$ and
$\widetilde{D}_{f}$, we thus see that

$D_{f}(UP\|VP)=\widetilde{D}_{f}(\mu P\|\nu P),$

which yields

$R_{\alpha}(UP\|VP)=\widetilde{R}_{\alpha}(\mu P\|\nu P),$

and hence

$\displaystyle\eta^{f}(P)$
$\displaystyle\geq\sup_{\mu\neq\nu;U(x,\cdot)=\mu,V(x,\cdot)=\nu}\dfrac{D_{f}(UP\|VP)}{D_{f}(U\|V)}=\sup_{\mu\neq\nu}\dfrac{\widetilde{D}_{f}(\mu
P\|\nu P)}{\widetilde{D}_{f}(\mu\|\nu)}=\widetilde{\eta}^{f}(P),$
$\displaystyle\eta^{(R_{\alpha})}(P)$
$\displaystyle\geq\sup_{\mu\neq\nu;U(x,\cdot)=\mu,V(x,\cdot)=\nu}\dfrac{R_{\alpha}(UP\|VP)}{R_{\alpha}(U\|V)}=\sup_{\mu\neq\nu}\dfrac{\widetilde{R}_{\alpha}(\mu
P\|\nu
P)}{\widetilde{R}_{\alpha}(\mu\|\nu)}=\widetilde{\eta}^{(R_{\alpha})}(P).$

Therefore we have $\widetilde{\eta}^{f}(P)=\eta^{f}(P)$ and
$\eta^{(R_{\alpha})}(P)\geq\widetilde{\eta}^{(R_{\alpha})}(P)$.

Item (iii).: We first prove the second case. For any
$\mu,\nu\in\mathcal{P}(\mathcal{X})$, we see that

$\displaystyle\widetilde{R}_{\alpha}(\mu P\|\nu P)$
$\displaystyle=\dfrac{1}{\alpha-1}\ln(1+(\alpha-1)\widetilde{D}_{\alpha}(\mu
P\|\nu P))$
$\displaystyle\leq\widetilde{\eta}^{(R_{\alpha})}(P)\dfrac{1}{\alpha-1}\ln(1+(\alpha-1)\widetilde{D}_{\alpha}(\mu\|\nu))$
$\displaystyle\leq\dfrac{1}{\alpha-1}\ln(1+\widetilde{\eta}^{(R_{\alpha})}(P)(\alpha-1)\widetilde{D}_{\alpha}(\mu\|\nu)),$

where the first inequality follows from the definition of
$\widetilde{\eta}^{(R_{\alpha})}(P)$ and the second inequality stems from
$\alpha>1$ and the inequality

$\displaystyle(1+x)^{a}$ $\displaystyle\leq 1+ax$ (18)

for $x>-1$ and $a\in[0,1]$. Rearranging the above inequalities give

$\displaystyle\widetilde{D}_{\alpha}(\mu P\|\nu P)$
$\displaystyle\leq\widetilde{\eta}^{(R_{\alpha})}(P)\widetilde{D}_{\alpha}(\mu\|\nu),$

and hence

$\widetilde{\eta}^{(D_{\alpha})}(P)\leq\widetilde{\eta}^{(R_{\alpha})}(P).$

On the other hand, using the definition of
$\widetilde{\eta}^{(D_{\alpha})}(P)$, we see that

$\displaystyle\widetilde{D}_{\alpha}(\mu^{*}_{n}P\|\nu^{*}_{n}P))\leq\widetilde{\eta}^{(D_{\alpha})}(P)\widetilde{D}_{\alpha}(\mu^{*}_{n}\|\nu^{*}_{n}),$

and applying the non-decreasing transformation
$t\mapsto\frac{1}{\alpha-1}\ln(1+(\alpha-1)t)$ gives

$\displaystyle\widetilde{R}_{\alpha}(\mu^{*}_{n}P\|\nu^{*}_{n}P))\leq\dfrac{1}{\alpha-1}\ln(1+(\alpha-1)\widetilde{\eta}^{(D_{\alpha})}(P)\widetilde{D}_{\alpha}(\mu^{*}_{n}\|\nu^{*}_{n})).$

Now, we divide both sides by
$\widetilde{R}_{\alpha}(\mu^{*}_{n}\|\nu^{*}_{n})>0$ and pass to $n\to\infty$
to yield

$\widetilde{\eta}^{(R_{\alpha})}(P)\leq\lim_{n\to\infty}\dfrac{\ln(1+(\alpha-1)\widetilde{\eta}^{(D_{\alpha})}(P)\widetilde{D}_{\alpha}(\mu^{*}_{n}\|\nu^{*}_{n}))}{\ln(1+(\alpha-1)\widetilde{D}_{\alpha}(\mu^{*}_{n}\|\nu^{*}_{n}))}\leq
1.$

The remaining inequalities can be obtained analogously by simply replacing
$\mu^{*}_{n},\nu^{*}_{n}$ by $U_{n},V_{n}$ respectively and
$\widetilde{D}_{\alpha},\widetilde{R}_{\alpha}$ by their untilded
counterparts.

For the case of $\beta\in(0,1)$, similar to the reasoning above we obtain that

$\displaystyle\widetilde{\eta}^{(R_{\beta})}(P)\leq\begin{cases}\dfrac{\ln(1+(\beta-1)\widetilde{\eta}^{(D_{\beta})}(P)\widetilde{D}_{\beta}(\mu^{*}\|\nu^{*}))}{\ln(1+(\beta-1)\widetilde{D}_{\beta}(\mu^{*}\|\nu^{*}))}\leq\widetilde{\eta}^{(D_{\beta})}(P),\quad&\textrm{if
}\,\mu^{*}\neq\nu^{*},\\\ \widetilde{\eta}^{(D_{\beta})}(P),\quad&\textrm{if
}\,\mu^{*}=\nu^{*},\end{cases}$

where we use again (18) in the second inequality and $\beta\in(0,1)$.

Item (iv).: First, we note that he mapping
$P\mapsto\eta^{f}(P)=\widetilde{\eta}^{f}(P)$ is convex according to [24,
Section 4]. Next, for $P,M\neq L\in\mathcal{L}$, the ratio

$\displaystyle(M,L)\mapsto\dfrac{R_{\alpha}(MP\|LP)}{R_{\alpha}(M\|L)}$

is jointly convex when $\alpha\in(0,1)$ by Proposition 3.2, and taking the
supremum over $M\neq L$ preserves its convexity.

Item (v).: It follows readily from item (ii). and the submultiplicativity of
$\widetilde{\eta}^{f}$ as in [24, Section $4$].

Item (vi).: Thanks to the skew symmetry property of $R_{\alpha}$ as in
Proposition 3.6, we see that for $P,M\neq L\in\mathcal{L}$,

$\displaystyle\dfrac{R_{\alpha}(MP\|LP)}{R_{\alpha}(M\|L)}$
$\displaystyle=\dfrac{R_{1-\alpha}(LP\|MP)}{R_{1-\alpha}(L\|M)},$

which yields the desired result by taking the supremum over $M\neq
L\in\mathcal{L}$. The analogous result for $D_{\alpha}$ holds due to the skew
symmetry of $D_{\alpha}$, that is,
$D_{\alpha}(M\|L)=\frac{\alpha}{1-\alpha}D_{\alpha}(L\|M)$.

Item (vii).: It follows directly from the equivalence property of $R_{\alpha}$
in Proposition 3.6.

Item (viii).: If $P$ is scrambling, then according to [24, Theorem 4.2],
$\eta^{f}(P)<1$. In particular,
$\eta^{(D_{\alpha})}(P)=\widetilde{\eta}^{(D_{\alpha})}(P)<1$ by item (ii)..
By item (iv)., this yields
$\eta^{(R_{\beta})}(P),\widetilde{\eta}^{(R_{\beta})}(P)<1$. On the other
hand, if $P$ is not scrambling, then by [24, Theorem 4.2] again,
$\eta^{f}(P)=1$. In particular,
$\eta^{(D_{\alpha})}(P)=\widetilde{\eta}^{(D_{\alpha})}(P)=1$ by item (ii)..
Using again item (iv)., this yields
$\eta^{(R_{\beta})}(P),\widetilde{\eta}^{(R_{\beta})}(P)=1$.

Item (ix).: Using [24, Section 4], unit rank of $P$ is equivalent to
$\eta^{f}(P)=0$. The rest of the proof is similar to that of item (viii). and
is omitted. ∎

######  Remark 3.2.

In Proposition 3.9 item (viii)., a transition matrix $P\in\mathcal{L}$ is
called scrambling if for each pair of rows
$(x,y)\in\mathcal{X}\times\mathcal{X}$, there exists a column
$z\in\mathcal{X}$ such that $P(x,z),P(y,z)>0$, i.e.

$\min_{x,y\in\mathcal{X}}\sum_{z\in\mathcal{X}}P(x,z)\wedge P(y,z)>0,$

and this means that every two rows of $P$ are not orthogonal, see [33, Theorem
3.1].

In Section 4.3, we will use the ergodicity coefficients to give the
relationship between Cesàro mixing time and classical mixing time.

##  4 Applications

The main aim of this section is to provide applications of these notions of
information divergences and ergodicity coefficients in the context of Markov
chain mixing and binary hypothesis testing.

###  4.1 Binary hypothesis testing between Markov chains

Given $n$ pairs of i.i.d. data
$\left\\{(X_{1},Y_{1}),(X_{2},Y_{2}),...,(X_{n},Y_{n})\right\\}$ which are
observed from an arbitrary inital distribution
$\pi\in\mathcal{P}(\mathcal{X})$ and transition matrix $P$, i.e.
$X_{i}\sim\pi$ and $Y_{i}|X_{i}\sim P(X_{i},\cdot)$. Note that in this section
$\pi\in\mathcal{P}(\mathcal{X})$ is given and needs not be the stationary
distribution of $P$. Then, we consider the following hypothesis testing
problem between transition matrices:

$H_{0}:P=P_{0}\quad\longleftrightarrow\quad
H_{1}:P=P_{1},\quad\pi\enspace\text{is known}.$ (19)

Denote $Z_{i}:=(X_{i},Y_{i})\in\mathcal{X}\times\mathcal{X}$, therefore
$Z_{i}$ follows the edge measure $Z_{i}\sim Q(x,y):=\pi(x)P(x,y)$, and the
hypothesis testing (19) is equivalent to the following hypothesis testing
between edge measures:

$H_{0}^{\prime}:Q=Q_{0}\quad\longleftrightarrow\quad H_{1}^{\prime}:Q=Q_{1},$
(20)

where $Q_{i}(x,y)=\pi(x)P_{i}(x,y)$ for $i=0,1$.

Now, let $A_{n}\subseteq(\mathcal{X}\times\mathcal{X})^{n}$ be the region of
rejecting $H_{0}$ or $H_{0}^{\prime}$, and $A_{n}^{c}$ be the region of
accepting $H_{0}$ or $H_{0}^{\prime}$, then the first and second type error
are

$\alpha_{n}:=Q_{0}^{n}(A_{n}),\quad\beta_{n}:=Q_{1}^{n}(A_{n}^{c}),$ (21)

where $Q_{0}^{n}$ and $Q_{1}^{n}$ are extended measures from
$\mathcal{X}\times\mathcal{X}$ to $(\mathcal{X}\times\mathcal{X})^{n}$. Using
[25, Theorem 11.7.1] to apply Neyman-Pearson lemma on (20), we can find that
the optimal test for both (19) and (20) has the form of likelihood ratio test,
i.e.

$A_{n}=A_{n}(T)=\left\\{\mathbb{z}=(z_{1},z_{2},...,z_{n})\in(\mathcal{X}\times\mathcal{X})^{n}:\dfrac{Q_{0}(z_{1})Q_{0}(z_{2})...Q_{0}(z_{n})}{Q_{1}(z_{1})Q_{1}(z_{2})...Q_{1}(z_{n})}<T\right\\},$
(22)

where there is a slight abuse of notation regarding $Q_{0}$ and $Q_{1}$. Then,
we have the following asymptotic equipartition property (AEP):

######  Theorem 4.1.

Let $\\{Z_{i}=(X_{i},Y_{i})\\}_{i=1}^{n}$ be i.i.d. random variables drawn
from $Q_{0}(x,y)=\pi(x)P_{0}(x,y)$. For another edge measure
$Q_{1}(x,y)=\pi(x)P_{1}(x,y)$, we have

$\dfrac{1}{n}\ln\dfrac{Q_{0}(Z_{1})Q_{0}(Z_{2})...Q_{0}(Z_{n})}{Q_{1}(Z_{1})Q_{1}(Z_{2})...Q_{1}(Z_{n})}\xrightarrow{a.s.}R_{1}(P_{0}\|P_{1})\quad
as\enspace n\rightarrow\infty,$ (23)

where we recall that $R_{1}(P_{0}\|P_{1})$ is the $\mathrm{KL}$ divergence
from $P_{1}$ to $P_{0}$ as defined in Proposition 3.4.

###### Proof.

By strong law of large numbers, recalling the definition of
$R_{1}(P_{0}\|P_{1})$ defined in Proposition 3.4, we have

$\displaystyle\dfrac{1}{n}\ln\dfrac{Q_{0}(Z_{1})Q_{0}(Z_{2})...Q_{0}(Z_{n})}{Q_{1}(Z_{1})Q_{1}(Z_{2})...Q_{1}(Z_{n})}$
$\displaystyle=\dfrac{1}{n}\sum_{i=1}^{n}\ln\dfrac{Q_{0}(Z_{i})}{Q_{1}(Z_{i})}$
$\displaystyle\xrightarrow{a.s.}\mathbb{E}_{Z_{1}\sim
Q_{0}}\left[\ln\dfrac{Q_{0}(Z_{1})}{Q_{1}(Z_{1})}\right]$
$\displaystyle=\sum_{x,y}\pi(x)P_{0}(x,y)\ln\dfrac{P_{0}(x,y)}{P_{1}(x,y)}=R_{1}(P_{0}\|P_{1}).$

∎

Next, we will consider the Bayesian case. Suppose $P=P_{0}$ has a prior
probability $\pi_{0}$ and $P=P_{1}$ has a prior probability $\pi_{1}$, where
$\pi_{0}+\pi_{1}=1$ and $0<\pi_{0}<1$. Then, the overall Bayesian error for
both (19) and (20) is

$P_{e}(A_{n})=\pi_{0}\alpha_{n}+\pi_{1}\beta_{n},$ (24)

and we need to estimate the best achievable Bayesian error

$\displaystyle P_{e}^{*}(n)$
$\displaystyle:=\inf_{A_{n}\subseteq(\mathcal{X}\times\mathcal{X})^{n}}P_{e}(A_{n})$
(25)
$\displaystyle=\inf_{A_{n}\subseteq(\mathcal{X}\times\mathcal{X})^{n}}\left\\{\pi_{0}Q_{0}^{n}(A_{n})+\pi_{1}Q_{1}^{n}(A_{n}^{c})\right\\}.$

Before presenting the estimation of $P_{e}^{*}(n)$, we will first give a
rigorous definition of Chernoff information between transition matrices
$P_{0}$ and $P_{1}$:

$\displaystyle C(P_{0},P_{1})$ $\displaystyle:=\max_{0\leq\alpha\leq
1}(1-\alpha)R_{\alpha}(P_{0}\|P_{1})$ (26)
$\displaystyle=\max_{0\leq\alpha\leq
1}-\ln\sum_{x,y}\pi(x)P_{0}^{\alpha}(x,y)P_{1}^{1-\alpha}(x,y).$ (27)

When $\alpha>1$, $(1-\alpha)R_{\alpha}(P_{0}\|P_{1})\leq 0$, hence (26) is in
accordance with 17 in Proposition 3.8 using (16), that is,

$\displaystyle\sup_{\alpha>0}\inf_{P\in\mathcal{L}}\left\\{\alpha
D_{KL}(P\|M)+(1-\alpha)D_{KL}(P\|L)\right\\}$
$\displaystyle=\sup_{\alpha>0}(1-\alpha)R_{\alpha}(P_{0}\|P_{1})$
$\displaystyle=\max_{0\leq\alpha\leq 1}(1-\alpha)R_{\alpha}(P_{0}\|P_{1}).$

Then, we have the following result using Chernoff information.

######  Theorem 4.2.

Recalling the best achievable Bayesian error defined in (25), we have

$\lim_{n\rightarrow\infty}-\dfrac{1}{n}\ln P_{e}^{*}(n)=C(P_{0},P_{1}),$ (28)

###### Proof.

According to [25, Theorem 11.9.1], denote

$Q_{\lambda}(x,y):=\dfrac{Q_{0}^{\lambda}(x,y)Q_{1}^{1-\lambda}(x,y)}{\sum_{x,y}Q_{0}^{\lambda}(x,y)Q_{1}^{1-\lambda}(x,y)},$

then we have

$\displaystyle\lim_{n\rightarrow\infty}-\dfrac{1}{n}\ln P_{e}^{*}(n)$
$\displaystyle=\max_{0\leq\lambda\leq
1}\min\left\\{\widetilde{R}_{1}(Q_{\lambda}\|Q_{0}),\widetilde{R}_{1}(Q_{\lambda}\|Q_{1})\right\\}$
$\displaystyle=\max_{0\leq\alpha\leq
1}-\ln\sum_{x,y}Q_{0}^{\alpha}(x,y)Q_{1}^{1-\alpha}(x,y).$

Since

$\sum_{x,y}Q_{0}^{\alpha}(x,y)Q_{1}^{1-\alpha}(x,y)=\sum_{x,y}\pi(x)P_{0}^{\alpha}(x,y)P_{1}^{1-\alpha}(x,y),$

and by the definition of $C(P_{0},P_{1})$ in (26), the statement is verified.
∎

###  4.2 Information-theoretic mixing times and their spectral bounds

For given $\varepsilon>0$ and transition matrix $P\in\mathcal{L}$ which admits
$\pi$ as its stationary distribution, we first introduce three notions of
average mixing times based upon suitable information divergences. We define
the $\pi$-weighted $\alpha$-divergence mixing time, $\pi$-weighted Rényi
divergence mixing time of the order $\alpha\in(0,1)\cup(1,+\infty)$ and the
$\pi$-weighted total variation distance mixing time to be respectively

$\displaystyle\bar{t}_{\mathrm{mix}}^{(D_{\alpha})}(\varepsilon,P)$
$\displaystyle:=\inf\left\\{t>0:D_{\alpha}(P^{t}\|\Pi)<\varepsilon\right\\},$
(29) $\displaystyle\bar{t}_{\mathrm{mix}}^{(R_{\alpha})}(\varepsilon,P)$
$\displaystyle:=\inf\left\\{t>0:R_{\alpha}(P^{t}\|\Pi)<\varepsilon\right\\},$
(30) $\displaystyle\bar{t}_{\mathrm{mix}}^{(\mathrm{TV})}(\varepsilon,P)$
$\displaystyle:=\inf\left\\{t>0:\mathrm{TV}(P^{t},\Pi)<\varepsilon\right\\},$
(31)

where $\Pi$ is a $|\mathcal{X}|\times|\mathcal{X}|$ matrix with each row being
$\pi$, i.e. $\Pi(x,y)=\pi(y)$, for all $x,y\in\mathcal{X}$. These average
mixing times can be used to assess the quantitative convergence rate of the
transition matrix $P^{t}$ towards $\Pi$. In the first main result below, we
obtain spectral bounds of these mixing times in terms of $\gamma_{*}$, the
absolute spectral gap of $P$, which is defined as

$\lambda_{*}:=\max\left\\{|\lambda|:\lambda\enspace\text{is an eigenvalue
of}\enspace P,\enspace\lambda\neq 1\right\\},$

and we also call $\gamma_{*}:=1-\lambda_{*}$ as the absolute spectral gap of
$P$. By [28, Lemma 12.1], if $P$ is aperiodic and irreducible, then
$\gamma_{*}>0$.

######  Theorem 4.3.

Let $P\in\mathcal{L}(\pi)$ be an irreducible, aperiodic and $\pi$-reversible
transition matrix, and we denote $\pi_{\mathrm{min}}:=\min_{x}\pi(x)>0$. For
$\alpha\in(0,1)\cup(1,+\infty)$, if
$\varepsilon<\min\left\\{\frac{1}{2|\alpha-1|},\frac{4\alpha}{|\alpha-1|}\right\\}$,
we have

$\displaystyle\bar{t}_{\mathrm{mix}}^{(D_{\alpha})}(\varepsilon,P)$
$\displaystyle\leq\begin{cases}\dfrac{1}{\gamma_{*}}\left(\ln\dfrac{2\alpha}{(\alpha-1)\pi_{\mathrm{min}}}+\ln\dfrac{1}{\varepsilon}\right),\quad\textrm{if
}\,\alpha>1,\\\
\dfrac{1}{\gamma_{*}}\left(\ln\dfrac{8\alpha}{(1-\alpha)\pi_{\mathrm{min}}}+\ln\dfrac{1}{\varepsilon}\right),\quad\textrm{if
}\,0<\alpha<1,\end{cases}$

and

$\displaystyle\bar{t}_{\mathrm{mix}}^{(D_{\alpha})}(\varepsilon,P)$
$\displaystyle\geq\begin{cases}\dfrac{1}{2\ln\frac{1}{1-\gamma_{*}}}\left(\ln\dfrac{\pi_{\mathrm{min}}^{2}}{8}+\ln\dfrac{1}{\varepsilon}\right),\quad\textrm{if
}\,\alpha>1,\\\
\dfrac{1}{2\ln\frac{1}{1-\gamma_{*}}}\left(\ln\dfrac{\pi_{\mathrm{min}}^{2}\alpha}{16}+\ln\dfrac{1}{\varepsilon}\right),\quad\textrm{if
}\,0<\alpha<1,\end{cases}$

where $\gamma_{*}$ is the absolute spectral gap of $P$.

###### Proof.

$P$ is irreducible and aperiodic implies $\gamma_{*}>0$. According to [28,
Eq.12.13], we have

$\left|\dfrac{P^{t}(x,y)}{\pi(y)}-1\right|\leq\dfrac{(1-\gamma_{*})^{t}}{\sqrt{\pi(x)\pi(y)}}\leq\dfrac{e^{-\gamma_{*}t}}{\pi_{\text{min}}}.$
(32)

Then, for $\alpha\in(0,1)\cup(1,+\infty)$, we rewrite $D_{\alpha}(P^{t}\|\Pi)$
as

$\displaystyle D_{\alpha}(P^{t}\|\Pi)$
$\displaystyle=\dfrac{1}{\alpha-1}\sum_{x}\pi(x)\sum_{y}\Pi(x,y)\left(\left(\dfrac{P^{t}(x,y)}{\Pi(x,y)}\right)^{\alpha}-1\right)$
$\displaystyle=\dfrac{1}{\alpha-1}\sum_{x}\pi(x)\sum_{y}\pi(y)\left(\left(\dfrac{P^{t}(x,y)}{\pi(y)}\right)^{\alpha}-1\right).$

Note that for $x\geq-1$, when $\alpha>1$,
$\left|(1+x)^{\alpha}-1\right|\leq(1+|x|)^{\alpha}-1$. Moreover, for $x,y>0$,
it can be easily verified that $\left(1+\frac{x}{y}\right)^{y}<e^{x}$.
Therefore, using (32), for $\alpha>1$, we have

$\displaystyle D_{\alpha}(P^{t}\|\Pi)$
$\displaystyle=\dfrac{1}{\alpha-1}\sum_{x}\pi(x)\sum_{y}\pi(y)\left(\left(1+\dfrac{P^{t}(x,y)}{\pi(y)}-1\right)^{\alpha}-1\right)$
$\displaystyle\leq\dfrac{1}{\alpha-1}\sum_{x}\pi(x)\sum_{y}\pi(y)\left(\left(1+\left|\dfrac{P^{t}(x,y)}{\pi(y)}-1\right|\right)^{\alpha}-1\right)$
$\displaystyle\leq\dfrac{1}{\alpha-1}\sum_{x}\pi(x)\sum_{y}\pi(y)\left(\exp\left(\alpha\left|\dfrac{P^{t}(x,y)}{\pi(y)}-1\right|\right)-1\right)$
$\displaystyle\leq\dfrac{1}{\alpha-1}\left(\exp\left(\dfrac{\alpha}{\pi_{\mathrm{min}}}e^{-\gamma_{*}t}\right)-1\right).$

Therefore, in order to have $D_{\alpha}(P^{t}\|\Pi)<\varepsilon$, we have

$\displaystyle\bar{t}_{\mathrm{mix}}^{(D_{\alpha})}(\varepsilon,P)$
$\displaystyle\leq\dfrac{1}{\gamma_{*}}\left(\ln\dfrac{\alpha}{\pi_{\mathrm{min}}}+\ln\dfrac{1}{\ln\left(1+(\alpha-1)\varepsilon\right)}\right)$
$\displaystyle\leq\dfrac{1}{\gamma_{*}}\left(\ln\dfrac{2\alpha}{(\alpha-1)\pi_{\mathrm{min}}}+\ln\dfrac{1}{\varepsilon}\right),\quad\alpha>1,$

where the last inequality comes from $\varepsilon<\frac{1}{\alpha-1}$ and
$\ln(1+x)\geq x-\frac{x^{2}}{2}\geq\frac{x}{2}$ for $x<1$.

When $0<\alpha<1$, denote $h_{t}=h_{t}(x,y):=P^{t}(x,y)/\pi(y)\geq 0$ and
$g_{t}=g_{t}(x,y):=1-h_{t}(x,y)\leq 1$ as shorthand notation. From (32), we
directly have for all $x,y\in\mathcal{X}$,

$|g_{t}(x,y)|\leq\dfrac{e^{-\gamma_{*}t}}{\pi_{\mathrm{min}}},\quad
1-\dfrac{e^{-\gamma_{*}t}}{\pi_{\mathrm{min}}}\leq h_{t}(x,y)\leq
1+\dfrac{e^{-\gamma_{*}t}}{\pi_{\mathrm{min}}}.$ (33)

Therefore, for $t>\frac{1}{\gamma_{*}}\ln\frac{2}{\pi_{\mathrm{min}}}$, we
have $\frac{1}{2}\leq h_{t}(x,y)\leq\frac{3}{2}$, in which case

$\displaystyle D_{\alpha}(P^{t}\|\Pi)$
$\displaystyle=\dfrac{1}{\alpha-1}\sum_{x}\pi(x)\sum_{y}\pi(y)\left(\left(\dfrac{P^{t}(x,y)}{\pi(y)}\right)^{\alpha}-1\right)$
$\displaystyle=\dfrac{1}{1-\alpha}\sum_{x}\pi(x)\sum_{y}\pi(y)\left(1-h_{t}^{\alpha}(x,y)\right)$
$\displaystyle=\dfrac{1}{1-\alpha}\sum_{x}\pi(x)\sum_{y}\pi(y)\left(\left(g_{t}(x,y)+h_{t}(x,y)\right)^{\alpha}-h_{t}^{\alpha}(x,y)\right)$
$\displaystyle=\dfrac{1}{1-\alpha}\sum_{x}\pi(x)\sum_{y}\pi(y)h_{t}^{\alpha}\left(\left(1+\dfrac{g_{t}}{h_{t}}\right)^{\alpha}-1\right)$
$\displaystyle\leq\dfrac{1}{1-\alpha}\sum_{x}\pi(x)\sum_{y}\pi(y)h_{t}^{\alpha}\left(\left(1+\left|\dfrac{g_{t}}{h_{t}}\right|\right)^{\alpha}-1\right)$
$\displaystyle\leq\dfrac{1}{1-\alpha}\sum_{x}\pi(x)\sum_{y}\pi(y)h_{t}^{\alpha}\left(\exp\left(\alpha\left|\dfrac{g_{t}}{h_{t}}\right|\right)-1\right)$
$\displaystyle\leq\dfrac{1}{1-\alpha}\left(\dfrac{3}{2}\right)^{\alpha}\left(\exp\left(\dfrac{2\alpha}{\pi_{\mathrm{min}}}e^{-\gamma_{*}t}\right)-1\right)$
$\displaystyle<\dfrac{2}{1-\alpha}\left(\exp\left(\dfrac{2\alpha}{\pi_{\mathrm{min}}}e^{-\gamma_{*}t}\right)-1\right),$

where the second inequality comes from $\left(1+\frac{x}{y}\right)^{y}<e^{x}$
for $x,y>0$, the third inequality comes from (33), and the last inequality
comes from $\alpha<1$. Hence, in order to have the last term above smaller
than $\varepsilon$, apart from
$t>\frac{1}{\gamma_{*}}\ln\frac{2}{\pi_{\mathrm{min}}}$, we still need

$t>\dfrac{1}{\gamma_{*}}\left(\ln\dfrac{2\alpha}{\pi_{\mathrm{min}}}+\ln\dfrac{1}{\ln\left(1+\frac{1-\alpha}{2}\varepsilon\right)}\right),$

which implies

$\displaystyle\bar{t}_{\mathrm{mix}}^{(D_{\alpha})}(\varepsilon,P)$
$\displaystyle\leq\max\left\\{\dfrac{1}{\gamma_{*}}\ln\dfrac{2}{\pi_{\mathrm{min}}},\dfrac{1}{\gamma_{*}}\left(\ln\dfrac{2\alpha}{\pi_{\mathrm{min}}}+\ln\dfrac{1}{\ln\left(1+\frac{1-\alpha}{2}\varepsilon\right)}\right)\right\\}$
$\displaystyle\leq\dfrac{1}{\gamma_{*}}\max\left\\{\ln\dfrac{2}{\pi_{\mathrm{min}}},\left(\ln\dfrac{8\alpha}{(1-\alpha)\pi_{\mathrm{min}}}+\ln\dfrac{1}{\varepsilon}\right)\right\\}$
$\displaystyle=\dfrac{1}{\gamma_{*}}\left(\ln\dfrac{8\alpha}{(1-\alpha)\pi_{\mathrm{min}}}+\ln\dfrac{1}{\varepsilon}\right),\quad
0<\alpha<1,$

where the second inequality comes from $\varepsilon<\frac{1}{1-\alpha}$ and
$\ln(1+x)\geq\frac{x}{2}$ for $x<1$, and the equality comes from
$\varepsilon<\frac{4\alpha}{1-\alpha}$.

On the other hand, we first recall the Pinsker’s inequality Proposition 3.5
which implies for $\alpha>1$,

$\dfrac{1}{2}\mathrm{TV}^{2}(P^{t},\Pi)\leq
R_{\alpha}(P^{t}\|\Pi)=\dfrac{1}{\alpha-1}\ln\left(1+(\alpha-1)D_{\alpha}(P^{t}\|\Pi)\right),$
(34)

and for $0<\alpha<1$,

$\dfrac{\alpha}{2}\mathrm{TV}^{2}(P^{t},\Pi)\leq
R_{\alpha}(P^{t}\|\Pi)=\dfrac{1}{\alpha-1}\ln\left(1+(\alpha-1)D_{\alpha}(P^{t}\|\Pi)\right).$
(35)

Then we use the statement in [28, Remark 12.6] that if $\lambda$ is an
eigenvalue of $P$ and $\lambda\neq 1$, there exists

$d^{(\mathrm{TV})}(t):=\max_{x}\dfrac{1}{2}\sum_{y}\left|P^{t}(x,y)-\pi(y)\right|\geq\dfrac{1}{2}|\lambda|^{t},$
(36)

which yields

$\mathrm{TV}(P^{t}\|\Pi)=\dfrac{1}{2}\sum_{x,y}\pi(x)\left|P^{t}(x,y)-\pi(y)\right|\geq\pi_{\mathrm{min}}d^{(\mathrm{TV})}(t)\geq\dfrac{\pi_{\mathrm{min}}}{2}|\lambda|^{t},$

since $\lambda$ is arbitrary, we have
$\mathrm{TV}(P^{t}\|\Pi)\geq\frac{\pi_{\mathrm{min}}}{2}(1-\gamma_{*})^{t}$.
Combining with the inequalities (34) and (35) above, we obtain that when
$\alpha>1$,

$\displaystyle D_{\alpha}(P^{t}\|\Pi)$
$\displaystyle\geq\dfrac{1}{\alpha-1}\left(\exp\left(\dfrac{\alpha-1}{2}\mathrm{TV}^{2}(P^{t},\Pi)\right)-1\right)$
$\displaystyle\geq\dfrac{1}{\alpha-1}\left(\exp\left(\dfrac{(\alpha-1)\pi_{\mathrm{min}}^{2}}{8}(1-\gamma_{*})^{2t}\right)-1\right),$

and when $0<\alpha<1$, similarly we have

$D_{\alpha}(P^{t}\|\Pi)\geq\dfrac{1}{\alpha-1}\left(\exp\left(\dfrac{\alpha(\alpha-1)\pi_{\mathrm{min}}^{2}}{8}(1-\gamma_{*})^{2t}\right)-1\right).$

Therefore, we can obtain

$\displaystyle\bar{t}_{\mathrm{mix}}^{(D_{\alpha})}(\varepsilon,P)$
$\displaystyle\geq\dfrac{1}{2\ln\frac{1}{1-\gamma_{*}}}\left(\ln\dfrac{\pi_{\mathrm{min}}^{2}(\alpha-1)}{8}+\ln\dfrac{1}{\ln(1+(\alpha-1)\varepsilon)}\right)$
$\displaystyle\geq\dfrac{1}{2\ln\frac{1}{1-\gamma_{*}}}\left(\ln\dfrac{\pi_{\mathrm{min}}^{2}}{8}+\ln\dfrac{1}{\varepsilon}\right),\quad\alpha>1,$

where the second inequality comes from $\ln(1+x)\leq x$. Similary for
$0<\alpha<1$, we have

$\displaystyle\bar{t}_{\mathrm{mix}}^{(D_{\alpha})}(\varepsilon,P)$
$\displaystyle\geq\dfrac{1}{2\ln\frac{1}{1-\gamma_{*}}}\left(\ln\dfrac{\pi_{\mathrm{min}}^{2}\alpha(1-\alpha)}{8}+\ln\left|\dfrac{1}{\ln(1+(\alpha-1)\varepsilon)}\right|\right)$
$\displaystyle\geq\dfrac{1}{2\ln\frac{1}{1-\gamma_{*}}}\left(\ln\dfrac{\pi_{\mathrm{min}}^{2}\alpha}{16}+\ln\dfrac{1}{\varepsilon}\right),\quad
0<\alpha<1,$

where the second inequality comes from $\ln(1+x)\geq\frac{x}{1+x}$ for $x>-1$
and $\varepsilon<\frac{1}{2(1-\alpha)}$. ∎

From the definition of $\alpha$-divergence and Rényi divergence of Markov
chains, we see that

$R_{\alpha}(P^{t}\|\Pi)<\varepsilon\iff
D_{\alpha}(P^{t}\|\Pi)<\dfrac{1}{\alpha-1}\left(e^{(\alpha-1)\varepsilon}-1\right),$

and hence the $\pi$-weighted $\alpha$-divergence mixing time and the Rényi
divergence mixing time are related via

$\bar{t}_{\mathrm{mix}}^{(R_{\alpha})}(\varepsilon,P)=\bar{t}_{\mathrm{mix}}^{(D_{\alpha})}\left(\dfrac{1}{\alpha-1}\left(e^{(\alpha-1)\varepsilon}-1\right),P\right).$
(37)

Thus, to give spectral bounds on
$\bar{t}_{\mathrm{mix}}^{(R_{\alpha})}(\varepsilon,P)$, using (37) yields the
following corollary of Theorem 4.3:

######  Corollary 4.1.

Let $P\in\mathcal{L}(\pi)$ be an irreducible, aperiodic, reversible transition
matrix and we denote by $\pi_{\mathrm{min}}:=\min_{x}\pi(x)>0$. For
$\alpha\in(0,1)\cup(1,+\infty)$, if
$\varepsilon<\min\left\\{\frac{1}{2|\alpha-1|},\frac{4\alpha}{|\alpha-1|}\right\\}$,
we have

$\displaystyle\bar{t}_{\mathrm{mix}}^{(R_{\alpha})}(\varepsilon,P)$
$\displaystyle\leq\begin{cases}\dfrac{1}{\gamma_{*}}\left(\ln\dfrac{2\alpha}{\pi_{\mathrm{min}}}+\ln\dfrac{1}{e^{(\alpha-1)\varepsilon}-1}\right),&\quad\textrm{if
}\,\alpha>1,\\\
\dfrac{1}{\gamma_{*}}\left(\ln\dfrac{8\alpha}{\pi_{\mathrm{min}}}+\ln\dfrac{1}{1-e^{(\alpha-1)\varepsilon}}\right),&\quad\textrm{if
}\,0<\alpha<1,\end{cases}$

and

$\displaystyle\bar{t}_{\mathrm{mix}}^{(R_{\alpha})}(\varepsilon,P)$
$\displaystyle\geq\begin{cases}\dfrac{1}{2\ln\frac{1}{1-\gamma_{*}}}\left(\ln\dfrac{(\alpha-1)\pi_{\mathrm{min}}^{2}}{8}+\ln\dfrac{1}{e^{(\alpha-1)\varepsilon}-1}\right),&\quad\textrm{if
}\,\alpha>1,\\\
\dfrac{1}{2\ln\frac{1}{1-\gamma_{*}}}\left(\ln\dfrac{\pi_{\mathrm{min}}^{2}\alpha(1-\alpha)}{16}+\ln\dfrac{1}{1-e^{(\alpha-1)\varepsilon}}\right),&\quad\textrm{if
}\,0<\alpha<1,\end{cases}$

where $\gamma_{*}$ is the absolute spectral gap of $P$.

######  Remark 4.1.

To study the order of $\gamma_{*}$ in the upper and lower bound of
$\bar{t}_{\mathrm{mix}}^{(D_{\alpha})}(\varepsilon,P)$ in Theorem 4.3 and
$\bar{t}_{\mathrm{mix}}^{(R_{\alpha})}(\varepsilon,P)$ in Corollary 4.1, we
can see that if $\gamma_{*}$ is close to $0$, we have

$\lim_{\gamma_{*}\rightarrow
0^{+}}\dfrac{1}{\gamma_{*}}\bigg{/}\dfrac{1}{\ln\frac{1}{1-\gamma_{*}}}=1,$

which implies the upper bound and lower bound are approximately the same order
with respect to $\gamma_{*}$ in this situation. Indeed, in many statistical
physics models or Markov chains of interest, $\gamma_{*}=\mathcal{O}(1/N^{a})$
for some $a>0$ and $N$ being a problem-dependent parameter which is large. One
example is random walk on $N$-dimensional hypercube which will be explained in
Example 4.1.

Next, we recall the classical worst-case mixing times based upon
$\alpha$-divergence, Rényi divergence and total variation distance to be
respectively, for $\varepsilon>0$,

$\displaystyle t_{\mathrm{mix}}^{(\mathrm{D_{\alpha}})}(\varepsilon,P)$
$\displaystyle:=\inf\left\\{t>0:d^{(D_{\alpha})}(t)<\varepsilon\right\\},$
$\displaystyle t_{\mathrm{mix}}^{(\mathrm{R_{\alpha}})}(\varepsilon,P)$
$\displaystyle:=\inf\left\\{t>0:d^{(R_{\alpha})}(t)<\varepsilon\right\\},$
$\displaystyle t_{\mathrm{mix}}^{(\mathrm{TV})}(\varepsilon,P)$
$\displaystyle:=\inf\left\\{t>0:d^{(\mathrm{TV})}(t)<\varepsilon\right\\},$
(38)

where the worst-case divergences are defined as, for $t\in\mathbb{N}$,

$\displaystyle d^{(D_{\alpha})}(t)$
$\displaystyle:=\max_{x\in\mathcal{X}}\widetilde{D}_{\alpha}(P^{t}(x,\cdot)\|\pi)=\max_{x\in\mathcal{X}}\dfrac{1}{\alpha-1}\left(\sum_{y\in\mathcal{X}}\pi(y)\left(\dfrac{P^{t}(x,y)}{\pi(y)}\right)^{\alpha}-1\right),$
$\displaystyle d^{(R_{\alpha})}(t)$
$\displaystyle:=\max_{x\in\mathcal{X}}\widetilde{R}_{\alpha}(P^{t}(x,\cdot)\|\pi)=\max_{x\in\mathcal{X}}\dfrac{1}{\alpha-1}\ln\left(\sum_{y\in\mathcal{X}}\pi(y)\left(\dfrac{P^{t}(x,y)}{\pi(y)}\right)^{\alpha}\right),$
$\displaystyle d^{(\mathrm{TV})}(t)$
$\displaystyle:=\max_{x\in\mathcal{X}}\left\|P^{t}(x,\cdot)-\pi\right\|_{\mathrm{TV}}=\max_{x\in\mathcal{X}}\dfrac{1}{2}\sum_{y\in\mathcal{X}}\left|P^{t}(x,y)-\pi(y)\right|.$

We prove the following relationships between these $\pi$-weighted mixing times
and and their worst-case mixing times counterpart, and in particular implies
that the $\pi$-weighted mixing times and worst-case mixing times are of the
same order under some reasonable assumptions on the absolute spectral gap
$\gamma_{*}$:

######  Theorem 4.4.

Let $P\in\mathcal{L}(\pi)$ be an irreducible, aperiodic, $\pi$-reversible
transition matrix, and we denote $\pi_{\mathrm{min}}:=\min_{x}\pi(x)>0$, then
we have the following relationships:

  1. (i).

$t_{\mathrm{mix}}^{(\mathrm{TV})}\left(\varepsilon,P\right)$ and
$\bar{t}_{\mathrm{mix}}^{(\mathrm{TV})}(\varepsilon,P)$: if
$\varepsilon<\frac{\pi_{\mathrm{min}}^{3}}{4}$, then

$\dfrac{1-\gamma_{*}}{2}t_{\mathrm{mix}}^{(\mathrm{TV})}\left(\varepsilon,P\right)\leq\bar{t}_{\mathrm{mix}}^{(\mathrm{TV})}(\varepsilon,P)\leq
t_{\mathrm{mix}}^{(\mathrm{TV})}(\varepsilon,P).$

  2. (ii).

$t_{\mathrm{mix}}^{(D_{\alpha})}\left(\varepsilon,P\right)$ and
$\bar{t}_{\mathrm{mix}}^{(D_{\alpha})}(\varepsilon,P)$: if
$\varepsilon<\varepsilon_{0}:=\min\left\\{\frac{1}{2|\alpha-1|},\frac{4\alpha}{|\alpha-1|},\frac{|\alpha-1|\pi_{\mathrm{min}}^{6}}{128\alpha},\frac{\alpha|\alpha-1|\pi_{\mathrm{min}}^{6}}{2048}\right\\}$,
then

$\dfrac{1-\gamma_{*}}{4}t_{\mathrm{mix}}^{(D_{\alpha})}(\varepsilon,P)\leq\bar{t}_{\mathrm{mix}}^{(D_{\alpha})}(\varepsilon,P)\leq
t_{\mathrm{mix}}^{(D_{\alpha})}(\varepsilon,P),\quad\alpha\in(0,1)\cup(1,\infty).$

  3. (iii).

$t_{\mathrm{mix}}^{(R_{\alpha})}\left(\varepsilon,P\right)$ and
$\bar{t}_{\mathrm{mix}}^{(R_{\alpha})}(\varepsilon,P)$: if
$\varepsilon<\frac{1}{\alpha-1}\ln(1+(\alpha-1)\varepsilon_{0})$ with
$\varepsilon_{0}$ defined in item ((ii).), then

$\dfrac{1-\gamma_{*}}{4}t_{\mathrm{mix}}^{(R_{\alpha})}(\varepsilon,P)\leq\bar{t}_{\mathrm{mix}}^{(R_{\alpha})}(\varepsilon,P)\leq
t_{\mathrm{mix}}^{(R_{\alpha})}(\varepsilon,P),\quad\alpha\in(0,1)\cup(1,\infty).$

###### Proof.

Item (i).: Recalling the definition of $\mathrm{TV}(P^{t},\Pi)$ in Definition
2.5, we have

$\displaystyle\mathrm{TV}(P^{t},\Pi)$
$\displaystyle=\dfrac{1}{2}\sum_{x}\pi(x)\sum_{y}\left|P^{t}(x,y)-\pi(y)\right|$
$\displaystyle\leq\sum_{x}\pi(x)\left(\max_{x}\dfrac{1}{2}\sum_{y}\left|P^{t}(x,y)-\pi(y)\right|\right)$
$\displaystyle=d^{(\mathrm{TV})}(t),$

and

$\displaystyle\mathrm{TV}(P^{t},\Pi)$
$\displaystyle=\dfrac{1}{2}\sum_{x}\pi(x)\sum_{y}\left|P^{t}(x,y)-\pi(y)\right|$
$\displaystyle\geq\pi_{\mathrm{min}}d^{(\mathrm{TV})}(t),$

therefore we can obtain

$t_{\mathrm{mix}}^{(\mathrm{TV})}\left(\dfrac{\varepsilon}{\pi_{\mathrm{min}}},P\right)\leq\bar{t}_{\mathrm{mix}}^{(\mathrm{TV})}(\varepsilon,P)\leq
t_{\mathrm{mix}}^{(\mathrm{TV})}(\varepsilon,P).$ (39)

According to [28, Theorem 12.4, 12.5], there exists

$\left(\dfrac{1}{\gamma_{*}}-1\right)\ln\dfrac{1}{2\varepsilon}\leq
t_{\mathrm{mix}}^{(\mathrm{TV})}(\varepsilon,P)\leq\dfrac{1}{\gamma_{*}}\ln\dfrac{1}{\varepsilon\pi_{\mathrm{min}}},$
(40)

which implies

$\displaystyle
t_{\mathrm{mix}}^{(\mathrm{TV})}\left(\dfrac{\varepsilon}{\pi_{\mathrm{min}}},P\right)\geq\left(\dfrac{1}{\gamma_{*}}-1\right)\ln\dfrac{\pi_{\mathrm{min}}}{2\varepsilon}$
$\displaystyle\geq(1-\gamma_{*})\left(1+\dfrac{\ln\frac{\pi_{\mathrm{min}}^{2}}{2}}{\ln\frac{1}{\varepsilon}-\ln\pi_{\mathrm{min}}}\right)t_{\mathrm{mix}}^{(\mathrm{TV})}(\varepsilon,P)$
$\displaystyle\geq\dfrac{1-\gamma_{*}}{2}t_{\mathrm{mix}}^{(\mathrm{TV})}(\varepsilon,P),$

where the last inequality is from
$\varepsilon<\dfrac{\pi_{\mathrm{min}}^{3}}{4}$. Plugging into (39), we have

$\dfrac{1-\gamma_{*}}{2}t_{\mathrm{mix}}^{(\mathrm{TV})}\left(\varepsilon,P\right)\leq\bar{t}_{\mathrm{mix}}^{(\mathrm{TV})}(\varepsilon,P)\leq
t_{\mathrm{mix}}^{(\mathrm{TV})}(\varepsilon,P).$

Item (ii).: Similar to analysis in item (i)., we have

$t_{\mathrm{mix}}^{(D_{\alpha})}\left(\dfrac{\varepsilon}{\pi_{\mathrm{min}}},P\right)\leq\bar{t}_{\mathrm{mix}}^{(D_{\alpha})}(\varepsilon,P)\leq
t_{\mathrm{mix}}^{(D_{\alpha})}(\varepsilon,P).$

Therefore, recalling Theorem 4.3, for $\alpha>1$ we have

$\displaystyle\bar{t}_{\mathrm{mix}}^{(D_{\alpha})}(\varepsilon,P)\leq
t_{\mathrm{mix}}^{(D_{\alpha})}(\varepsilon,P)$
$\displaystyle\leq\bar{t}_{\mathrm{mix}}^{(D_{\alpha})}(\pi_{\mathrm{min}}\varepsilon,P)\leq\dfrac{1}{\gamma_{*}}\left(\ln\dfrac{2\alpha}{(\alpha-1)\pi_{\mathrm{min}}^{2}}+\ln\dfrac{1}{\varepsilon}\right)$
$\displaystyle\leq\bar{t}_{\mathrm{mix}}^{(D_{\alpha})}(\varepsilon,P)\dfrac{2\ln\frac{1}{1-\gamma_{*}}}{\gamma_{*}}\dfrac{\ln\frac{1}{\varepsilon}+\ln\frac{2\alpha}{(\alpha-1)\pi_{\mathrm{min}}^{2}}}{\ln\frac{1}{\varepsilon}+\ln\frac{\pi_{\mathrm{min}}^{2}}{8}}$
$\displaystyle\leq\bar{t}_{\mathrm{mix}}^{(D_{\alpha})}(\varepsilon,P)\cdot\dfrac{4}{1-\gamma_{*}},\quad\alpha>1,$

where the last inequality comes from
$\ln\frac{1}{1-\gamma_{*}}\leq\frac{\gamma_{*}}{1-\gamma_{*}}$ and
$\varepsilon<\frac{(\alpha-1)\pi_{\mathrm{min}}^{6}}{128\alpha}$. For
$0<\alpha<1$, we also have

$\displaystyle\bar{t}_{\mathrm{mix}}^{(D_{\alpha})}(\varepsilon,P)\leq
t_{\mathrm{mix}}^{(D_{\alpha})}(\varepsilon,P)$
$\displaystyle\leq\bar{t}_{\mathrm{mix}}^{(D_{\alpha})}(\pi_{\mathrm{min}}\varepsilon,P)\leq\dfrac{1}{\gamma_{*}}\left(\ln\dfrac{8\alpha}{(1-\alpha)\pi_{\mathrm{min}}^{2}}+\ln\dfrac{1}{\varepsilon}\right)$
$\displaystyle\leq\bar{t}_{\mathrm{mix}}^{(D_{\alpha})}(\varepsilon,P)\dfrac{2\ln\frac{1}{1-\gamma_{*}}}{\gamma_{*}}\dfrac{\ln\frac{1}{\varepsilon}+\ln\frac{8\alpha}{(1-\alpha)\pi_{\mathrm{min}}^{2}}}{\ln\frac{1}{\varepsilon}+\ln\frac{\alpha\pi_{\mathrm{min}}^{2}}{16}}$
$\displaystyle\leq\bar{t}_{\mathrm{mix}}^{(D_{\alpha})}(\varepsilon,P)\cdot\dfrac{4}{1-\gamma_{*}},\quad
0<\alpha<1,$

where in the last inequality we have used
$\varepsilon<\frac{\alpha(1-\alpha)\pi_{\mathrm{min}}^{6}}{2048}$.

Item (iii).: Similar to (37), since the mapping
$t\mapsto\frac{1}{\alpha-1}\ln(1+(\alpha-1)t)$ is increasing, we have

$d^{(D_{\alpha})}(t)<\varepsilon\iff
d^{(R_{\alpha})}(t)<\dfrac{1}{\alpha-1}\left(e^{(\alpha-1)\varepsilon}-1\right),$

which implies

$t_{\mathrm{mix}}^{(R_{\alpha})}(\varepsilon,P)=t_{\mathrm{mix}}^{(D_{\alpha})}\left(\dfrac{1}{\alpha-1}\left(e^{(\alpha-1)\varepsilon}-1\right),P\right).$

Therefore, plugging into item (ii). we get the result. ∎

Theorem 4.4 illustrates that the mixing time under total variation distance
and worst case distance are of the same order. As an illustration for Theorem
4.3 and 4.4, we consider the following lazy random walk on high-dimensional
hypercube.

######  Example 4.1 (Random walk on the $N$-dimensional hypercube).

Consider $\mathcal{X}=\\{-1,1\\}^{N}$ where $N>1$. In this state space, at
each step the chain uniformly select a coordinate from $N$ coordinates and
update the chosen coordinate to $-1$ and $1$ with probability $\frac{1}{2}$
respectively. For $\mathbb{x},\mathbb{y}\in\mathcal{X}$, we denote
$\mathbb{x}=(x_{1},x_{2},...,x_{N})$ and $\mathbb{y}=(y_{1},y_{2},...,y_{N})$,
and the transition matrix $P$ of the random walk on $\mathcal{X}$ can be
written as

$P(\mathbb{x},\mathbb{y})=\sum_{i=1}^{N}\dfrac{1}{N}Q(x_{i},y_{i})\mathbf{1}_{\\{x_{j}=y_{j},j\neq
i\\}}(\mathbb{x},\mathbb{y}),$ (41)

where $Q$ is the transition matrix defined on $\mathcal{X}_{0}=\\{-1,1\\}$
such that $Q(x,y)=\frac{1}{2}$ for $x,y\in\mathcal{X}_{0}$, and therefore the
chain under $P$ is lazy. According to [28, Example 12.16], there exists
$\gamma_{*}=\frac{1}{N}$ and $\pi_{\mathrm{min}}=2^{-N}$. Plugging into
Theorem 4.3, if
$\varepsilon<\min\left\\{\frac{1}{2|\alpha-1|},\frac{4\alpha}{|\alpha-1|}\right\\}$,
we have for $\alpha>1$,

$\displaystyle\bar{t}_{\mathrm{mix}}^{(D_{\alpha})}(\varepsilon,P)$
$\displaystyle\leq N\left(N\ln
2+\ln\dfrac{2\alpha}{(\alpha-1)}+\ln\dfrac{1}{\varepsilon}\right),\quad\alpha>1,$
$\displaystyle\bar{t}_{\mathrm{mix}}^{(D_{\alpha})}(\varepsilon,P)$
$\displaystyle\geq\dfrac{N-1}{2}\left(\ln\dfrac{1}{\varepsilon}-(2N+3)\ln
2\right),\quad\alpha>1,$

where we use $\ln\frac{N}{N-1}\leq\frac{1}{N-1}$ in the second inequality. For
$\alpha<1$, we similarly have

$\displaystyle\bar{t}_{\mathrm{mix}}^{(D_{\alpha})}(\varepsilon,P)$
$\displaystyle\leq N\left(N\ln
2+\ln\dfrac{8\alpha}{(1-\alpha)}+\ln\dfrac{1}{\varepsilon}\right),\quad
0<\alpha<1,$
$\displaystyle\bar{t}_{\mathrm{mix}}^{(D_{\alpha})}(\varepsilon,P)$
$\displaystyle\geq\dfrac{N-1}{2}\left(\ln\alpha+\ln\dfrac{1}{\varepsilon}-(2N+4)\ln
2\right),\quad 0<\alpha<1,$

Moreover, plugging $\gamma_{*}=\frac{1}{N}$ and $\pi_{\mathrm{min}}=2^{-N}$
into Theorem 4.4 and (40), when $\varepsilon<2^{-(3N+2)}$, we have

$\dfrac{(N-1)^{2}}{2N}\ln\dfrac{1}{2\varepsilon}\leq\bar{t}_{\mathrm{mix}}^{(\mathrm{TV})}(\varepsilon,P)\leq
N\left(N\ln 2+\ln\dfrac{1}{\varepsilon}\right).$

###  4.3 Cesàro mixing time and ergodicity coefficients

In Section 4.2, we have investigated various average or worst-case mixing
times of Markov chains with irreducible, aperiodic and $\pi$-reversible
stochastic matrices. However, the convergence results similar to Theorem 4.3
and 4.4 may not hold for a periodic transition matrix $P$, as $P$ can have an
eigenvalue of $-1$, which implies $\gamma_{*}=0$. This motivates us to study
other notions of mixing times that are suitable for periodic chains.

One such alternative is to consider the so-called Cesáro mixing. Following
similar notations in Section 4.2, for irreducible transition matrix
$P\in\mathcal{L}$ that is $\pi$-stationary and $\varepsilon>0$, we define
several Cesàro mixing times that are based upon information divergences as
follows:

$\displaystyle\bar{t}_{\mathrm{Ces}}^{(\mathrm{TV})}(\varepsilon,P)$
$\displaystyle:=\inf\left\\{t>0:\mathrm{TV}\left(\dfrac{1}{t}\sum_{s=1}^{t}P^{s},\Pi\right)<\varepsilon\right\\},$
(42)
$\displaystyle\bar{t}_{\mathrm{Ces}}^{(\mathrm{D_{\alpha}})}(\varepsilon,P)$
$\displaystyle:=\inf\left\\{t>0:D_{\alpha}\left(\dfrac{1}{t}\sum_{s=1}^{t}P^{s}\bigg{\|}\Pi\right)<\varepsilon\right\\},$
$\displaystyle\bar{t}_{\mathrm{Ces}}^{(\mathrm{R_{\alpha}})}(\varepsilon,P)$
$\displaystyle:=\inf\left\\{t>0:R_{\alpha}\left(\dfrac{1}{t}\sum_{s=1}^{t}P^{s}\bigg{\|}\Pi\right)<\varepsilon\right\\}.$

Next, we offer inequalities between Cesàro mixing time and related mixing
times as introduced earlier. These for instance can be used for upper bounding
the Cesáro mixing time. Note that the following results in Theorem 4.5 hold
without assuming $\pi$-reversibility or aperiodicity of $P$.

######  Theorem 4.5.

For irreducible $\pi$-stationary $P\in\mathcal{L}$ on $\mathcal{X}$ and
$\varepsilon>0$, we have

$\bar{t}_{\mathrm{Ces}}^{(\mathrm{TV})}(\varepsilon,P)\leq\dfrac{1}{\varepsilon(1-2\varepsilon)}t_{\mathrm{mix}}^{(\mathrm{TV})}(\varepsilon,P),$
(43)

where $\bar{t}_{\mathrm{Ces}}^{(\mathrm{TV})}(\varepsilon,P)$ and
$t_{\mathrm{mix}}^{(\mathrm{TV})}(\varepsilon,P)$ are introduced respectively
in (42) and (38).

Furthermore, we assume that there exists $0<\theta<1$ such that the ergodicity
coefficient $\eta^{(\mathrm{TV})}(P)\leq\theta$ (i.e. $P$ is scrambling). If
$\alpha\in(0,1)\cup(1,+\infty)$ and $D_{\alpha}(P\|\Pi)<\infty$, we have

$\displaystyle\bar{t}_{\mathrm{Ces}}^{(\mathrm{TV})}(\varepsilon,P)$
$\displaystyle\leq\dfrac{1}{\varepsilon}\cdot\bar{t}_{\mathrm{mix}}^{(\mathrm{TV})}(\varepsilon,P)+\dfrac{1}{1-\theta},$
(44) $\displaystyle\bar{t}_{\mathrm{Ces}}^{(D_{\alpha})}(\varepsilon,P)$
$\displaystyle\leq\dfrac{D_{\alpha}(P\|\Pi)}{\varepsilon}\cdot\bar{t}_{\mathrm{mix}}^{(D_{\alpha})}(\varepsilon,P)+\dfrac{1}{1-\theta},$
(45) $\displaystyle\bar{t}_{\mathrm{Ces}}^{(R_{\alpha})}(\varepsilon,P)$
$\displaystyle\leq\frac{1+\varepsilon}{\varepsilon}D_{\alpha}(P\|\Pi)\cdot\bar{t}_{\mathrm{mix}}^{(R_{\alpha})}\left(\varepsilon,P\right)+\dfrac{1}{1-\theta},$
(46)

where we recall that
$\bar{t}_{\mathrm{mix}}^{(\mathrm{TV})}(\varepsilon,P),\bar{t}_{\mathrm{mix}}^{(D_{\alpha})}(\varepsilon,P),\bar{t}_{\mathrm{mix}}^{(R_{\alpha})}(\varepsilon,P)$
are respectively defined in (31), (29) and (30).

###### Proof.

Denote $t=t_{\mathrm{mix}}^{(\mathrm{TV})}(\varepsilon,P)$, and hence
$d^{(\mathrm{TV})}(t)=\max_{x\in\mathcal{X}}\frac{1}{2}\sum_{y\in\mathcal{X}}\left|P^{t}(x,y)-\pi(y)\right|<\varepsilon$.
For any positive integer $l>0$, we have

$\displaystyle\mathrm{TV}\left(\dfrac{1}{lt}\sum_{s=1}^{lt}P^{s},\Pi\right)$
$\displaystyle=\dfrac{1}{2}\sum_{x,y}\pi(x)\left|\dfrac{1}{lt}\sum_{s=1}^{lt}P^{s}(x,y)-\pi(y)\right|$
$\displaystyle\leq\dfrac{1}{lt}\sum_{x}\pi(x)\sum_{s=1}^{lt}\left\|P^{s}(x,\cdot)-\pi(\cdot)\right\|_{\mathrm{TV}}$
$\displaystyle\leq\dfrac{1}{lt}\sum_{s=1}^{lt}\max_{x}\left\|P^{s}(x,\cdot)-\pi(\cdot)\right\|_{\mathrm{TV}}$
$\displaystyle=\dfrac{1}{lt}\sum_{s=1}^{lt}d^{(\mathrm{TV})}(s).$

According to [28, Lemma 4.10,4.11,Ex.4.2], $d(t)$ is non-increasing, and there
exists

$d^{(\mathrm{TV})}(cs)\leq(2d^{(\mathrm{TV})}(s))^{c},\quad\text{c is any
positive integer},$

hence we have

$\displaystyle\mathrm{TV}\left(\dfrac{1}{lt}\sum_{s=1}^{lt}P^{s},\Pi\right)$
$\displaystyle\leq\dfrac{1}{lt}\left(t+t\varepsilon+t(2\varepsilon)^{2}+...+t(2\varepsilon)^{l-1}\right)$
$\displaystyle\leq\dfrac{1}{l}\left(\dfrac{1}{1-2\varepsilon}-\varepsilon\right),$

and in order for the right hand side above smaller than $\varepsilon$, it
suffices to have

$l\geq\dfrac{1}{\varepsilon(1-2\varepsilon)}\geq\left\lceil\dfrac{1-\varepsilon+2\varepsilon^{2}}{\varepsilon-2\varepsilon^{2}}\right\rceil.$

Therefore,

$\bar{t}_{\mathrm{Ces}}^{(\mathrm{TV})}(\varepsilon,P)\leq\dfrac{t}{\varepsilon(1-2\varepsilon)}=\dfrac{1}{\varepsilon(1-2\varepsilon)}t_{\mathrm{mix}}^{(\mathrm{TV})}(\varepsilon,P).$

To prove (44) and (45), by convexity of $D_{\alpha}(\cdot\|\cdot)$ from
Proposition 3.2, for any integer $T>0$, it is easy to verify

$\displaystyle\mathrm{TV}\left(\dfrac{1}{T}\sum_{s=1}^{T}P^{s},\Pi\right)$
$\displaystyle\leq\dfrac{1}{T}\sum_{s=1}^{T}\mathrm{TV}(P^{s},\Pi),$
$\displaystyle
D_{\alpha}\left(\dfrac{1}{T}\sum_{s=1}^{T}P^{s}\bigg{\|}\Pi\right)$
$\displaystyle\leq\dfrac{1}{T}\sum_{s=1}^{T}D_{\alpha}(P^{s}\|\Pi).$

Denote $t=\bar{t}_{\mathrm{mix}}^{(\mathrm{TV})}(\varepsilon,P)$, which gives
$\mathrm{TV}(P^{t}\|\Pi)\leq\varepsilon$. According to Proposition 3.9 item
(i)., we thus have, for $s>t$,

$\displaystyle\mathrm{TV}(P^{s},\Pi)\leq\theta^{s-t}\varepsilon,$

which yields

$\displaystyle\mathrm{TV}\left(\dfrac{1}{T}\sum_{s=1}^{T}P^{s},\Pi\right)$
$\displaystyle\leq\dfrac{1}{T}\left(\sum_{s=1}^{t}\mathrm{TV}(P^{s},\Pi)+\sum_{s=t+1}^{T}\mathrm{TV}(P^{s},\Pi)\right)$
$\displaystyle\leq\frac{1}{T}\left(t+\frac{\varepsilon\theta}{1-\theta}\right).$

We set the right hand side above to be smaller than $\varepsilon$. As such we
require that

$T\geq\frac{t}{\varepsilon}+\frac{1}{1-\theta}\geq\left\lceil\frac{t}{\varepsilon}+\frac{\theta}{1-\theta}\right\rceil,$

and therefore (44) is obtained. The proof for (45) is similar by recalling
that $\eta^{(D_{\alpha})}(P)\leq\eta^{(\mathrm{TV})}(P)\leq\theta$ as stated
in Proposition 3.9 item (i).. For (46), analogous to the proof of (37) we see
that

$\bar{t}_{\mathrm{Ces}}^{(R_{\alpha})}(\varepsilon,P)=\bar{t}_{\mathrm{Ces}}^{(D_{\alpha})}\left(\dfrac{1}{\alpha-1}\left(e^{(\alpha-1)\varepsilon}-1\right),P\right),$

then by (45) and (37) we have

$\displaystyle\bar{t}_{\mathrm{Ces}}^{(R_{\alpha})}(\varepsilon,P)$
$\displaystyle=\bar{t}_{\mathrm{Ces}}^{(D_{\alpha})}\left(\dfrac{1}{\alpha-1}\left(e^{(\alpha-1)\varepsilon}-1\right),P\right)$
$\displaystyle\leq\dfrac{\alpha-1}{e^{(\alpha-1)\varepsilon}-1}D_{\alpha}(P\|\Pi)\bar{t}_{\mathrm{mix}}^{(D_{\alpha})}\left(\dfrac{1}{\alpha-1}\left(e^{(\alpha-1)\varepsilon}-1\right),P\right)+\dfrac{1}{1-\theta}$
$\displaystyle=\dfrac{\alpha-1}{e^{(\alpha-1)\varepsilon}-1}D_{\alpha}(P\|\Pi)\bar{t}_{\mathrm{mix}}^{(R_{\alpha})}\left(\varepsilon,P\right)+\dfrac{1}{1-\theta}$
$\displaystyle\leq\frac{1+\varepsilon}{\varepsilon}D_{\alpha}(P\|\Pi)\bar{t}_{\mathrm{mix}}^{(R_{\alpha})}\left(\varepsilon,P\right)+\dfrac{1}{1-\theta},$

where the last inequality comes from
$e^{(\alpha-1)\varepsilon}\geq(\alpha-1)\varepsilon+1$ for $\alpha>1$ and
$e^{(1-\alpha)\varepsilon}\geq(1-\alpha)\varepsilon+1$ for $0<\alpha<1$. ∎

In (44), (45) and (46), we require that $P$ is a scrambling matrix so that
$\eta^{(\mathrm{TV})}(P)<1$ (see Proposition 3.9 item (viii). and Remark 3.2),
while in many cases this condition is hard to guarantee. An alternative
consideration is, if we can show that $\eta^{(\mathrm{TV})}(P^{t})<1$ for some
$t>0$, then by submultiplicativity of $\eta^{(\mathrm{TV})}(\cdot)$ from
Proposition 3.9 item (v)., it is a direct corollary that for all $s\geq t$,
$\eta^{(\mathrm{TV})}(P^{s})\leq\eta^{(\mathrm{TV})}(P^{t})<1$, and we can
still obtain similar bound for Cesàro mixing time. In the following example,
we will show that in general Metropolis-Hastings algorithms under low
temperature, the first time that the ergodicty/Dobrushin coefficient
$\eta^{(\mathrm{TV})}(P^{t})<\varepsilon$ for any $\varepsilon>0$ has an
exponential dependence on the exit height.

######  Example 4.2 (Ergodicity/Dobrushin coefficient of Metropolis-Hastings
chain).

Let $Q$ be a reversible transition matrix with respect to probability measure
$\mu$ on finite state space $\mathcal{X}$. Let
$U:\mathcal{X}\rightarrow\mathbb{R}$ be the target function, $\beta$ be the
inverse temperature, and we use the Metropolis-Hastings algorithm to sample
from the Gibbs distribution $\pi_{\beta}(x)\propto\mu(x)e^{-\beta U(x)}$. The
transition matrix of the chain can be written as

$P_{\beta}(x,y)=\begin{cases}Q(x,y)\exp\left(-\beta(U(y)-U(x))_{+}\right),\quad&x\neq
y,\\\ 1-\sum_{z\neq x}P_{\beta}(x,z),\quad&x=y.\end{cases}$

Suppose the chain generated by $P_{\beta}$ is $\\{X_{n}\\}_{n\geq 0}$.
Following [23] and [29], for $A\subseteq\mathcal{X}$, we define the first
hitting time of the set $A$ to be $\tau_{A}:=\inf\\{n:X_{n}\in A\\}$, and the
exit height $H(A)$ as

$\displaystyle h(x,A)$
$\displaystyle:=\lim_{\beta\rightarrow\infty}\dfrac{1}{\beta}\ln\left(\mathbb{E}_{x}[\tau_{A^{c}}]\right),$
$\displaystyle H(A)$ $\displaystyle:=\max_{x\in A}h(x,A).$

Note that there is a dependency on the inverse temperature $\beta$ of
$\mathbb{E}_{x}[\tau_{A^{c}}]$ via the underlying Metropolis-Hastings chain.
Next, we define the product chain

$P_{\beta}^{\otimes
2}\left((x_{1},x_{2}),(y_{1},y_{2})\right):=P_{\beta}(x_{1},y_{1})P_{\beta}(x_{2},y_{2}),\quad(x_{1},x_{2}),(y_{1},y_{2})\in\mathcal{X}^{2},$

and the constant

$H_{3}:=H(\mathcal{X}^{2}\setminus\Delta),\quad\Delta:=\\{(x,x)\in\mathcal{X}^{2}:x\in\mathcal{X}\\},$

where $H_{3}$ is an exit height with respect to the product chain
$P_{\beta}^{\otimes 2}$.

For any $0<\varepsilon<1$, we define the first time that
$\eta^{(\mathrm{TV})}(P_{\beta}^{t})<\varepsilon$ as

$\displaystyle t_{\mathrm{Dob}}^{(\mathrm{TV})}(\varepsilon,P_{\beta})$
$\displaystyle:=\inf\\{t\geq
0:\eta^{(\mathrm{TV})}(P_{\beta}^{t})<\varepsilon\\},$
$\displaystyle\widetilde{t}_{\mathrm{Dob}}^{(\mathrm{TV})}(\varepsilon,P_{\beta})$
$\displaystyle:=\inf\\{t\geq
0:\widetilde{\eta}^{(\mathrm{TV})}(P_{\beta}^{t})<\varepsilon\\},$

then according to [29, Proposition 2.1], there exists

$\lim_{\beta\rightarrow\infty}\dfrac{1}{\beta}\ln\left(\widetilde{t}_{\mathrm{Dob}}^{(\mathrm{TV})}(\varepsilon,P_{\beta})\right)=H_{3}.$

Since
$\eta^{(\mathrm{TV})}(P_{\beta}^{t})=\widetilde{\eta}^{(\mathrm{TV})}(P_{\beta}^{t})$
by Proposition 3.9 item (ii)., we then have

$\lim_{\beta\rightarrow\infty}\dfrac{1}{\beta}\ln\left(t_{\mathrm{Dob}}^{(\mathrm{TV})}(\varepsilon,P_{\beta})\right)=H_{3}.$

## Acknowledgements

Youjia Wang gratefully acknowledges the financial support from National
University of Singapore via the Presidential Graduate Fellowship. Michael Choi
acknowledges the financial support of the project “MAPLE: Mechanistic
Accelerated Prediction of Protein Secondary Structure via LangEvin Monte
Carlo” with grant number 22-5715-P0001 under the National University of
Singapore Faculty of Science Ministry of Education Tier 1 grant Data for
Science and Science for Data collaborative scheme, as well as the startup
funding of the National University of Singapore.

## References

  * [1] David J Aldous  “Some inequalities for reversible Markov chains”  In _Journal of the London Mathematical Society_ 2.3 Oxford University Press, 1982, pp. 564–576
  * [2] Robert M Anderson, Haosui Duanmu and Aaron Smith  “Mixing times and hitting times for general Markov processes”  In _Israel Journal of Mathematics_ Springer, 2023, pp. 1–76
  * [3] Riddhipratim Basu, Jonathan Hermon and Yuval Peres  “Characterization of cutoff for reversible Markov chains”  In _Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms_ , 2014, pp. 1774–1791  SIAM
  * [4] Louis J Billera and Persi Diaconis  “A geometric interpretation of the Metropolis-Hastings algorithm”  In _Statistical Science_ JSTOR, 2001, pp. 335–339
  * [5] Olivier Catoni  “Simulated annealing algorithms and Markov chains with rare transitions”  In _Séminaire de probabilités XXXIII_ Springer, 2006, pp. 69–119
  * [6] Joel E Cohen et al.  “Relative entropy under mappings by stochastic matrices”  In _Linear algebra and its applications_ 179 Elsevier, 1993, pp. 211–235
  * [7] T.M. Cover and J.A. Thomas  “Elements of Information Theory”  Wiley, 2012  URL: https://books.google.com.sg/books?id=VWq5GG6ycxMC
  * [8] Simon Griffiths, Ross Kang, Roberto Oliveira and Viresh Patel  “Tight inequalities among set hitting times in Markov chains”  In _Proceedings of the American Mathematical Society_ 142.9, 2014, pp. 3285–3298
  * [9] Jonathan Hermon  “A technical report on hitting times, mixing and cutoff”  In _arXiv preprint arXiv:1501.01869_ , 2015
  * [10] David A Levin and Yuval Peres  “Markov chains and mixing times”  American Mathematical Soc., 2017
  * [11] L Miclo  “About relaxation time of finite generalized Metropolis algorithms”  In _The Annals of Applied Probability_ 12.4 Institute of Mathematical Statistics, 2002, pp. 1492–1515
  * [12] Roberto Oliveira  “Mixing and hitting times for finite Markov chains”, 2012
  * [13] Yuval Peres and Perla Sousi  “Mixing times are hitting times of large sets”  In _Journal of Theoretical Probability_ 28.2 Springer, 2015, pp. 488–519
  * [14] Yury Polyanskiy and Yihong Wu  “Information theory: From coding to learning”  In _Book draft_ , 2022
  * [15] Eugene Seneta  “Non-negative matrices and Markov chains”  Springer Science & Business Media, 2006
  * [16] Perla Sousi and Peter Winkler  “Mixing times and moving targets”  In _Combinatorics, Probability and Computing_ 23.3 Cambridge University Press, 2014, pp. 460–476
  * [17] Tim Van Erven and Peter Harremos  “Rényi divergence and Kullback-Leibler divergence”  In _IEEE Transactions on Information Theory_ 60.7 IEEE, 2014, pp. 3797–3820
  * [18] Geoffrey Wolfer and Shun Watanabe  “Information geometry of reversible Markov chains”  In _Information Geometry_ 4.2 Springer, 2021, pp. 393–433

## References

  * [19] David J Aldous  “Some inequalities for reversible Markov chains”  In _Journal of the London Mathematical Society_ 2.3 Oxford University Press, 1982, pp. 564–576
  * [20] Robert M Anderson, Haosui Duanmu and Aaron Smith  “Mixing times and hitting times for general Markov processes”  In _Israel Journal of Mathematics_ Springer, 2023, pp. 1–76
  * [21] Riddhipratim Basu, Jonathan Hermon and Yuval Peres  “Characterization of cutoff for reversible Markov chains”  In _Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms_ , 2014, pp. 1774–1791  SIAM
  * [22] Louis J Billera and Persi Diaconis  “A geometric interpretation of the Metropolis-Hastings algorithm”  In _Statistical Science_ JSTOR, 2001, pp. 335–339
  * [23] Olivier Catoni  “Simulated annealing algorithms and Markov chains with rare transitions”  In _Séminaire de probabilités XXXIII_ Springer, 2006, pp. 69–119
  * [24] Joel E Cohen et al.  “Relative entropy under mappings by stochastic matrices”  In _Linear algebra and its applications_ 179 Elsevier, 1993, pp. 211–235
  * [25] T.M. Cover and J.A. Thomas  “Elements of Information Theory”  Wiley, 2012  URL: https://books.google.com.sg/books?id=VWq5GG6ycxMC
  * [26] Simon Griffiths, Ross Kang, Roberto Oliveira and Viresh Patel  “Tight inequalities among set hitting times in Markov chains”  In _Proceedings of the American Mathematical Society_ 142.9, 2014, pp. 3285–3298
  * [27] Jonathan Hermon  “A technical report on hitting times, mixing and cutoff”  In _arXiv preprint arXiv:1501.01869_ , 2015
  * [28] David A Levin and Yuval Peres  “Markov chains and mixing times”  American Mathematical Soc., 2017
  * [29] L Miclo  “About relaxation time of finite generalized Metropolis algorithms”  In _The Annals of Applied Probability_ 12.4 Institute of Mathematical Statistics, 2002, pp. 1492–1515
  * [30] Roberto Oliveira  “Mixing and hitting times for finite Markov chains”, 2012
  * [31] Yuval Peres and Perla Sousi  “Mixing times are hitting times of large sets”  In _Journal of Theoretical Probability_ 28.2 Springer, 2015, pp. 488–519
  * [32] Yury Polyanskiy and Yihong Wu  “Information theory: From coding to learning”  In _Book draft_ , 2022
  * [33] Eugene Seneta  “Non-negative matrices and Markov chains”  Springer Science & Business Media, 2006
  * [34] Perla Sousi and Peter Winkler  “Mixing times and moving targets”  In _Combinatorics, Probability and Computing_ 23.3 Cambridge University Press, 2014, pp. 460–476
  * [35] Tim Van Erven and Peter Harremos  “Rényi divergence and Kullback-Leibler divergence”  In _IEEE Transactions on Information Theory_ 60.7 IEEE, 2014, pp. 3797–3820
  * [36] Geoffrey Wolfer and Shun Watanabe  “Information geometry of reversible Markov chains”  In _Information Geometry_ 4.2 Springer, 2021, pp. 393–433