# PAC-Bayes Bounds on Variational Tempered Posteriors for Markov Models

Imon Banerjee  Vinayak A. Rao  Department of Statistics, Purdue University,
West Lafayette IN 47906<EMAIL_ADDRESS>Harsha Honnappa
School of Industrial Engineering, Purdue University, West Lafayette IN 47906

###### Abstract.

Datasets displaying temporal dependencies abound in science and engineering
applications, with Markov models representing a simplified and popular view of
the temporal dependence structure. In this paper, we consider Bayesian
settings that place prior distributions over the parameters of the transition
kernel of a Markov model, and seeks to characterize the resulting, typically
intractable, posterior distributions. We present a PAC-Bayesian analysis of
variational Bayes (VB) approximations to tempered Bayesian posterior
distributions, bounding the model risk of the VB approximations. Tempered
posteriors are known to be robust to model misspecification, and their
variational approximations do not suffer the usual problems of over confident
approximations. Our results tie the risk bounds to the mixing and ergodic
properties of the Markov data generating model. We illustrate the PAC-Bayes
bounds through a number of example Markov models, and also consider the
situation where the Markov model is misspecified.

##  1\. Introduction

This paper presents probably approximately correct (PAC)-Bayesian bounds on
variational Bayesian (VB) approximations of fractional or tempered posterior
distributions for Markov data generation models. Exact computation of either
standard or tempered posterior distributions is a hard problem that has,
broadly speaking, spawned two classes of computational methods. The first,
Markov chain Monte Carlo (MCMC), constructs ergodic Markov chains to
approximately sample from the posterior distribution. MCMC is known to suffer
from high variance and complex diagnostics, leading to the development of
variational Bayesian (VB) [25] methods as an alternative in recent years. VB
methods pose posterior computation as a variational optimization problem,
approximating the posterior distribution of interest by the ‘closest’ element
of an appropriately defined class of ‘simple’ probability measures. Typically,
the measure of closeness used by VB methods is the Kullback-Leibler (KL)
divergence. Excellent introductions to this so-called KL-VB method can be
found in [5, 21, 6]. More recently, there has also been interest in
alternative divergence measures, particularly the $\alpha$-Rényi divergence
[16, 19, 8], though in this paper, we focus on the KL-VB setting.

Theoretical properties of VB approximations, and in particular asymptotic
frequentist consistency, have been studied extensively under the assumption of
an independent and identically distributed (i.i.d.) data generation model [6,
26, 28]. On the other hand, the common setting where data sets display
temporal dependencies presents unique challenges. In this paper, we focus on
homogeneous Markov chains with parameterized transition kernels, representing
a parsimonious class of data generation models with a wide range of
applications. We work in the Bayesian framework, focusing on the posterior
distribution over the unknown parameters of the transition kernel. Our theory
develops PAC bounds that link the ergodic and mixing properties of the data
generating Markov chain to the Bayes risk associated with approximate
posterior distributions.

Frequentist consistency of Bayesian methods, in the sense of concentration of
the posterior distribution around neighborhoods of the ‘true’ data generating
distribution, have been established in significant generality, in both the
i.i.d. [10, 24, 22] and in the non-i.i.d. data generation setting [11, 3].
More recent work [1, 27, 3] has studied fractional or tempered posteriors, a
class of generalized Bayesian posteriors obtained by combining the likelihood
function raised to a fractional power with an appropriate prior distribution
using Bayes theorem. Tempered posteriors are known to be robust against model
misspecification: in the Markov setting we consider, the associated stationary
distribution as well as mixing properties are sensitive to model
parameterization. Further, tempered posteriors are known to be much simpler to
analyze theoretically [27, 3]. Therefore, following [1, 27, 3] we focus on
tempered posterior distributions on the transition kernel parameters, and
study the rate of concentration of variational approximations to the tempered
posterior. Equivalently, as shown in [27] and discussed in section 1.1, our
results also apply to so-called $\alpha$-variational approximations to
standard posterior distributions over kernel parameters. The latter are
modifications of the standard KL-VB algorithm to address the well-known
problem of overconfident posterior approximations.

While there have been a number of recent papers studying the consistency of
approximate variational posteriors [26, 16, 1] in the large sample limit,
rates of convergence have received less attention. Exceptions include [1, 28,
15], where an i.i.d. data generation model is assumed. [1] establishes PAC-
Bayes bounds on the convergence of a variational tempered posterior with
fractional powers in the range $[0,1)$, while [28] considers the standard
variational posterior case (where the fractional power equals $1$). [15], on
the other hand, establishes PAC-Bayes bounds for risk-sensitive Bayesian
decision making problems in the standard variational posterior setting. The
setting in [1] allows for model misspecification and the analysis is generally
more straightforward than that in [28, 15]. Our work extends [1] to the
setting of a discrete-time Markov data generation model.

Our first results in Theorem 2.1 and Corollary 2.1 of Section 2 establish PAC-
Bayes bounds for sequences with arbitrary temporal dependence. Our results
generalize [1, Theorem 2.4] to the non-i.i.d. data setting in a
straightforward manner. Note that Theorem 2.1 also recovers [27, Theorem 3.3],
which is established under different ‘existence of test’ conditions. Our
objective in this paper is to explicate how the ergodic and mixing properties
of the Markov data generating process influences the PAC-Bayes bound. The
sufficient conditions of our theorem, bounding the mean and variance of the
log-likelihood ratio of the data, allows for developing this understanding,
without the technicalities of proving the existence of test conditions
intruding on the insights.

In Section 3 we study the setting where the data generating model is a
stationary $\alpha$-mixing Markov chain. Stationarity implies the existence of
an invariant distribution corresponding to the parameterized transition
kernel, implying the marginal distribution of the Markov data is invariant as
well. The $\alpha$-mixing condition, on the other hand, ensures that the
variance of the likelihood ratio of the Markov data does not grow faster than
linear in the sample size. Our main results in this setting are applicable
when the state space of the Markov chain is either continuous or discrete. The
primary requirement on the class of data generating Markov models is for the
log-likelihood ratio of the parameterized transition kernel and invariant
distribution to satisfy a Lipschitz property. This condition implies a
decoupling between the model parameters and the random samples, affording a
straightforward verification of the mean and variance bounds. We highlight
this main result by demonstrating that it is satisfied by a finite state
Markov chain, a birth-death Markov chain on the positive integers, and a one-
dimensional Gaussian linear model.

In practice, the assumption that the data generating model is stationary is
unlikely to be satisfied. Typically, the initial distribution is arbitrary,
with the state distribution of the Markov sequence converging weakly to the
stationary distribution. In this setting, we must further assume that the
class of data generating Markov chains are geometrically ergodic (with an
exception for finite state Markov chains). We show that this implies the
boundedness of the mean and variance of the log-likelihood ratio of the data
generating Markov chain. Alternatively, in Theorem 4.2 we directly impose a
drift condition on random variables that bound the log-likelihood ratio.
Again, in this more general nonstationary setting, we illustrate the main
results by showing that the PAC-Bayes bound is satisfied by a finite state
Markov chain, a birth-death Markov chain on the positive integers, and a one-
dimensional Gaussian linear model.

In preparation for our main technical results starting in Section 2 we first
note relevant notations and definitions in the next section.

###  1.1. Notations and Definitions

We broadly adopt the notation in [1]. Let the sequence of random variables
$X^{n}=(X_{0},\ldots,X_{n})\subset\mathbb{R}^{m\times(n+1)}$ represent a data
set of $n+1$ observations drawn from a joint distribution
$P_{\theta_{0}}^{(n)}$, where $\theta_{0}\in\Theta\subseteq\mathbb{R}^{d}$ is
the ‘true’ parameter underlying the data generation process. We assume the
state space $S\subseteq\mathbb{R}^{m}$ of the random variables $X_{i}$ is
either discrete-valued or continuous, and write $\\{x_{0},\dots,x_{n}\\}$ for
a realization of the dataset. We also adopt the convention that
$0\log(0/0)=0$.

For each $\theta\in\Theta$, we will write $p_{\theta}^{(n)}$ as the
probability density of $P_{\theta}^{(n)}$ with respect to some measure
$Q^{(n)}$, i.e. $p_{\theta}^{(n)}:=\frac{dP_{\theta}^{(n)}}{dQ^{(n)}}$, where
$Q^{(n)}$ is either Lebesgue measure or the counting measure. All expectations
and variances, which we represent as $\mathrm{E}[X]$ and $\mathrm{Var}[X]$,
are taken with respect to the true distribution $P_{\theta_{0}}$ unless stated
otherwise.

Let $\pi(\theta)$ be a prior distribution with support $\Theta$. The
fractional posterior is defined as

(1) $\displaystyle\pi_{n,\alpha|X^{n}}(d\theta)$
$\displaystyle:=\frac{e^{-\alpha
r_{n}(\theta,\theta_{0})(X^{n})}\pi(d\theta)}{\int e^{-\alpha
r_{n}(\theta,\theta_{0})(X^{n})}\pi(d\theta)},$

where, for $\theta,\theta_{0}\in\Theta$,
$r_{n}(\theta,\theta_{0})(\cdot):=\log\left(\frac{p^{(n)}_{\theta_{0}}(\cdot)}{p^{(n)}_{\theta}(\cdot)}\right)$,
is the log-likelihood ratio of the corresponding density functions. Setting
$\alpha=1$ recovers the standard Bayesian posterior.

The Kullback-Leibler (KL) divergence between distributions $P,Q$ is defined as

$\displaystyle\mathcal{K}(P,Q):=\int_{\mathcal{X}}\log\left(\frac{p(x)}{q(x)}\right)p(x)dx,$

where $\mathcal{X}$ is an arbitrary sample space, and $p,q$ are the densities
corresponding to $P,Q$ (respectively). In particular, the KL divergence
between the distributions parameterized by $\theta_{0}$ and $\theta$ is

$\displaystyle\mathcal{K}(P^{(n)}_{\theta_{0}},P^{(n)}_{\theta})$
$\displaystyle:=\int\log\left(\frac{p^{(n)}_{\theta_{0}}(x_{0},\dots,x_{n})}{p^{(n)}_{\theta}(x_{0},\dots,x_{n})}\right)p^{(n)}_{\theta_{0}}(x_{0},\dots,x_{n})dx_{0}\cdots
dx_{n}$ (2) $\displaystyle=\int
r_{n}(\theta,\theta_{0})(x_{0},\dots,x_{n})p^{n}_{\theta_{0}}(x_{0},\dots,x_{n})dx_{0}\cdots
dx_{n}.$

The $\alpha$-Rényi divergence
$D_{\alpha}(P^{(n)}_{\theta},P^{(n)}_{\theta_{0}})$ is defined as

(3) $\displaystyle D_{\alpha}(P^{(n)}_{\theta},P^{(n)}_{\theta_{0}})$
$\displaystyle:=\frac{1}{\alpha-1}\log\int\exp\left(-\alpha
r_{n}(\theta,\theta_{0})(x_{0},\dots,x_{n})\right)p^{(n)}_{\theta_{0}}(x_{0},\dots,x_{n})dx_{0}\cdots
dx_{n}.$

By letting $\alpha\to 0$, the $\alpha$-Rényi divergence recovers the KL
divergence.

Let $\mathcal{F}$ be some class of distributions with support in
$\mathbb{R}^{d}$ and such that any distribution $P$ in $\mathcal{F}$ is
absolutely continuous with respect to the tempered posterior:
$P\ll\pi_{n,\alpha|X^{n}}$. Let $\tilde{\pi}_{n,\alpha|X^{n}}$ be the
variational approximation to the tempered posterior, defined as

(4) $\displaystyle\leavevmode\nobreak\ \tilde{\pi}_{n,\alpha|X^{n}}$
$\displaystyle:=\underset{\rho\in\mathcal{F}}{\arg\min}\enspace\mathcal{K}(\rho,\pi_{n,\alpha|X^{n}})$

Many choices of $\mathcal{F}$ exist; for instance, $\mathcal{F}$ can be the
set of Gaussian measures, denoted $\mathcal{F}^{\Phi}_{id}$:

(5) $\displaystyle\mathcal{F}^{\Phi}_{id}$
$\displaystyle=\\{\Phi(d\theta;\mu,\Sigma):\mu\in\mathbb{R}^{d},\Sigma_{d\times
d}\in\text{P.D.}\\},$

where P.D. references the class of positive definite matrices. Alternately,
$\mathcal{F}$ can be the family of mean-field or factored distributions where
the components $\theta_{i}$ of $\theta$ are independent of each other.

It is easy to see that eq. 4 is equivalent to the following optimization
problem:

(6) $\displaystyle\leavevmode\nobreak\ \tilde{\pi}_{n,\alpha|X^{n}}$
$\displaystyle:=\underset{\rho\in\mathcal{F}}{\arg\max}\int
r_{n}(\theta,\theta_{0})(x_{0},\dots,x_{n})\rho({d\theta})-\alpha^{-1}\mathcal{K}(\rho,\pi).$

Setting $\alpha=1$ again recovers the usual variational solution that seeks to
approximate the posterior distribution with the closest element of
$\mathcal{F}$ (the right-hand side above is called the evidence lower bound
(ELBO)). Other settings of $\alpha$ constitute $\alpha$-variational inference
[27], which seeks to regularize the ‘overconfident’ approximate posteriors
that standard variational methods tend to produce.

####  1.1.1. Markov chains

We assume the joint density or probability mass function
$p_{\theta}^{(n)}(x_{0},\dots,x_{n})$ corresponds to the ‘walk probability’ of
a time-homogeneous Markov chain. We call the Markov chain ‘parameterized’ if
the transition kernel $p_{\theta}(\cdot|\cdot)$ is parametrized by some
$\theta\in\Theta\subseteq\mathbb{R}^{d}$. Let $q^{(0)}(\cdot)$ be the initial
density (defined with respect to the Lebesgue measure over $\mathbb{R}^{m}$)
or initial probability mass function. Then, the joint density or probability
mass function is
$p_{\theta}^{(n)}(x_{0},\dots,x_{n})=q^{(0)}(x_{0})\prod_{i=0}^{n-1}p_{\theta}(x_{i+1}|x_{i})$.

Our results in the ensuing sections will be established under strong mixing
conditions [7] on the Markov chain. Specifically, recall the definition of the
$\alpha$-mixing coefficients of a stationary Markov chain:

######  Definition 1.1 ($\alpha$-mixing coefficient).

Let $\mathcal{M}_{i}^{j}$ denote the $\sigma$-field generated by the Markov
chain $\\{X_{k}:i\leq k\leq j\\}$ parameterized by $\theta\in\Theta$. Then,
the $\alpha$-mixing coefficient is defined as

(7)
$\displaystyle\alpha_{k}=\underset{t>0}{\sup}\underset{(A,B)\in\mathcal{M}_{-\infty}^{t}\times\mathcal{M}_{t+k}^{\infty}}{\sup}\left|P_{\theta}(A\cap
B)-P_{\theta}(A)P_{\theta}(B)\right|.$

Informally speaking, the $\alpha$-mixing coefficients $\\{\alpha_{k}\\}$
measure the dependence between any two events $A$ (in the ‘history’
$\sigma$-algebra) and $B$ (in the ‘future’ $\sigma$-algebra) with a time lag
$k$. Our results in Section 4 also rely on the ergodic properties of the
Markov chain, and we assume that the Markov chain is $V$-geometrically ergodic
[20, Chapter 15]. First, refer to the definition of the functional norm
$\|\cdot\|_{V}$, from 1.2,

######  Definition 1.2 ($f$-norm).

The functional norm in $f$-metric of the measure $v$, or the $f$-norm of $v$
is defined as

(8) $\|v\|_{f}=\underset{g:|g|<f}{\sup}\left|\int gdv\right|.$

An immediate consequence of this definition is that if $f_{1},f_{2}$ are two
functions such that $f_{1}<f_{2}$ (i.e., for all points in the support of the
functions), then

(9) $\leavevmode\nobreak\ \|v\|_{f_{1}}\leq\|v\|_{f_{2}}.$

Now that we have defined the $\|\cdot\|_{f}$ norm, we can now define
$V$-geometric ergodicity. In the following, we assume the Markov chain is
positive Harris; see [20] for a definition. This is a mild and fairly standard
assumption in Markov chain theory.

######  Definition 1.3 ($V$-geometric ergodicity).

A stationary Markov chain $\\{X_{n}\\}$ parameterized by $\theta\in\Theta$ is
$V$-geometrically ergodic if it is positive Harris and there exists a constant
$r_{V}>1$, that depends on $V$, such that for any $A\in\mathcal{B}(X)$,

(10) $\sum_{n=1}^{n}r_{V}^{n}\left\|P_{\theta}(X_{n}\in
A|X_{0}=x)-\int_{A}q_{\theta}(y)dy\right\|_{V}<\infty.$

It is straightforward to see that this is equivalent to

$\left\|P_{\theta}(X_{n}\in A|X_{0}=x)-\int q_{\theta}(y)dy\right\|_{V}\leq
Cr^{-n}$

for an appropriate constant $C$ (which may depend on the state $x$). That is,
the Markov chain approaches steady state at a geometrically fast rate. If a
Markov chain is $V$-geometrically ergodic for $V\equiv 1$, then, it is simply
termed as geometrically ergodic. It is straightforward to see (via theorem A.2
in the appendix) that a geometrically ergodic Markov chain is also
$\alpha$-mixing, with $\alpha$ coefficients satisfying

(11) $\sum_{k\geq
0}\alpha_{k}^{\upsilon}<\infty\enspace\forall\enspace\upsilon>0,$

showing that, under geometric ergodicity, the alpha mixing coefficients raised
to any positive power $\upsilon$ are finitely summable. We note here that the
most standard procedure to establish $V$-geometric ergodicity for any Markov
chain is through the verification of the drift condition, A.1. If a Markov
chain satisfies A.1, then Theorem A.1 proves that it is also $V$-geometrically
ergodic.

##  2\. A Concentration Bound for the $\alpha$-Rényi Divergence

The object of analysis in what follows is the probability measure
$\tilde{\pi}_{n,\alpha|X^{n}}(\theta)$, the variational approximation to the
tempered posterior. Our main result establishes a bound on the Bayes risk of
this distribution; in particular, given a sequence of loss functions
$\ell_{n}(\theta,\theta_{0})$, we bound
$\int\ell_{n}(\theta,\theta_{0})\tilde{\pi}_{n,\alpha|X^{n}}(\theta)d\theta$.
Following recent work in both the i.i.d. and dependent sequence setting [3, 1,
27], we will use
$\ell_{n}(\theta,\theta_{0})=D_{\alpha}(P^{(n)}_{\theta},P^{(n)}_{\theta_{0}})$,
the $\alpha$-Rényi divergence between $P^{(n)}_{\theta}$ and
$P^{(n)}_{\theta_{0}}$ as our loss function (recall that for each
$\theta\in\Theta$ and $n\geq 1$, $P_{\theta}^{(n)}$ is the distribution
corresponding to the sequence $\\{X_{0},\ldots,X_{n}\\}$). Unlike more obvious
loss functions like Euclidean distance, Rényi divergence compares $\theta$ and
$\theta_{0}$ through their effect on observed sequences, so that issues like
parameter identifiability are no longer relevant. Our first result generalizes
[1, Theorem 2.1] to a non-i.i.d. data setting.

######  Proposition 2.1.

Let $\mathcal{F}$ be a subset of all probability distributions on $\Theta$.
For any $\alpha\in(0,1)$, $\epsilon\in(0,1)$ and $n\geq 1$, the following
probabilistic uniform upper bound on the expected $\alpha$-Rényi divergence
holds:

(12) $\displaystyle P^{(n)}_{\theta_{0}}\left[\sup_{\rho\in\mathcal{F}}\int
D_{\alpha}(P^{(n)}_{\theta},P^{(n)}_{\theta_{0}})\rho(d\theta)\leq\frac{\alpha}{1-\alpha}\int
r_{n}(\theta,\theta_{0})\rho(d\theta)+\frac{\mathcal{K}(\rho,\pi)+\log(\frac{1}{\epsilon})}{1-\alpha}\right]\geq
1-\epsilon.$

The proof of Proposition 2.1 follows easily from [1], and we include it in
Section C.1 for completeness. Mirroring the comments in [1], when
$\rho=\tilde{\pi}_{n,\alpha}$ this result is precisely [3, Theorem 3.5]. This
probabilistic bound implies the following PAC-Bayesian concentration bound on
the model risk computed with respect to the fractional variational posterior:

######  Theorem 2.1.

Let $\mathcal{F}$ be a subset of all probability distributions parameterized
by $\Theta$, and assume there exist $\epsilon_{n}>0$ and
$\rho_{n}\in\mathcal{F}$ such that

  1. (i)

$\int\mathcal{K}(P^{(n)}_{\theta_{0}},P^{(n)}_{\theta})\rho_{n}(d\theta)=\int\mathrm{E}[r_{n}(\theta,\theta_{0})]\rho_{n}(d\theta)\leq
n\epsilon_{n}$,

  2. (ii)

$\int\mathrm{Var}\left(r_{n}(\theta,\theta_{0})\right)\rho_{n}(d\theta)\leq
n\epsilon_{n}$, and

  3. (iii)

$\mathcal{K}(\rho_{n},\pi)\leq n\epsilon_{n}$.

Then, for any $\alpha\in(0,1)$ and $(\epsilon,\eta)\in(0,1)\times(0,1)$,

(13) $\displaystyle\leavevmode\nobreak\ P\left[\int
D_{\alpha}(P^{(n)}_{\theta},P^{(n)}_{\theta_{0}})\tilde{\pi}_{n,\alpha}(d\theta|X^{(n)})\leq\frac{(\alpha+1)n\epsilon_{n}+\alpha\sqrt{\frac{n\epsilon_{n}}{\eta}}-\log(\epsilon)}{1-\alpha}\right]\geq
1-\epsilon-\eta.$

The proof of Theorem 2.1 is a straightforward generalization of [1, Theorem
2.4] to the non-i.i.d. setting, and a special case of [27, Theorem 3.1], where
the problem setting includes latent variables. We include a proof for
completeness. As noted in [1], the sufficient conditions follow closely from
[11] and we will show that they hold for a variety of Markov chain models.

A direct corollary of Theorem 2.1 follows by setting
$\eta=\frac{1}{n\epsilon_{n}}$, $\epsilon=e^{-n\epsilon_{n}}$ and using the
fact that $e^{-n\epsilon_{n}}\geq\frac{1}{n\epsilon_{n}}$. Note that eq. 13 is
vacuous if $\eta+\epsilon>1$. Therefore, without loss of generality, we
restrict ourselves to the condition $\frac{2}{n\epsilon_{n}}<1$.

######  Corollary 2.1.

Assume $\exists\hskip 2.84526pt\epsilon_{n}>0$, $\rho_{n}\in\mathcal{F}$ such
that the following conditions hold:

  1. (i)

$\int\mathcal{K}(P^{(n)}_{\theta_{0}},P^{(n)}_{\theta})\rho_{n}(d\theta)=\int
E[r_{n}(\theta,\theta_{0})]\rho_{n}(d\theta)\leq n\epsilon_{n}$ ,

  2. (ii)

$\int\mathrm{Var}\left(r_{n}(\theta,\theta_{0})\right)\rho_{n}(d\theta)\leq
n\epsilon_{n}$ , and

  3. (iii)

$\mathcal{K}(\rho_{n},\pi)\leq n\epsilon_{n}$.

Then, for any $\alpha\in(0,1)$,

(14) $\displaystyle P\bigg{[}\int
D_{\alpha}(P^{(n)}_{\theta},P^{(n)}_{\theta_{0}})\tilde{\pi}_{n,\alpha}(d\theta|X^{(n)})\leq\frac{(\alpha+1)\epsilon_{n}}{1-\alpha}\bigg{]}\geq
1-\frac{2}{n\epsilon_{n}}.$

Observe that the first two conditions in Corollary 2.1 ensure that the
distribution $\rho_{n}$ concentrates on parameters $\theta\in\Theta$ around
the true parameter $\theta_{0}$, while the third condition requires that
$\rho_{n}$ not diverge from the prior $\pi$ rapidly as a function of the
sample size $n$. In general, satisfying the first and third conditions is
relatively straightforward. The second condition, on the other hand, is
significantly more complicated in the current setting of dependent data, as
the variance of $r_{n}(\theta,\theta_{0})$ includes correlations between the
observations $\\{X_{0},\dots,X_{n}\\}$. In the next section, we will make
assumptions on the transition kernels (and corresponding invariant densities)
that ’decouple’ the temporal correlations and the model parameters in the
setting of strongly mixing and ergodic Markov chain models, and allow for the
verification of the conditions in Corollary 2.1.

Ṫhe computations critical to the verification of the conditions in Corollary
2.1 are the bounds (i) and (ii), and Propositions 2.2 and 2.3 below
characterize the expectation and variance of the log-likelihood ratio
$r_{n}(\cdot,\cdot)$ in terms of the one-step transition kernels of the Markov
chain. First, consider the expectation of $r_{n}(\cdot,\cdot)$ in condition
(i).

######  Proposition 2.2.

Fix $\theta_{1},\theta_{2}\in\Theta$ and consider the parameterized Markov
transition kernels $p_{\theta_{1}}$ and $p_{\theta_{2}}$, and initial
distributions $q^{(0)}_{\theta_{1}}$ and $q^{(0)}_{\theta_{2}}$. Let
$p_{\theta_{1}}^{(n)}$ and $p_{\theta_{2}}^{(n)}$ be the corresponding joint
probability densities; that is,
$p_{\theta_{j}}^{(n)}(x_{0},\ldots,x_{n})=q_{\theta_{j}}^{(0)}(x_{0})\prod_{i=1}^{n}p_{\theta_{i}}(x_{i}|x_{i-1})$
for $j\in\\{1,2\\}$. Then, for any $n\geq 1$, the log-likelihood ratio
$r_{n}(\theta_{2},\theta_{1})$ satisfies

(15) $\displaystyle\leavevmode\nobreak\
\mathrm{E}_{\theta_{1}}\left[r_{n}(\theta_{2},\theta_{1})\right]$
$\displaystyle=\sum_{i=1}^{n}\mathrm{E}_{\theta_{1}}\left[\log\left(\frac{p_{\theta_{1}}(X_{i}|X_{i-1})}{p_{\theta_{2}}(X_{i}|X_{i-1})}\right)\right]+\mathrm{E}[Z_{0}],$

where
$Z_{0}:=\log\left(\frac{q^{(0)}_{\theta_{1}}(X_{0})}{q^{(0)}_{\theta_{2}}(X_{0})}\right)$.
The expectation in the first term is with respect to the joint density
function $p_{\theta_{1}}(y,x)=p_{\theta_{1}}(y|x)q^{(i-1)}_{\theta_{1}}(x)$
where the marginal density satisfies

$\displaystyle q^{(i-1)}_{\theta_{1}}(x)=\begin{cases}\int
p_{\theta_{1}}^{(i-1)}(x_{0},\ldots,x_{i-2},x)dx_{0}\cdots
dx_{i-2}&\leavevmode\nobreak\ \text{for}\leavevmode\nobreak\ i>1,and\\\
q_{\theta_{1}}^{(0)}(x)&\leavevmode\nobreak\ \text{for}\leavevmode\nobreak\
i=1.\end{cases}$

If the Markov chain is also stationary under $\theta_{1}$, then eq. 15
simplifies to

(16)
$\displaystyle\mathrm{E}_{\theta_{1}}\left[r_{n}(\theta_{2},\theta_{1})\right]=n\mathrm{E}_{\theta_{1}}\left[\log\left(\frac{p_{\theta_{1}}(X_{1}|X_{0})}{p_{\theta_{2}}(X_{1}|X_{0})}\right)\right]+\mathrm{E}_{\theta_{1}}[Z_{0}].$

Notice that $\mathrm{E}_{\theta_{1}}\left[r_{n}(\theta_{2},\theta_{1})\right]$
is precisely the KL divergence,
$\mathcal{K}(P^{(n)}_{\theta_{1}},P^{(n)}_{\theta_{2}})$. Next, the following
proposition uses [13, Lemma 1.3] to upper bound the variance of the log-
likelihood ratio.

######  Proposition 2.3.

Fix $\theta_{1},\theta_{2}\in\Theta$ and consider parameterized Markov
transition kernels $p_{\theta_{1}}$ and $p_{\theta_{2}}$, with initial
distributions $q^{(0)}_{\theta_{1}}$ and $q^{(0)}_{\theta_{2}}$. Let
$p_{\theta_{1}}^{(n)}$ and $p_{\theta_{2}}^{(n)}$ be the corresponding joint
probability densities of the sequence $(x_{0},\dotsc,x_{n})$, and
$q^{(i)}_{\theta_{j}}$ the marginal density for $i\in\\{1,\ldots,n\\}$ and
$j\in\\{1,2\\}$. Fix $\delta>0$ and, for each $i\in\\{1,\dots,n\\}$, define

$\displaystyle C_{\theta_{1},\theta_{2}}^{(i)}$
$\displaystyle:=\int\left|\log\left(\frac{p_{\theta_{1}}(x_{i}|x_{i-1})}{p_{\theta_{2}}(x_{i}|x_{i-1})}\right)\right|^{2+\delta}p_{\theta_{1}}(x_{i}|x_{i-1})q^{(i-1)}_{\theta_{1}}(x_{i-1})dx_{i}dx_{i-1}.$

Similarly, define
$Z_{0}:=\log\left(\frac{q^{(0)}_{\theta_{1}}(X_{0})}{q^{(0)}_{\theta_{2}}(X_{0})}\right)$,
and $D_{1,2}:=\mathrm{E}_{q_{\theta_{1}}^{(0)}}\left|Z_{0}\right|^{2+\delta}.$
Suppose the Markov chain corresponding to $\theta_{1}$ is $\alpha$-mixing with
coefficients $\\{\alpha_{k}\\}$. Then,

$\displaystyle\leavevmode\nobreak\
\mathrm{Var}\left(r_{n}(\theta_{1},\theta_{2})\right)$
$\displaystyle<\sum_{i,j=1}^{n}\left(\frac{4}{n}+2n^{\delta/2}(C_{\theta_{1},\theta_{2}}^{(i)}+C_{\theta_{1},\theta_{2}}^{(j)}+2\sqrt{C_{\theta_{1},\theta_{2}}^{(i)}C_{\theta_{1},\theta_{2}}^{(j)}})\right)\left(\alpha_{|i-j|-1}^{\delta/(2+\delta)}\right)$
(17)
$\displaystyle\qquad+\sum_{i=1}^{n}\left(\frac{4}{n}+2n^{\delta/2}(C_{\theta_{1},\theta_{2}}^{(i)}+D_{1,2}+\sqrt{C_{\theta_{1},\theta_{2}}^{(i)}D_{1,2}})\right)\left(\alpha_{i-1}^{\delta/(2+\delta)}\right)+\mathrm{Cov}(Z_{0},Z_{0}).$

Note that this result holds for any parameterized Markov chain. In particular,
when the Markov chain is stationary,
$C_{\theta_{1},\theta_{2}}^{(i)}=C_{\theta_{1},\theta_{2}}^{(1)}\enspace\forall\enspace
i$ and $\forall\theta\in\Theta$, and the expression proposition 2.3 simplifies
to

$\displaystyle\mathrm{Var}\left(r_{n}(\theta_{1},\theta_{2})\right)$
$\displaystyle<n\left(\frac{4}{n}+6n^{\delta/2}C_{\theta_{1},\theta_{2}}^{(1)}\right)\left(\sum_{k\geq
0}\alpha_{k}^{\delta/(2+\delta)}\right)$ (18)
$\displaystyle\qquad+\left(\frac{4}{n}+2n^{\delta/2}(C_{\theta_{1},\theta_{2}}^{(1)}+D_{1,2}+\sqrt{C_{\theta_{1},\theta_{2}}^{(1)}D_{1,2}})\right)\left(\sum_{k\geq
1}\alpha_{k}^{\delta/(2+\delta)}\right)+\mathrm{Cov}(Z_{0},Z_{0}).$

If the sum $\sum_{k\geq 0}\alpha_{k}^{\delta/(2+\delta)}$ is infinite, the
bound is trivially true. For it to be finite, of course, the coefficients
$\alpha_{k}$ must decay to zero sufficiently quickly. For instance, Theorem
A.2 shows that if the Markov chain is geometrically ergodic, then the
$\alpha$-mixing coefficients are geometrically decreasing. We will use this
fact when the Markov chain is non-stationary, as in Section 4. In the next
section, however, we first consider the simpler stationary Markov chain
setting where ergodic conditions are not explicitly imposed. We also note that
unless only a finite number of $\alpha_{k}$ are nonzero, the sum $\sum_{k\geq
0}\alpha_{k}^{\delta/(2+\delta)}$ is infinite when $\delta=0$, and our results
will typically require $\delta>0$.

##  3\. Stationary Markov Data-Generating Models

In this section we assume that corresponding to each transition kernel
$p_{\theta},\leavevmode\nobreak\ \theta\in\Theta,$ there exists an invariant
distribution $q^{(\infty)}_{\theta}\equiv q_{\theta}$ that satisfies

$q_{\theta}(x)=\int p_{\theta}(x|y)q_{\theta}(dy)\quad\forall
x\in\mathbb{R}^{m},\theta\in\Theta.$

We will also use $q_{\theta}$ to designate the density of the invariant
measure (as before, this is with respect to the Lebesgue or counting measure
for continuous or discrete state spaces respectively). A Markov chain is
stationary if its initial distribution is the invariant probability
distribution, that is, $X_{0}\sim q_{\theta}$.

Observe that the PAC-Bayesian concentration bound in Corollary 2.1
specifically requires bounding the mean and variance of the log-likelihood
ratio $r_{n}(\theta,\theta_{0})$. We ensure this by imposing regularity
conditions on the log-ratio of the one-step transition kernels and the
corresponding invariant densities. Specifically, we assume the following
conditions that decouple the model parameters from the random samples,
allowing us to verify the bounds in Corollary 2.1.

######  Assumption 3.1.

There exist positive functions $M^{(1)}_{k}(\cdot,\cdot)$ and
$M^{(2)}_{k}(\cdot)$, $k\in\\{1,2,\dots,m\\}$ such that for any parameters
$\theta_{1},\theta_{2}\in\Theta$, the log of the ratio of one-step transition
kernels and the log of the ratio of the invariant distributions satisfy,
respectively,

(19) $\displaystyle\leavevmode\nobreak\ |\log p_{\theta_{1}}(x_{1}|x_{0})-\log
p_{\theta_{2}}(x_{1}|x_{0})|\leq\sum_{k=1}^{m}M^{(1)}_{k}(x_{1},x_{0})|f^{(1)}_{k}(\theta_{2},\theta_{1})|\leavevmode\nobreak\
\forall\leavevmode\nobreak\ (x_{0},x_{1}),\text{and}$ (20)
$\displaystyle\leavevmode\nobreak\ |\log q_{\theta_{1}}(x)-\log
q_{\theta_{2}}(x)|\leq\sum_{k=1}^{m}M^{(2)}_{k}(x)|f^{(2)}_{k}(\theta_{2},\theta_{1})|\enspace\forall\enspace
x.$

We further assume that for some $\delta>0$, the functions
$f^{(1)}_{k},f^{(2)}_{k}$ and $M^{(1)}_{k}$ satisfy the following:

  1. (i)

there exist constants $C^{(t)}_{k}$ and measures $\rho_{n}\in\mathcal{F}$ such
that
$\int|f^{(t)}_{k}(\theta,\theta_{0})|^{2+\delta}\rho_{n}(d\theta)<\frac{C_{k}^{(t)}}{n}$
for $t\in\\{1,2\\}$, $n\geq 1$ and $k\in\\{1,2,\dots,m\\}$, and

  2. (ii)

there exists a constant $B$ such that $\int
M^{(1)}_{k}(x_{1},x_{0})^{2+\delta}p_{\theta_{j}}(x_{1}|x_{0})q_{\theta_{j}}^{(0)}(x_{0})dx_{1}dx_{0}<B,\,k\in\\{1,\dotsc,m\\}$
and $j\in\\{1,2\\}$.

The following examples illustrate eq. 19 and eq. 20 for discrete and
continuous state Markov chains.

######  Example 3.1.

Suppose $\\{X_{0},\dots,X_{n}\\}$ is generated by the birth-death chain with
parameterized transition probability mass function,

$\displaystyle p_{\theta}(j|i)=\begin{cases}\theta&\leavevmode\nobreak\
\text{if}\leavevmode\nobreak\ j=i-1,\\\ 1-\theta&\leavevmode\nobreak\
\text{if}\leavevmode\nobreak\ j=i+1.\end{cases}$

In this example, the parameter $\theta$ denotes the probability of birth. We
shall see that, $m=3$: $M^{(1)}_{1}(X_{1},X_{0})=I_{[X_{1}=X_{0}+1]}$,
$M^{(1)}_{2}(X_{1},X_{0})=I_{[X_{1}=X_{0}-1]}$, and
$M^{(1)}_{3}(X_{1},X_{0})=1$. We also define $M^{(2)}_{1}(X_{0})=1$, and set
$M^{(2)}_{2}(X_{0})$ and $M^{(2)}_{3}(X_{0})$ both to $X_{0}-1$. Let
$f^{(1)}_{1}(\theta,\theta_{0})=\log\left[\frac{\theta_{0}}{\theta}\right]$,
$f^{(1)}_{2}(\theta,\theta_{0})=\log\left[\frac{1-\theta_{0}}{1-\theta}\right]$,
$f^{(1)}_{3}(\theta,\theta_{0})=0$,
$f^{(2)}_{1}(\theta,\theta_{0})=-f^{(2)}_{3}(\theta,\theta_{0})=\log\left[\frac{1-\theta_{0}}{1-\theta}\right]$,
and
$f^{(2)}_{2}(\theta,\theta_{0})=\log\left[\frac{\theta_{0}}{\theta}\right]$.
The derivation of these terms and that they satisfy the conditions of 3.1 is
provided in the proof of Proposition 3.3.

######  Example 3.2.

Suppose $\\{X_{0},\dots,X_{n}\\}$ is generated by the ‘simple linear’ Markov
model

$X_{n}=\theta X_{n-1}+W_{n},$

where $\\{W_{n}\\}$ is a sequence of i.i.d. standard Gaussian random
variables. Then, $m=2$, with $M^{(1)}_{1}(X_{n},X_{n-1})=|X_{n}X_{n-1}|$,
$M^{(1)}_{2}(X_{n},X_{n-1})=X_{n}^{2},M^{(2)}_{1}(x)=\frac{x^{2}}{2}$ and
$M^{(2)}_{2}(X)=0$. Corresponding to these, we have
$f^{(1)}_{1}(\theta,\theta_{0})=(\theta-\theta_{0}),f^{(1)}_{2}(\theta,\theta_{0})=(\theta_{0}^{2}-\theta^{2}),f^{(2)}_{1}(\theta_{0},\theta_{0})=(\theta_{0}^{2}-\theta^{2})$
and $f^{(2)}_{2}(\theta_{0},\theta_{0})=0$. The derivation of these quantities
and that these satisfy the conditions of 3.1 under appropriate choices of
$\rho_{n}$ is shown in the proof of Proposition 4.3.

Note that assuming the same number $m$ of $M^{(1)}_{k}$ and $M^{(2)}_{k}$
involves no loss of generality, since these functions can be set to $0$. Both
eq. 19 and eq. 20 can be viewed as generalized Lipschitz-smoothness
conditions, recovering the usual Lipschitz-smoothness when $m=1$ and when
$f_{k}^{(t)}$ is Euclidean distance. Our generalized conditions are useful for
distributions like the Gaussian, where Lipschitz smoothness does not apply.
Observe also that by an application of Jensen’s inequality, 3.1 (i) above
implies that for some constant $C>0$ and
$k\in\\{1,2,\dots,m\\},t\in\\{1,2\\}$,

(21) $\displaystyle\int|f^{(t)}_{k}(\theta,\theta_{0})|\rho_{n}(d\theta)$
$\displaystyle\leq\frac{C}{n^{1/(2+\delta)}}<\frac{C}{\sqrt{n}}.$

3.1 (i) is satisfied in a variety of scenarios, for example, under mild
assumptions on the partial derivatives of the functions $f^{(t)}_{k}$. To
illustrate this, we present the following proposition.

######  Proposition 3.1.

Let $f(\theta,\theta_{0})$ be a function on a bounded domain with bounded
partial derivatives with $f(\theta_{0},\theta_{0})=0$. Let
$\\{\rho_{n}(\cdot)\\}$ be a sequence of probability densities on $\theta$
such that $\mathrm{E}_{\rho_{n}}[\theta]=\theta_{0}$ and
$\mathrm{Var}_{\rho_{n}}[\theta]=\frac{\sigma^{2}}{n}$ for some $\sigma>0$.
Then, for some $C>0$,

(22) $\int|f(\theta,\theta_{0})|^{2+\delta}\rho_{n}(d\theta)<\frac{C}{n}.$

###### Proof.

Define $\partial_{\theta}f(\theta,\theta_{0}):=\frac{\partial
f(\theta,\theta_{0})}{\partial\theta}$ as the partial derivative of the
function $f$. By the mean value theorem,
$|f(\theta,\theta_{0})|=|\theta-\theta_{0}||\partial_{\theta}f(\theta^{*},\theta_{0})|$,
for some
$\theta^{*}\in[\min\\{\theta,\theta_{0}\\},\max\\{\theta,\theta_{0}\\}]$.
Since the partial derivatives are bounded, there exists $L\in\mathbb{R}$ such
that $\partial_{\theta}f(\theta^{*},\theta_{0})<L$, and
$\int|f(\theta,\theta_{0})|^{2+\delta}\rho_{n}(d\theta)<L^{2+\delta}\int|\theta-\theta_{0}|^{2+\delta}\rho_{n}(d\theta)$.
Choose $G>0$ be such that $|\theta|<G$, then
$\left|\frac{\theta-\theta_{0}}{2G}\right|^{2+\delta}<\left|\frac{\theta-\theta_{0}}{2G}\right|^{2}$.
Therefore,
$\int|\theta-\theta_{0}|^{2+\delta}\rho_{n}(d\theta)<(2G)^{2+\delta}\mathrm{Var}\left[\frac{\theta}{2G}\right]<(2G)^{\delta}\frac{\sigma^{2}}{n}$.
Now choosing $(2G)^{\delta}\sigma^{2}$ as $C$ completes the proof. ∎

If $\partial_{\theta}f^{(t)}_{k}$ is continuous and $\Theta$ is compact, then
$\partial_{\theta}f^{(t)}_{k}$ is always bounded. Also observe that if
$\mathrm{E}\left[M^{(1)}_{k}(X_{1},X_{0})^{2+\delta}\right]<B$, without loss
of generality we can use Jensen’s inequality to conclude that, for all
$0<a<2+\delta$,
$\mathrm{E}\left[M^{(1)}_{k}(X_{1},X_{0})^{a}\right]<B^{\frac{a}{2+\delta}}<B$.

We can now state the main theorem of this section.

######  Theorem 3.1.

Let $\\{X_{0},\ldots,X_{n}\\}$ be generated by a stationary, $\alpha$-mixing
Markov chain parametrized by $\theta_{0}\in\Theta$. Suppose that 3.1 holds and
that the $\alpha$-mixing coefficients satisfy $\sum_{k\geq
1}\alpha_{k}^{\delta/(2+\delta)}<+\infty$. Furthermore, assume that
$\mathcal{K}(\rho_{n},\pi)\leq\sqrt{n}C$ for some constant $C>0$. Then, the
conditions of Corollary 2.1 are satisfied with
$\epsilon_{n}\in\mathrm{O}\left(\max(\frac{1}{\sqrt{n}},\frac{n^{\delta/2}}{n})\right)$.

Theorem 3.1 is satisfied by a large class of Markov chains, including chains
with countable and continuous state spaces. In particular, if the Markov chain
is geometrically ergodic, then it follows from eq. 11 that $\sum_{k\geq
1}\alpha_{k}^{\delta/(2+\delta)}<+\infty$. Observe that in order to achieve
$O(\frac{1}{\sqrt{n}})$ convergence, we need $\delta\leq 1$. Note also that as
$\delta$ decreases, satisfying the condition $\sum_{k\geq
1}\alpha_{k}^{\delta/(2+\delta)}$ requires the Markov chain to be faster
mixing.

We now illustrate Theorem 3.1 for a number of Markov chain models. First,
consider a birth-death Markov chain on a finite state space.

######  Proposition 3.2.

Suppose the data-generating process is a birth-death Markov chain, with one-
step transition kernel parametrized by the birth probability
$\theta_{0}\in\Theta$. Let $\mathcal{F}$ be the set of all Beta distributions.
We choose the prior to be a Beta distribution with parameters $\alpha$ and
$\beta$. Then, the conditions of Theorem 3.1 are satisfied and
$\epsilon_{n}\in\mathrm{O}\left(\frac{1}{\sqrt{n}}\right)$.

###### Proof.

The proof of Proposition 3.2 follows from the more general Proposition 4.1, by
fixing the initial distribution to the invariant distribution under
$\theta_{0}$. ∎

The birth death chain on the finite state space is, of course, geometrically
ergodic and the alpha mixing coefficients $\alpha_{k}$ decay geometrically.
Note that the invariant distribution of this Markov chain is uniform over the
state space, and consequently this is a particularly simple example. A more
complicated and more realistic example is a birth-death Markov chain on the
positive integers. We note that if the probability of birth in a birth-death
Markov chain on positive integers is greater than $0.5$, then the Markov chain
is transient, and consequently, not ergodic. As seen in Example 3.1, we
denoted the probability of birth as $\theta$. Hence, our prior should be
chosen in such a fashion that the support should be within $(0,0.5)$. For that
purpose, we define the class of scaled beta distribution.

######  Definition 3.1 (Scaled Beta).

If $X$ is a beta distribution on with parameters $\alpha$ and $\beta$, then
$Y$ is said to be a scaled beta distribution with same parameters on the
interval $(c,m+c)$ if,

$\displaystyle Y$ $\displaystyle=mx+c\enspace;\enspace(m,c)\in\mathbb{R}^{2}$

and in that case, via transformation of variables, the pdf of $Y$ is obtained
as,

$\displaystyle
f(y)=\begin{cases}\frac{m}{\mathrm{Beta}(\alpha,\beta)}\left(\frac{y-c}{m}\right)^{\alpha-1}\left(1-\frac{y-c}{m}\right)^{\beta-1}&\mathrm{if}y\in(c,m+c)\\\
\quad 0&\mathrm{otherwise}.\end{cases}$

It follows that under such circumstances,
$\mathrm{E}[Y]=m\frac{\alpha}{\alpha+\beta}$ and
$\mathrm{Var}[Y]=m^{2}\frac{\alpha\beta}{(\alpha+\beta)^{2}(\alpha+\beta+1)}$.
The scaled beta distribution is a popular distribution which finds use in a
variety of practical applications. One example of such scaled beta
distribution might be when $m=0.5$ and $c=0$. Then it becomes a beta
distribution rescaled to have support on $(0,\frac{1}{2})$. Another example is
when $m=2$ and when $c=-1$. Then it becomes a beta distribution rescaled to
have support on $(-1,1)$.

######  Proposition 3.3.

Suppose the data-generating process is a positive recurrent birth-death Markov
chain on the positive integers parameterized by the birth probability
$\theta_{0}\in(0,\frac{1}{2})$. Further let $\mathcal{F}$ be the set of all
Beta distributions rescaled to have support $(0,\frac{1}{2})$. We choose the
prior to be a scaled Beta distribution on $(0,1/2)$ with parameters $\alpha$
and $\beta$. Then, the conditions of Theorem 3.1 are satisfied with
$\epsilon_{n}\in\mathrm{O}\left(\frac{1}{\sqrt{n}}\right)$.

###### Proof.

The proof of Proposition 3.3 follows from that of Proposition 4.2 by fixing
the initial distribution to the invariant distribution under $\theta_{0}$. ∎

Note that if the transition probability of jumping from state $i$ to state
$i+1$ (i.e., the ‘birth’ probability) is greater than $\frac{1}{2}$, then the
birth-death chain is transient. Therefore, we restrict to only those cases
when the probability of birth is less than $\frac{1}{2}$. Unlike with the
finite state-space, the invariant distribution now depends on the parameter
$\theta\in\Theta$, and verification of the conditions of the proposition is
more involved.

Both Proposition 3.2 and Proposition 3.3 assume a discrete state space. The
next example considers a strictly stationary simple linear model (as defined
in Example 3.2), which has a continuous, unbounded state space.

######  Proposition 3.4.

Suppose the data-generating model is a strictly stationary simple linear model
satisfying the equation

(23) $\displaystyle X_{n}$ $\displaystyle=\theta_{0}X_{n-1}+W_{n},$

where $\\{W_{n}\\}$ are i.i.d. standard Gaussian random variables and
$|\theta_{0}|<1$. Let $\mathcal{F}$ be the space of all parameterized
distributions with support $(-1,1)$ and suppose that $\mathcal{F}$ is the
class of all beta distributions rescaled to have the support $(-1,1)$. Then,
the conditions of Theorem 3.1 are satisfied with
$\epsilon_{n}\in\mathrm{O}\left(\frac{1}{\sqrt{n}}\right)$.

###### Proof.

The proof that simple linear model satisfies 3.1 is deferred to the proof of
Proposition 4.3. The simple linear model with $|\theta_{0}|<1$ has
geometrically decreasing (and therefore summable) $\alpha$-mixing coefficients
as a consequence of [20, eq. (15.49)] and Theorem A.2. Combining these two
facts, it follows that the conditions of Theorem 3.1 are satisfied. ∎

Observe that Theorem 2.1 (and Corollary 2.1) are general, and hold for any
dependent data-generating process. Therefore, there can be Markov chains that
satisfy these, but do not satisfy Assumption 3.1 which entails some loss of
generality. However, as our examples demonstrate, common Markov chain models
do indeed satisfy the latter assumption.

##  4\. Non-Stationary, Ergodic Markov Data-Generating Models

We call a time-homogeneous Markov chain non-stationary if the initial
distribution $q^{(0)}$ is not the invariant distribution. There are two sets
of results in this setting: in Theorem 4.1 and Theorem 4.2 we explicitly
impose the $\alpha$-mixing condition, while in Theorem 4.3 we impose a
$V$-geometric ergodicity condition (1.3). As seen in eq. 11 if the Markov
chain is also geometrically ergodic, then $\forall\enspace\delta>0$,
$\sum\alpha_{k}^{\delta/(2+\delta)}<\infty$. This condition can be relaxed,
albeit at the risk of more complicated calculations that, nonetheless, mirror
those in the geometrically ergodic setting. A common thread through these
results is that we must impose some integrability or regularity conditions on
the functions $M^{(1)}_{k}$.

First, in Theorem 4.1 we assume that the $M^{(1)}_{k}$ functions in 3.1 are
uniformly bounded and that the $\alpha$-mixing condition is satisfied. This
result holds for both discrete and continuous state space settings.

######  Theorem 4.1.

Let $\\{X_{0},\dots,X_{n}\\}$ be generated by an $\alpha$-mixing Markov chain
parametrized by $\theta_{0}\in\Theta$ with transition probabilities satisfying
3.1 and with known initial distribution $q^{(0)}$. Let $\\{\alpha_{k}\\}$ be
the $\alpha$-mixing coefficients under $\theta_{0}$, and assume that
$\sum_{k\geq 1}\alpha_{k}^{{\delta}/{(2+\delta)}}<+\infty$. Suppose that there
exists $B\in\mathbb{R}$ such that $\sup_{x,y}|M^{(1)}_{k}(x,y)|<B$ for all
$k\in\\{1,2,\dots,m\\}$ in 3.1. Furthermore, assume that there exists
$\rho_{n}\in\mathcal{F}$ such that $\mathcal{K}(\rho_{n},\pi)\leq\sqrt{n}C$
for some constant $C>0$. If the initial distribution $q^{(0)}$ satisfies
$E_{q^{(0)}}|M^{(2)}_{k}(X_{0})|^{2}<+\infty$ for all $k\in\\{1,2,\dots,m\\}$,
then the conditions of Corollary 2.1 are satisfied with
$\epsilon_{n}=\mathrm{O}\left(\max(\frac{1}{\sqrt{n}},\frac{n^{\delta/2}}{n})\right)$.

The following result in Proposition 4.1 illustrates Theorem 4.1 in the setting
of a finite state birth-death Markov chain.

######  Proposition 4.1.

Suppose the data-generating process is a finite state birth-death Markov
chain, with one-step transition kernel parametrized by the birth probability
$\theta_{0}$. Let $\mathcal{F}$ be the set of all Beta distributions. We
choose the prior to be a Beta distribution with parameters $\alpha$ and
$\beta$. Then, the conditions of Theorem 4.1 are satisfied with
$\epsilon_{n}=\mathrm{O}\left(\frac{1}{\sqrt{n}}\right)$ for any initial
distribution $q^{(0)}$.

Theorem 4.1 also applies to data generated by Markov chains with countably
infinite state spaces, so long as the class of data-generating Markov chains
is strongly ergodic and the initial distribution has finite second moments.
The following example demonstrates this in the setting of a birth-death Markov
chain on the positive integers, where the initial distribution is assumed to
have finite second moments.

######  Proposition 4.2.

Suppose the data-generating process is a birth-death Markov chain on the non-
negative integers, parameterized by the probability of birth
$\theta_{0}\in(0,\frac{1}{2})$. Further let $\mathcal{F}$ be the set of all
Beta distributions rescaled upon the support $(0,\frac{1}{2})$. Let $q^{(0)}$
be a probability mass function on non-negative integers such that
$\sum_{i=1}^{\infty}i^{2}q^{(0)}(i)<+\infty$. We choose the prior to be a
scaled Beta distribution on $(0,1/2)$ with parameters $\alpha$ and $\beta$.
Then, the conditions of Theorem 4.1 are satisfied with
$\epsilon_{n}=\mathrm{O}\left(\frac{1}{\sqrt{n}}\right)$.

Since continuous functions on a compact domain are bounded, we have the
following (easy) corollary (stated without proof).

######  Corollary 4.1.

Let $\\{X_{0},\dots,X_{n}\\}$ be generated by an $\alpha$-mixing Markov chain
parametrized by $\theta_{0}\in\Theta$ on a compact state space, and with
initial distribution $q^{(0)}$. Suppose the $\alpha$-mixing coefficients
satisfy $\sum_{k\geq 1}\alpha_{k}^{{\delta}/{(2+\delta)}}<+\infty$, and that
3.1 holds with continuous functions $M^{(1)}_{k}(\cdot,\cdot)$,
$k\in\\{1,2,\dots,m\\}$. Furthermore, assume that there exists $\rho_{n}$ such
that $\mathcal{K}(\rho_{n},\pi)\leq\sqrt{n}C$ for some constant C. Then,
Theorem 4.1 is satisfied with
$\epsilon_{n}=\mathrm{O}\left(\max(\frac{1}{\sqrt{n}},\frac{n^{\delta/2}}{n})\right)$.

In general the $M^{(1)}_{k}$ functions will not be uniformly bounded (consider
the case of a Gaussian-Markov simple linear model in Example 3.2), and
stronger conditions must be imposed on the data-generating Markov chain
itself. The following assumption imposes a ‘drift’ condition from [12].
Specifically, [12, Theorem 2.3] shows that under the conditions of 4.1, the
moment generating function of an aperiodic Markov chain $\\{X_{n}\\}$ can be
upper bounded by a function of the moment generating function of $X_{0}$.
Together with the $\alpha$-mixing condition, 4.1 implies that this Markov data
generating process satisfies Corollary 2.1.

######  Assumption 4.1.

Consider a Markov chain $\\{X_{n}\\}$ parameterized by $\theta_{0}\in\Theta$.
Let $\mathcal{M}_{-\infty}^{n}$ denote the $\sigma$-field generated by
$\\{X_{-\infty},\dots,X_{n-1},X_{n}\\}$. Denote the stochastic process
$\\{M^{k}_{n}\\}:=\\{M^{(1)}_{k}(X_{n},X_{n-1})\\}$; recall $M^{(1)}_{k}$, for
each $k=1,\ldots,m_{1}$, are defined in 3.1. For each $k=1,\ldots,m$, the
process $\\{M^{k}_{n}\\}$ is assumed to satisfy the following conditions:

  * •

The drift condition holds for $\\{M^{k}_{n}\\}$, i.e.
$\mathrm{E}\left[M^{k}_{n}-M^{k}_{n-1}|\mathcal{M}_{-\infty}^{n-1},M^{k}_{n-1}>a\right]\leq-\epsilon$
for some $\epsilon,a>0$.

  * •

For some $\lambda>0$ and $\mathcal{D}>0$,
$\mathrm{E}\left[e^{\lambda(M^{k}_{n}-M^{k}_{n-1})}|\mathcal{M}_{-\infty}^{n-1}\right]\leq\mathcal{D}$.

Under this drift condition, the next theorem shows that Corollary 2.1 is
satisfied.

######  Theorem 4.2.

Let $\\{X_{0},\ldots,X_{n}\\}$ be generated by an aperiodic $\alpha$-mixing
Markov chain parametrized by $\theta_{0}\in\Theta$ and initial distribution
$q^{(0)}$. Suppose that 3.1 and 4.1 hold, and that the $\alpha$-mixing
coefficients satisfy $\sum_{k\geq 1}\alpha_{k}^{\delta/(2+\delta)}<+\infty$.
Furthermore, assume $\mathcal{K}(\rho_{n},\pi)\leq\sqrt{n}C$ for some constant
$C>0$. If $\int e^{\lambda
M^{(1)}_{k}(y,x)}p_{\theta_{0}}(y|x)q_{1}^{(0)}(x)dx<+\infty$ for all
$k=1,\ldots,m_{1}$, then the conditions of Corollary 2.1 are satisfied with
$\epsilon_{n}=\mathrm{O}\left(\max(\frac{1}{\sqrt{n}},\frac{n^{\delta/2}}{n})\right)$.

Verifying the conditions in Theorem 4.2 can be quite challenging in general.
Instead, we suggest a different approach that requires $V$-geometric
ergodicity. Unlike the drift condition in 4.1, $V$-geometric ergodicity
additionally requires the existence of a petite set. However, geometric
ergodicity is a fairly standard property that has already been established
from a number of important Markov chains. As noted before, geometric
ergodicity implies $\alpha$-mixing of the Markov chain with geometrically
decaying mixing coefficients. As with Theorem 4.2, we assume that the Markov
chain is aperiodic. It is well known that in case of a periodic Markov chain
with period $d$, the notion of geometric ergodicity only makes sense for the
$d$-chain $\\{X_{dn}\\}.$

######  Theorem 4.3.

Let $\\{X_{0},\dots,X_{n}\\}$ be generated by an aperiodic Markov chain
parametrized by $\theta_{0}\in\Theta$ with known initial distribution
$q^{(0)}$, and assumed to be $V$-geometrically ergodic for some
$V:\mathbb{R}^{m}\to[1,\infty)$. Suppose that 3.1 holds and $\int
M^{(1)}_{k}(y,x)^{2+\delta}p_{\theta_{0}}(y|x)dy<V(x)\enspace\forall\enspace
k,x\text{ and some }\delta>0$. Furthermore, assume that
$\mathcal{K}(\rho_{n},\pi)\leq\sqrt{n}C$ for some constant $C>0$. If the
initial distribution $q^{(0)}$ satisfies $E_{q^{(0)}}[V(X_{0})]<+\infty$, then
the conditions of Corollary 2.1 are satisfied with
$\epsilon_{n}=\mathrm{O}\left(\max(\frac{1}{\sqrt{n}},\frac{n^{\delta/2}}{n})\right)$.

The following Proposition 4.3 shows, the simple linear model satisfies Theorem
4.3 when the parameter $\theta_{0}$ is suitably restricted.

######  Proposition 4.3.

Consider the simple linear model satisfying the equation

(24) $\displaystyle X_{n}$ $\displaystyle=\theta_{0}X_{n-1}+W_{n},$

where $\\{W_{n}\\}$ are i.i.d. standard Gaussian random variables and
$|\theta_{0}|<2^{\frac{1}{4+2\delta}-1}$ for $\delta>0$. Let $\mathcal{F}$ be
the space of all scaled Beta distributions on $(-1,1)$ and suppose the prior
$\pi$ is a uniform distribution on $(-1,1)$. Then, the conditions of Theorem
4.3 are satisfied with
$\epsilon_{n}\in\mathrm{O}\left(\max(\frac{1}{\sqrt{n}},\frac{n^{\delta/2}}{n})\right)$,
if the initial distribution $q^{(0)}$ satisfies
$E_{q^{(0)}}[X_{0}^{4+2\delta}]<+\infty$.

##  5\. Misspecified Models

We shown next how our results can be extended to the misspecified model
setting. Assume that the true data generating distribution is parametrized by
$\theta_{0}\not\in\Theta$. Let
$\theta^{*}_{n}:=\arg\min_{\theta\in\Theta}\mathcal{K}(P^{(n)}_{\theta_{0}},P^{(n)}_{\theta})$
represent the closest parametrized distribution in the variational family to
the data-generating distribution. Further, assume that our usual hypotheses
are satisfied:

  1. (i)

$\int\mathrm{E}[r_{n}(\theta,\theta^{*}_{n})]\rho_{n}(d\theta)\leq
n\epsilon_{n}$,

  2. (ii)

$\int\mathrm{Var}\left(r_{n}(\theta,\theta^{*}_{n})\right)\rho_{n}(d\theta)\leq
n\epsilon_{n}$.

Now, since
$r_{n}(\theta,\theta_{0})=r_{n}(\theta,\theta^{*}_{n})+r_{n}(\theta^{*}_{n},\theta_{0})$,
we have

(25) $\leavevmode\nobreak\
\int\mathcal{K}(P^{(n)}_{\theta_{0}},P^{(n)}_{\theta})\rho_{n}(d\theta)\leq\mathrm{E}[r_{n}(\theta_{0},\theta^{*}_{n})]+n\epsilon_{n}.$

Similarly, decomposing the variance it follows that

(26) $\displaystyle\mathrm{Var}[r_{n}(\theta,\theta_{0})]$
$\displaystyle=\mathrm{Var}[r_{n}(\theta,\theta^{*}_{n})]+\mathrm{Var}[r_{n}(\theta^{*}_{n},\theta_{0})]+2\mathrm{Cov}[r_{n}(\theta,\theta^{*}_{n}),r_{n}(\theta^{*}_{n},\theta_{0})].$
Using the fact that $2ab\leq{a^{2}+b^{2}}$ to the covariance term
$2\mathrm{Cov}[r_{n}(\theta,\theta^{*}_{n}),r_{n}(\theta^{*}_{n},\theta_{0})]=2\mathrm{E}\left[\left(r_{n}(\theta,\theta^{*}_{n})-\mathrm{E}[r_{n}(\theta,\theta^{*}_{n})]\right)\left(r_{n}(\theta^{*}_{n},\theta_{0})-\mathrm{E}[r_{n}(\theta^{*}_{n},\theta_{0})]\right)\right]$,
we have (27) $\displaystyle\mathrm{Var}[r_{n}(\theta,\theta_{0})]$
$\displaystyle\leq
2\mathrm{Var}[r_{n}(\theta,\theta^{*}_{n})]+2\mathrm{Var}[r_{n}(\theta^{*}_{n},\theta_{0})].$
Integrating both sides with respect to $\rho_{n}(d\theta)$ we get
$\displaystyle\int\mathrm{Var}[r_{n}(\theta,\theta_{0})]\rho_{n}(d\theta)$
$\displaystyle\leq
2\int\mathrm{Var}[r_{n}(\theta,\theta^{*}_{n})]\rho_{n}(d\theta)+2\int\mathrm{Var}[r_{n}(\theta^{*}_{n},\theta_{0})]\rho_{n}(d\theta)$
(28) $\displaystyle\leq
2n\epsilon_{n}+2\mathrm{Var}[r_{n}(\theta^{*}_{n},\theta_{0})].\leavevmode\nobreak\
$

Consequently, we arrive at the following result:

######  Theorem 5.1.

Let $\mathcal{F}$ be a subset of all probability distributions parameterized
by $\Theta$. Let
$\theta^{*}_{n}=\arg\min_{\theta\in\Theta}\mathcal{K}(P^{(n)}_{\theta_{0}},P^{(n)}_{\theta})$
and assume there exist $\epsilon_{n}>0$ and $\rho_{n}\in\mathcal{F}$ such that

  1. (i)

$\int\mathrm{E}[r_{n}(\theta,\theta^{*}_{n})]\rho_{n}(d\theta)\leq
n\epsilon_{n}$,

  2. (ii)

$\int\mathrm{Var}\left(r_{n}(\theta,\theta^{*}_{n})\right)\rho_{n}(d\theta)\leq
n\epsilon_{n}$, and

  3. (iii)

$\mathcal{K}(\rho_{n},\pi)\leq n\epsilon_{n}$.

Then, for any $\alpha\in(0,1)$ and $(\epsilon,\eta)\in(0,1)\times(0,1)$,

(29) $\displaystyle\leavevmode\nobreak\ P\left[\int
D_{\alpha}(P^{(n)}_{\theta},P^{(n)}_{\theta_{0}})\tilde{\pi}_{n,\alpha}(d\theta|X^{(n)})\leq\frac{(\alpha+1)n\epsilon_{n}+\mathrm{E}[r_{n}(\theta_{0},\theta^{*}_{n})]+\alpha\sqrt{\frac{2n\epsilon_{n}+2\mathrm{Var}[r_{n}(\theta^{*}_{n},\theta_{0})]}{\eta}}-\log(\epsilon)}{1-\alpha}\right]$
$\displaystyle\geq 1-\epsilon-\eta.$

The proof of this theorem is straightforward and follows from the proof of
Theorem 2.1 by plugging in the upper bounds for KL-divergence from eq. 25, and
variance from eq. 28 to Section C.2. A sketch of the proof is presented in the
appendix.

##  6\. Conclusion

Concentration of the KL-VB model risk, in terms of the expected $\alpha$-Rényi
divergence, is well established under the i.i.d. data generating model
assumption. Here, we extended this to the setting of Markov data generating
models, linking the concentration rate to the mixing and ergodic properties of
the Markov model. Our results apply to both stationary and non-stationary
Markov chains, as well as to the situation with misspecified models. There
remain a number of open questions. An immediate one is to extend the current
analysis to continuous-time Markov chains and Markov jump processes, possibly
using uniformization of the continuous time model. Another direction is to
extend this to the setting of non-homogeneous Markov chains, where analogues
of notions such as stationarity are less straightforward. Further, as noted in
the introduction, [3] establish PAC-Bayes bounds under slightly weaker
‘existence of test functions’ conditions, while our results are established
under the stronger conditions used by [1] for the i.i.d. setting. Weakening
the conditions in our analysis is important, but complicated. A possible path
is to build on results from [4] who provides conditions form the existence of
exponentially powerful test functions exist for distinguishing between two
Markov chains. It is also known that there exists a likelihood ratio test
separating any two ergodic measures [23]. However, leveraging these to
establish the PAC-Bayes bounds for the KL-VB posterior is a challenging effort
that we leave to future papers. Finally it is of interest to generalize our
PAC-bounds to posterior approximations beyond KL-variational inference, such
as $\alpha$-Rényi posterior approximations [19], and loss-calibrated posterior
approximations [18, 14].

##  Appendix A Definitions Related to Markov Chains

As noted before, ergodicity plays an acute role in establishing our results.
We consolidate various definitions used throughout the paper in this appendix.
We assume that the parameterized Markov chains possess an invariant
probability density or mass function $q_{\theta}$ under parameter
$\theta\in\Theta$.

We defined $V$-geometric ergodicity in the previous sections. In this section,
we provide a sufficient condition for a Markov chain to be $V$-geometrically
ergodic. First, we recall the definition of petite sets,

######  Definition A.1 (Petite Sets).

Let $X_{0},\dots,X_{n}$ be $n$ samples from a Markov chain taking values on
the state space $\mathcal{X}$. Let $C$ be a set. We shall call $C$ to be
$v_{q}$ petite if

$\displaystyle K_{q}(x,B)\geq\upsilon_{q}(B)$

for all $x\in C$ and $B\in\mathcal{B(X)}$, and a non-trivial measure
$\upsilon_{q}$ on $\mathcal{B(X)}$

Now, let $\Delta V(x):=E[V(X_{n})|X_{n-1}=x]-V(x)$ for $V:S\to[1,\infty)$.

######  Assumption A.1 (Drift condition).

Suppose the chain $\\{X_{n}\\}$ is, aperiodic and $\psi$-irreducible . Let
there exists a petite set $C$, constants $b<\infty,\beta>0$, and a non-trivial
function $V:S\to[1,\infty)$ satisfying

(30) $\displaystyle\Delta V(x)\leq-\beta V(x)+bI_{x\in C}\enspace\forall x\in
S.$

If a Markov chain drifts towards a petite set then it is $V$-geometrically
ergodic. Suppose, for simplicity, that $V(x)=|X|$. Then, the drift condition
becomes $E[|X_{n}\|X_{x-1}]-|X_{n-1}|=-\beta|X_{n}|+bI_{X_{n}\in C}$. The left
hand side of this equation represents the change in the state of the Markov
chain in one time epoch. Thus, the condition in A.1 essentially states that
the Markov chain drifts towards a petite set $C$ and then, once it reaches
that set, moves to any point in the state space with at least some probability
independent of $C$.

######  Theorem A.1 (Geometrically ergodic theorem).

Suppose that $\\{X_{n}\\}$ is satisfies A.1. Then, the set
$S_{V}=\\{x:V(x)<\infty\\}$ is absorbing, i.e. $P_{\theta}(X_{1}\in
S_{V}|X_{0}=x)=1$ $\forall x\in S_{V}$, and full, i.e. $\psi(S_{V}^{c})=0$.
Also, $\exists\enspace\text{constants }r>1,R<\infty$ such that, for any
$A\in\mathcal{B}(S)$,

(31) $\left\|P_{\theta}(X_{n}\in
A|X_{0}=x)-\int_{A}q_{\theta}(y)dy\right\|_{V}\leq Rr^{-n}V(x).$

Any aperiodic and $\psi$-irreducible Markov chain satisfying the drift
condition is geometrically ergodic. A consequence of Equation 9 is that if,
$\\{X_{n}\\}$ is $V$-geometrically ergodic, then for any other function
$U,\text{ such that }|U|<V$, it is also $U$-geometrically ergodic. In essence,
a geometrically ergodic Markov chain is asymptotically uncorrelated in a
precise sense. Recall $\rho$-mixing coefficients defined as follows. Let
$\mathcal{A}$ be a sigma field and $\mathcal{L}^{2}(A)$ be the set of square
integrable, real valued, $\mathcal{A}$ measurable functions.

######  Definition A.2 ($\rho$-mixing coefficient).

Let $\mathcal{M}_{i}^{j}$ denote the sigma field generated by the measures
$X_{k},\text{ where }i\leq k\leq j$. Then,

(32)
$\rho_{k}=\underset{t>0}{\sup}\underset{(f,g)\in\mathcal{L}^{2}\left(\mathcal{M}_{-\infty}^{t}\right)\times\mathcal{L}^{2}\left(\mathcal{M}_{t+k}^{\infty}\right)}{\sup}\left|\mathrm{Corr}(f,g)\right|,$

where $\mathrm{Corr}$ is the correlation function.

######  Theorem A.2.

If $X_{n}$ is geometrically ergodic, then it is $\alpha$-mixing. That is,
there exists a constant $c>0$ such that $\alpha_{k}\in O(e^{-ck})$.

###### Proof.

By [17, Theorem 2] it follows that a geometrically ergodic Markov chain is
asymptotically uncorrelated with $\rho$-mixing coefficients (see A.2) that
satisfy $\rho_{k}\in O(e^{-ck})$. Furthermore, it is well known that [7, 17]
$\alpha_{k}\leq\frac{1}{4}\rho_{k}$, implying $\alpha_{k}\in O(e^{-ck})$. ∎

##  Appendix B Bounding the KL-divergence between Beta distributions

The following results will be utilized in the proofs of Propositions 4.1, 4.2
and 4.3.

######  Lemma B.1.

Let $\theta_{0}\in(0,1)$. Let, $\rho_{n}$ be a sequence of Beta distributions
with parameters $\alpha_{n}=n\theta_{0}$ and $\beta_{n}=n(1-\theta_{0})$. Let
$\pi$ denote an uniform distribution, $U(0,1)$. Then,
$\mathcal{K}(\rho_{n},\pi)<C+\frac{1}{2}\log(n)$, for some constant $C>0$.

###### Proof.

The KL divergence $\mathcal{K}(\rho_{n},\pi)$ can be written as
$\int\log\left(\frac{\rho_{n}}{\pi}\right)\rho_{n}(d\theta)$. Since $\pi$ is
uniform, $\pi(\theta)=1$ whenever $\theta\in(0,1)$. Hence, the KL-divergence
can be written as the negative of the entropy of $\rho_{n}$
$\int_{0}^{1}\log\left(\rho_{n}\left(\theta\right)\right)\rho_{n}(d\theta),$
which can be written as

(33)
$\displaystyle\mathcal{K}(\rho_{n},\pi)=(\alpha_{n}-1)\psi(\alpha_{n})+(\beta_{n}-1)\psi(\beta_{n})-(\alpha_{n}+\beta_{n}-2)\psi(\alpha_{n}+\beta_{n})-\log\text{Beta}(\alpha_{n},\beta_{n}),$

where $\psi$ is the digamma function. Using Stirling’s approximation on
$\text{Beta}(\alpha_{n},\beta_{n})$ yields,

$\displaystyle\text{Beta}(\alpha_{n},\beta_{n})=\sqrt{2\pi}\frac{\alpha_{n}^{\alpha_{n}-1/2}\beta_{n}^{\beta_{n}-1/2}}{(\alpha_{n}+\beta_{n})^{\alpha_{n}+\beta_{n}-1/2}}(1+o(1)).$

Plugging in the values of $\alpha_{n}$ and $\beta_{n}$, we get,

$\displaystyle\text{Beta}(\alpha_{n},\beta_{n})$
$\displaystyle=\sqrt{2\pi}\frac{(n\theta_{0})^{(n\theta_{0})-1/2}(n(1-\theta_{0}))^{(n(1-\theta_{0}))-1/2}}{(n\theta_{0}+n(1-\theta_{0}))^{n\theta_{0}+n(1-\theta_{0})-1/2}}\left(1+o(1)\right)$
$\displaystyle=\sqrt{2\pi}\frac{n^{n-1}\theta_{0}^{n\theta_{0}-1/2}(1-\theta_{0})^{n(1-\theta_{0})-1/2}}{n^{n-1/2}}(1+o(1))$
$\displaystyle=\sqrt{\frac{2\pi}{n}}\theta_{0}^{n\theta_{0}-1/2}(1-\theta_{0})^{n(1-\theta_{0})-1/2}(1+o(1)).$

Setting $C_{1}=\log(\sqrt{2\pi})$, we have,

$\displaystyle-\log\text{Beta}(\alpha_{n},\beta_{n})$
$\displaystyle<\log(1+o(1))+C_{1}+\frac{1}{2}\log(n)-(n\theta_{0}-1/2)\log(\theta_{0})-(n(1-\theta_{0})-1/2)\log(1-\theta_{0}).$

Now, we analyze the term $(\alpha_{n}-1)\psi(\alpha_{n})$. From [2] we have
that $\log(x)-\frac{1}{x}<\psi(x)<\log(x)-\frac{1}{2x}\ \forall\enspace x>0$.
Without loss of generality, assume $\alpha_{n}>1$, giving

$\displaystyle(\alpha_{n}-1)\psi(\alpha_{n})$
$\displaystyle<(\alpha_{n}-1)\log(\alpha_{n})-\frac{\alpha_{n}-1}{2\alpha_{n}}.$
If not, then we would have obtained using the lower bound of $\psi(x)$,
$\displaystyle(\alpha_{n}-1)\psi(\alpha_{n})$
$\displaystyle<(\alpha_{n}-1)\log(\alpha_{n})-\frac{\alpha_{n}-1}{\alpha_{n}},$
and we could have proceeded similarly. By plugging in the value of
$\alpha_{n}$, we get $\displaystyle(\alpha_{n}-1)\psi(\alpha_{n})$
$\displaystyle<(n\theta_{0}-1)\log(n\theta_{0})-\left(1/2-\frac{1}{2n\theta_{0}}\right)$
$\displaystyle=(n\theta_{0}-1)\log(n)+(n\theta_{0}-1)\log(\theta_{0})-\left(1/2-\frac{1}{2n\theta_{0}}\right).$

Similarly assuming $\beta_{n}>1$, we get the following upper bound for
$(\beta_{n}-1)\psi(\beta_{n})$, giving

$\displaystyle(\beta_{n}-1)\psi(\beta_{n})<(n(1-\theta_{0})-1)\log(n)+(n(1-\theta_{0})-1)\log(1-\theta_{0})-\left(1/2-\frac{1}{2n(1-\theta_{0})}\right)$

Combining all the terms, we get, for
$C^{(n)}_{2}=C_{1}-(1/2-\frac{1}{2n\theta_{0}})-(1/2-\frac{1}{2n(1-\theta_{0})})$

$\displaystyle(\alpha_{n}-1)\psi(\alpha_{n})$
$\displaystyle+(\beta_{n}-1)\psi(\beta_{n})-(\alpha_{n}+\beta_{n}-2)\psi(\alpha_{n}+\beta_{n})-\log\text{Beta}(\alpha_{n},\beta_{n})$
$\displaystyle<C^{(n)}_{2}-\frac{1}{2}(\log(\theta_{0})+\log(1-\theta_{0}))+(n\theta_{0}-1)\log(n)+(n(1-\theta_{0})-1)\log(n)$
$\displaystyle\qquad+\frac{1}{2}\log(n)-(\alpha_{n}+\beta_{n}-2)\psi(\alpha_{n}+\beta_{n})+\log(1+o(1)).$
Now plugging in the values of $\alpha_{n}$ and $\beta_{n}$ in
$(\alpha_{n}+\beta_{n}-1)\psi(\alpha_{n}+\beta_{n})$, we get,
$\displaystyle(\alpha_{n}-1)\psi(\alpha_{n})$
$\displaystyle+(\beta_{n}-1)\psi(\beta_{n})-(\alpha_{n}+\beta_{n}-2)\psi(\alpha_{n}+\beta_{n})-\log\text{Beta}(\alpha_{n},\beta_{n})$
$\displaystyle<C^{(n)}_{2}-\frac{1}{2}(\log(\theta_{0})-\log(1-\theta_{0}))+(n-2)\log(n)+\frac{1}{2}\log(n)-(n-2)\psi(n)$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad+\log(1+o(1)).$

By using the lower bound of $\psi(x)$, we get that,
$-\psi(x)<-\log(x)+\frac{1}{x}$. Plugging this into the above equation, we
get,

$\displaystyle(\alpha_{n}-1)\psi(\alpha_{n})$
$\displaystyle+(\beta_{n}-1)\psi(\beta_{n})-(\alpha_{n}+\beta_{n}-2)\psi(\alpha_{n}+\beta_{n})-\log\text{Beta}(\alpha_{n},\beta_{n})$
$\displaystyle<C^{(n)}_{2}-\frac{1}{2}(\log(\theta_{0})-\log(1-\theta_{0}))+(n-2)\log(n)-(n-2)\log(n)+\frac{1}{2}\log(n)$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad+\frac{n-2}{n}+\log(1+o(1))$
$\displaystyle=C^{(n)}_{2}-\frac{1}{2}(\log(\theta_{0})-\log(1-\theta_{0}))+\frac{1}{2}\log(n)+\frac{n-2}{n}+\log(1+o(1)).$
Since $\frac{1}{2n\theta_{0}}+\frac{1}{2n(1-\theta_{0})})<2$, $C^{(2)}_{n}$
can be upper bounded by $C_{1}+1$. Using this fact, we get
$\displaystyle(\alpha_{n}-1)\psi(\alpha_{n})$
$\displaystyle+(\beta_{n}-1)\psi(\beta_{n})-(\alpha_{n}+\beta_{n}-2)\psi(\alpha_{n}+\beta_{n})-\log\text{Beta}(\alpha_{n},\beta_{n})<C+\frac{1}{2}\log(n),$

for some large constant $C$. ∎

######  Proposition B.1.

Let $\theta_{0}\in(0,1)$. Let, $\rho_{n}$ be a sequence of Beta distributions
with parameters $\alpha_{n}=n\theta_{0}$ and $\beta_{n}=n(1-\theta_{0})$. Let
$\pi$ denote an Beta distribution, with parameters $(\alpha,\beta)$. Then,
$\mathcal{K}(\rho_{n},\pi)<C+\frac{1}{2}\log(n)$, for some constant $C>0$.

###### Proof.

The KL-divergence between $\rho_{n}$ and $\pi$ can be written as,

$\displaystyle\mathcal{K}(\rho_{n},\pi)=$
$\displaystyle\int\log\left(\frac{\rho_{n}}{\pi}\right)\rho_{n}(d\theta)=\int\log\left(\frac{\rho_{n}}{U}\right)\rho_{n}(d\theta)+\int\log\left(\frac{U}{\pi}\right)\rho_{n}(d\theta),$

where, $U$ is an uniform distribution on $(0,1)$. We analyze the second term
in the above expression. The second term can be written as,

$\displaystyle\int\log\left(\frac{U}{\pi}\right)\rho_{n}(d\theta)$
$\displaystyle=\int\log\left(\frac{1}{\frac{1}{\text{Beta}(\alpha,\beta)}\theta^{\alpha-1}(1-\theta)^{\beta-1}}\right)\rho_{n}(d\theta)$
$\displaystyle=C_{1}-(\alpha-1)\int\log(\theta)\rho_{n}(d\theta)-(\beta-1)\int\log(1-\theta)\rho_{n}(d\theta),$
where $C_{1}$ is $\log(\text{Beta}(\alpha,\beta))$. Since, $\rho_{n}$ follows
a Beta distribution with parameters $\alpha_{n}=n\theta_{0}$ and
$\beta_{n}=n(1-\theta_{0})$, we get that,
$\displaystyle\int\log\left(\frac{U}{\pi}\right)\rho_{n}(d\theta)$
$\displaystyle=C_{1}-(\alpha-1)\left[\psi(\alpha_{n})-\psi(\alpha_{n}+\beta_{n})\right]-(\beta-1)\left[\psi(\beta_{n})-\psi(\alpha_{n}+\beta_{n})\right]$

Since, $\log(x)-\frac{1}{x}<\psi(x)<\log(x)-\frac{1}{2x}$, looking at the term
$\left[\psi(\alpha_{n})-\psi(\alpha_{n}+\beta_{n})\right]$, we get that,

$\displaystyle\left[\psi(\alpha_{n})-\psi(\alpha_{n}+\beta_{n})\right]$
$\displaystyle=\left[\psi(n\theta_{0})-\psi(n\theta_{0}+n(1-\theta_{0}))\right]$
$\displaystyle=\left[\psi(n\theta_{0})-\psi(n)\right].$ Using the upper bound
on $\psi(n\theta_{0})$ and the lower bound on $\psi(n)$, we get
$\displaystyle\left[\psi(n\theta_{0})-\psi(n)\right]$
$\displaystyle<\log(n\theta_{0})-\frac{1}{2n\theta_{0}}-\log(n)+\frac{1}{n\theta_{0}}$
$\displaystyle=\log(\theta_{0})+\frac{1}{2n\theta_{0}}.$ We can also get a
lower bound very similarly.
$\displaystyle\left[\psi(\alpha_{n})-\psi(\alpha_{n}+\beta_{n})\right]$
$\displaystyle>\log(\theta_{0})-\frac{1}{2n\theta_{0}}.$

Therefore it follows that

(34)
$\log(\theta_{0})-\frac{1}{2n\theta_{0}}<\left[\psi(\alpha_{n})-\psi(\alpha_{n}+\beta_{n})\right]<\log(\theta_{0})+\frac{1}{2n\theta_{0}}.$

Similarly, we have

(35)
$\log(1-\theta_{0})-\frac{1}{2n(1-\theta_{0})}<\left[\psi(\beta_{n})-\psi(\alpha_{n}+\beta_{n})\right]<\log(1-\theta_{0})+\frac{1}{2n(1-\theta_{0})}.$

Consequently, for a large enough constant $C_{2}>0$ it follows that

$\displaystyle-
C_{2}<\left[\psi(\alpha_{n})-\psi(\alpha_{n}+\beta_{n})\right]<C_{2},$

and

$\displaystyle-
C_{2}<\left[\psi(\beta_{n})-\psi(\alpha_{n}+\beta_{n})\right]<C_{2}.$

Without loss of generality assume that $\min\\{\alpha-1,\beta-1\\}>0$. Then we
get,

$\displaystyle-(\alpha-1)C_{2}<(\alpha-1)\left[\psi(\alpha_{n})-\psi(\alpha_{n}+\beta_{n})\right]<(\alpha-1)C_{2},$

and

$\displaystyle-(\alpha-1)C_{2}<(\alpha-1)\left[\psi(\beta_{n})-\psi(\alpha_{n}+\beta_{n})\right]<(\alpha-1)C_{2}.$

If, either of $\alpha-1$ or $\beta-1$ was negative, then the direction of
inequality on the previous equation would have reversed. However, due to the
symmetric nature of the inequality, that would not have made a difference.
Using the above bounds we finally show that,

$\displaystyle
C_{1}-(\alpha-1)\left[\psi(\alpha_{n})-\psi(\alpha_{n}+\beta_{n})\right]-(\beta-1)\left[\psi(\beta_{n})-\psi(\alpha_{n}+\beta_{n})\right]<C_{1}+C_{2}\theta_{0}+C_{2}(1-\theta_{0})<C,$

for some large constant C. Finally, we upper bound
$\int\log\left(\frac{\rho_{n}}{U}\right)\rho_{n}(d\theta)$ by Lemma B.1
thereby completing the proof. ∎

##  Appendix C Proofs of Main Results

###  C.1. Proposition 2.1

We start by recalling the variational formula of Donsker and Varadhan [9].

######  Lemma C.1 (Donsker-Varadhan).

For any probability distribution function $\pi$ on $\Theta$, and for any
measurable function $h:\Theta\rightarrow\mathbb{R}$, if $\int
e^{h}d\pi<\infty$, then

(36) $\displaystyle\log\int e^{h}d\pi$
$\displaystyle=\underset{\rho\in\mathcal{M}^{+}(\Theta)}{\sup}\left\\{\int
hd\rho-\mathcal{K}(\rho,\pi)\right\\}$

###### Proof of Prop. 2.1.

Fix $\alpha\in(0,1)$, and $\theta\in\Theta$. First, observe that by the
definition of the $\alpha$-Rényi divergence we have

$\displaystyle\mathrm{E}^{(n)}_{\theta_{0}}[\exp(-\alpha
r_{n}(\theta,\theta_{0}))]=\exp[-(1-\alpha)D_{\alpha}(P^{(n)}_{\theta},P^{(n)}_{\theta_{0}})]$
Multiplying both sides of the equation by
$\exp[(1-\alpha)D_{\alpha}(P^{(n)}_{\theta},P^{(n)}_{\theta_{0}})$ and
integrating with respect to (w.r.t.) $\pi(\theta)$ it follows that
$\displaystyle\int\mathrm{E}^{(n)}_{\theta_{0}}\left[\exp\left(-\alpha
r_{n}(\theta,\theta_{0})+(1-\alpha)D_{\alpha}(P^{(n)}_{\theta},P^{(n)}_{\theta_{0}})\right)\right]\pi(d\theta)=1,\text{or}$
$\displaystyle\mathrm{E}^{(n)}_{\theta_{0}}\left[\int\exp\left(-\alpha
r_{n}(\theta,\theta_{0})+(1-\alpha)D_{\alpha}(P^{(n)}_{\theta},P^{(n)}_{\theta_{0}})\right)\pi(d\theta)\right]=1.$

Define $h(\theta):=-\alpha
r_{n}(\theta,\theta_{0})+(1-\alpha)D_{\alpha}(P^{(n)}_{\theta},P^{(n)}_{\theta_{0}})$.
Then, applying Lemma C.1 to the integrand on the left hand side (l.h.s.)
above, it follows that

$\displaystyle\mathrm{E}^{(n)}_{\theta_{0}}\left[\exp\left(\underset{\rho\in\mathcal{M}^{+}(\Theta)}{\sup}\left[\int
h(\theta)\rho(d\theta)-\mathcal{K}(\rho,\pi)\right]\right)\right]=1.$

Multiply both sides of this equation by $\epsilon>0$ to obtain

$\displaystyle\mathrm{E}^{(n)}_{\theta_{0}}\left[\exp\left(\underset{\rho\in\mathcal{M}^{+}(\Theta)}{\sup}\left[\int
h(\theta)\rho(d\theta)-\mathcal{K}(\rho,\pi)+\log(\epsilon)\right]\right)\right]=\epsilon.$

Now, by Markov’s inequality, we have

(37)
${P^{(n)}_{\theta_{0}}}\bigg{[}\underset{\rho\in\mathcal{M}^{+}(\Theta)}{\sup}\int(-\alpha
r_{n}(\theta,\theta_{0})+(1-\alpha)D_{\alpha}(P^{(n)}_{\theta},P^{(n)}_{\theta_{0}}))\rho(d\theta)-\mathcal{K}(\rho,\pi)+\log(\epsilon)\geq
0\bigg{]}\leq\epsilon.$

Thus, it follows via complementation that

$\displaystyle{P^{(n)}_{\theta_{0}}}\bigg{[}\forall\rho\in\mathcal{F}(\Theta)\int
D_{\alpha}(P^{(n)}_{\theta},P^{(n)}_{\theta_{0}})\rho(d\theta)\leq\frac{\alpha}{(1-\alpha)}\int
r_{n}(\theta,\theta_{0})\rho(d\theta)+\frac{\mathcal{K}(\rho,\pi)-\log(\epsilon)}{1-\alpha}\bigg{]}$
$\displaystyle\geq 1-\epsilon,$

thereby completing the proof. ∎

###  C.2. Theorem 2.1:

###### Proof of Theorem 2.1.

Recall the definition of the fractional posterior and the VB approximation,

$\displaystyle\pi_{n,\alpha|X^{n}}=\frac{\exp^{-\alpha
r_{n}(\theta,\theta_{0})(X^{n})}\pi(d\theta)}{\int\exp^{-\alpha
r_{n}(\gamma,\theta_{0})(X^{n})}\pi(d\gamma)},\leavevmode\nobreak\
\tilde{\pi}_{n,\alpha|X^{n}}=\underset{\mathcal{\rho\in
F}}{\arg\min}\leavevmode\nobreak\ \mathcal{K}(\rho,\pi_{n,\alpha|X^{(n)}}).$

It follows by definition of the KL divergence that

(38) $\displaystyle\tilde{\pi}_{n,\alpha|X^{n}}$
$\displaystyle=\underset{\mathcal{\rho\in F}}{\arg\min}\left\\{-\alpha\int
r_{n}(\theta,\theta_{0})\rho(d\theta)+\mathcal{K}(\rho,\pi)\right\\},$

where $\pi$ is the prior distribution. Following Proposition 2.1 it follows
that for any $\epsilon>0$

$\int
D_{\alpha}(P^{(n)}_{\theta},P^{(n)}_{\theta_{0}}){\tilde{\pi}(d\theta|X^{n})}\leq\frac{\alpha}{(1-\alpha)}\int
r_{n}(\theta,\theta_{0})\rho(d\theta)+\frac{\mathcal{K}(\rho,\pi)-\log(\epsilon)}{1-\alpha},$

with probability $1-\epsilon$. We fix an $\eta\in(0,1)$. Using Chebychev’s
inequality, we have

$\displaystyle P_{\theta_{0}}^{(n)}\left[\frac{\alpha}{1-\alpha}\int
r_{n}(\theta,\theta_{0})\rho_{n}(d\theta)\geq\frac{\alpha}{1-\alpha}\int\mathrm{E}[r_{n}(\theta,\theta_{0})]\rho_{n}(d\theta)+\frac{\alpha}{1-\alpha}\sqrt{\frac{\mathrm{Var}[\int
r_{n}(\theta,\theta_{0})\rho_{n}(d\theta)]}{\eta}}+\frac{\mathcal{K}(\rho_{n},\pi)}{1-\alpha}\right]$
$\displaystyle=P_{\theta_{0}}^{(n)}\left[\frac{\alpha}{1-\alpha}\int
r_{n}(\theta,\theta_{0})\rho_{n}(d\theta)-\frac{\alpha}{1-\alpha}\int\mathrm{E}[r_{n}(\theta,\theta_{0})]\rho_{n}(d\theta)-\frac{\mathcal{K}(\rho_{n},\pi)}{1-\alpha}\geq\frac{\alpha}{1-\alpha}\sqrt{\frac{\mathrm{Var}[\int
r_{n}(\theta,\theta_{0})\rho_{n}(d\theta)]}{\eta}}\right]$
$\displaystyle\leq\frac{\mathrm{Var}\left[\frac{\alpha}{1-\alpha}\int
r_{n}(\theta,\theta_{0})\rho_{n}(d\theta)-\frac{\alpha}{1-\alpha}\int\mathrm{E}[r_{n}(\theta,\theta_{0})]\rho_{n}(d\theta)-\frac{\mathcal{K}(\rho_{n},\pi)}{1-\alpha}\right]}{\frac{\alpha^{2}}{(1-\alpha)^{2}}\frac{\mathrm{Var}[\int
r_{n}(\theta,\theta_{0})\rho_{n}(d\theta)]}{\eta}}.$

Note that $\frac{\alpha}{1-\alpha}\int
E(r_{n}(\theta,\theta_{0}))\rho_{n}(d\theta)$ and
$\frac{\mathcal{K}(\rho_{n},\pi)}{1-\alpha}$ are constants with respect to the
data, implying

$\displaystyle\mathrm{Var}\bigg{[}\frac{\alpha}{1-\alpha}$ $\displaystyle\int
r_{n}(\theta,\theta_{0})\rho_{n}(d\theta)-\frac{\alpha}{1-\alpha}\int\mathrm{E}[r_{n}(\theta,\theta_{0})]\rho_{n}(d\theta)-\frac{\mathcal{K}(\rho_{n},\pi)}{1-\alpha}\bigg{]}$
$\displaystyle\qquad=\frac{\alpha^{2}}{(1-\alpha)^{2}}{\mathrm{Var}\left[\int
r_{n}(\theta,\theta_{0})\rho_{n}(d\theta)\right]}.$

Therefore, we have

$\displaystyle P_{\theta_{0}}^{(n)}\bigg{[}\frac{\alpha}{1-\alpha}\int
r_{n}(\theta,\theta_{0})\rho_{n}(d\theta)\geq\frac{\alpha}{1-\alpha}$
$\displaystyle\int\mathrm{E}[r_{n}(\theta,\theta_{0})]\rho_{n}(d\theta)$
$\displaystyle+\frac{\alpha}{1-\alpha}\sqrt{\frac{\mathrm{Var}[\int
r_{n}(\theta,\theta_{0})\rho_{n}(d\theta)]}{\eta}}+\frac{\mathcal{K}(\rho_{n},\pi)}{1-\alpha}\bigg{]}\leq\eta.$

From Proposition 2.1, with probability $1-\epsilon$ the following holds

$\int
D_{\alpha}(P^{(n)}_{\theta},P^{(n)}_{\theta_{0}})\tilde{\pi}_{n,\alpha|X^{n}}(d\theta)\leq\frac{\alpha\int
r_{n}(\theta,\theta_{0})\rho_{n}(d\theta)+\mathcal{K}(\rho_{n},\pi)-\log(\epsilon)}{1-\alpha}.$

Therefore, with probability $1-\eta-\epsilon$ the following statement holds

$\displaystyle\leavevmode\nobreak\ \int
D_{\alpha}(P^{(n)}_{\theta},P^{(n)}_{\theta_{0}})\tilde{\pi}_{n,\alpha|X^{n}}(d\theta)$
$\displaystyle\leq\frac{\alpha}{1-\alpha}\int\mathcal{K}(P^{(n)}_{\theta_{0}},P^{(n)}_{\theta})\rho_{n}(d\theta)+\frac{\alpha}{1-\alpha}\sqrt{\frac{\text{Var}[\int
r_{n}(\theta,\theta_{0})\rho_{n}(d\theta)]}{\eta}}$ (39)
$\displaystyle\qquad\qquad+\frac{\mathcal{K}(\rho_{n},\pi)-\log(\epsilon)}{1-\alpha}.$

Next, observe that

$\displaystyle\text{Var}\left[\int
r_{n}(\theta,\theta_{0})\rho_{n}(d\theta)\right]=E_{\theta_{0}}^{(n)}\left[\left|\int
r_{n}(\theta,\theta_{0})\rho_{n}(d\theta)-E\left[\int
r_{n}(\theta,\theta_{0})\rho_{n}(d\theta)\right]\right|^{2}\right]\leq\int\text{Var}[r_{n}(\theta,\theta_{0})]\rho_{n}(d\theta),$

by a straightforward application of Jensen’s inequality to the inner integral
on the left hand side. Finally, following the hypotheses (i), (ii) and (iii),
we have,

$\displaystyle\int
D_{\alpha}(P^{(n)}_{\theta},P^{(n)}_{\theta_{0}})\tilde{\pi}_{n,\alpha|X^{n}}(d\theta)$
$\displaystyle\leq\frac{\alpha}{1-\alpha}\int\bigg{(}\mathcal{K}(P^{(n)}_{\theta_{0}},P^{(n)}_{\theta})+\sqrt{\frac{\int\mathrm{Var}[r_{n}(\theta,\theta_{0})]\rho_{n}(d\theta)}{\eta}}\bigg{)}\rho_{n}(d\theta)$
$\displaystyle\qquad+\frac{1}{\alpha}\left(\mathcal{K}(\rho_{n},\pi)-\log(\epsilon)\right)$
$\displaystyle\leq\frac{\alpha(\epsilon_{n}+\sqrt{\frac{n\epsilon_{n}}{\eta}})}{1-\alpha}+\frac{n\epsilon_{n}-\log(\epsilon)}{1-\alpha},$

thereby concluding the proof. ∎

Lemma 2 :

###  C.3. Proposition 2.2

###### Proof of Proposition 2.2.

We define
$Y_{i}:=\log\left(\frac{p_{\theta_{1}}(X_{i}|X_{i-1})}{p_{\theta_{2}}(X_{i}|X_{i-1})}\right)$
for $i=1,\ldots,n$, and
$Z_{0}=\log\bigg{(}\frac{q^{(0)}_{1}(X_{0})}{q^{(0)}_{2}(X_{0})}\bigg{)}$.
Then, using the Markov property we can see that the Kullback-Leibler
divergence between the joint distributions $P_{\theta_{1}}^{(n)}$ and
$P_{\theta_{2}}^{(n)}$ satisfies
$\mathcal{K}\left(P_{\theta_{1}}^{(n)},P_{\theta_{2}}^{(n)}\right)=\sum_{i=1}^{n}\mathrm{E}_{\theta_{1}}\left[Y_{i}\right]+\mathrm{E}_{\theta_{1}}[Z_{0}].$
If the Markov chain $\\{X_{i}\\}$ is stationary under $\theta_{1}$, so is
$\\{Y_{i}\\}$. Hence $Y_{i}\overset{d}{=}Y_{1}$ and the above equation reduces
to,

(40)
$\displaystyle\mathcal{K}\left(P_{\theta_{1}}^{(n)},P_{\theta_{2}}^{(n)}\right)=n\mathrm{E}_{\theta_{1}}\left[Y_{1}\right]+\mathrm{E}_{\theta_{1}}[Z_{0}].$

∎

###  C.4. Proposition 2.3

First, recall the following result from [13].

######  Lemma C.2.

[13, Lemma 1.2] Let $X_{-\infty},\dots,X_{1},X_{2},\dots$ be an alpha mixing
Markov chain with alpha mixing coefficients given by $\alpha_{k}$. Let
$\mathcal{M}_{a}^{b}$ be the sigma-field generated by the subsequence
$(X_{a},X_{a+1},\dots,X_{b})$. Let $\eta_{t}\in\mathcal{M}_{-\infty}^{t}$ and
$\tau_{t}\in\mathcal{M}_{t+k}^{\infty}$ be adapted random variables such that
$|\eta_{t}|\leq 1,|\tau_{t}|\leq 1$. Then,

(41)
$\displaystyle\underset{t}{\sup}\underset{\eta_{t},\tau_{t}}{\sup}|\mathrm{E}[\eta_{t}\tau_{t}]-\mathrm{E}[\eta_{t}]\mathrm{E}[\tau_{t}]|\leq
4\alpha_{k}.$

This lemma provides an upper bound on the covariance of events $\eta\text{ and
}\tau$, as shown next.

######  Lemma C.3.

Let $\eta\in\mathcal{M}_{-\infty}^{t}$ $\tau\in\mathcal{M}_{t+k}^{\infty}$ be
such that, $E|\eta|^{2+\delta}\leq C_{1},E|\tau|^{2+\delta}\leq C_{2}\text{
for some }\delta>0$. Then, for a fixed $n<+\infty$, we have

(42)
$|\mathrm{E}\eta\tau-\mathrm{E}\eta\mathrm{E}\tau|\leq\left(\frac{4}{n}+2n^{\delta/2}(C_{1}+C_{2})+2n^{\delta/2}\sqrt{C_{1}C_{2}}\right)\alpha_{k}^{2\delta/(2+\delta)}.$

###### Proof.

Let $N<+\infty$ be a fixed number. We get from the triangle inequality that

(43) $\displaystyle|\mathrm{E}\eta\tau-\mathrm{E}\eta\mathrm{E}\tau|$
$\displaystyle\leq|\mathrm{E}\eta\tau I_{[|\eta|\leq N,|\tau|\leq
N]}-\mathrm{E}\eta I_{[|\eta|\leq N]}\mathrm{E}\tau I_{[|\tau|\leq N]}|$
$\displaystyle\qquad+|\mathrm{E}\eta\tau I_{[|\eta|\geq N,|\tau|\leq
N]}-\mathrm{E}\eta I_{[|\eta|\geq N]}\mathrm{E}\tau I_{[|\tau|\leq N]}|$
$\displaystyle\qquad+|\mathrm{E}\eta\tau I_{[|\eta|\leq N,|\tau|\geq
N]}-\mathrm{E}\eta I_{[|\eta|\leq N]}\mathrm{E}\tau I_{[|\tau|\geq N]}|$
$\displaystyle\qquad+|\mathrm{E}\eta\tau I_{[|\eta|\geq N,|\tau|\geq
N]}-\mathrm{E}\eta I_{[|\eta|\geq N]}\mathrm{E}\tau I_{[|\tau|\geq N]}|.$
Multiplying and dividing the first term by $N^{2}$ and applying Lemma C.2, we
get $|\mathrm{E}\eta\tau I_{[|\eta|\leq N,|\tau|\leq N]}-\mathrm{E}\eta
I_{[|\eta|\leq N]}\mathrm{E}\tau I_{[|\tau|\leq N]}|\leq 4N^{2}\alpha_{k}$.
For the second term, if $|\tau|\leq N$, then $\tau\leq N$ and $\tau\geq-N$.
Plugging this in the second term we get, (44)
$\displaystyle|\mathrm{E}\eta\tau I_{[|\eta|\geq N,|\tau|\leq N]}-$
$\displaystyle\mathrm{E}\eta I_{[|\eta|\geq N]}\mathrm{E}\tau I_{[|\tau|\leq
N]}|\leq\left|N\mathrm{E}\eta I_{[|\eta|\geq N}+N\left[\mathrm{E}\eta
I_{[|\eta|\geq N]}\right]\right|$ (45) $\displaystyle=2N|\mathrm{E}\eta
I_{[|\eta|\geq N]}|.$ Since $|\eta|\geq N$, we have
$1\leq\frac{|\eta|^{1+\delta}}{N^{1+\delta}}$. Following this, (46)
$\displaystyle|2N\mathrm{E}\eta I_{[|\eta|\geq N]}|$ $\displaystyle\leq
2N\left|\mathrm{E}\left[\frac{|\eta|^{2+\delta}}{N^{1+\delta}}I_{[|\eta|\geq
N]}\right]\right|$ (47) $\displaystyle\leq
2N\frac{1}{N^{1+\delta}}|\mathrm{E}\eta^{2+\delta}|\leq
2\frac{C_{1}}{N^{\delta}}.$

Similarly, we can also write for the third term, $|\mathrm{E}\eta\tau
I_{[|\eta|\leq N,|\tau|\geq N]}-\mathrm{E}\eta I_{[|\eta|\leq
N]}\mathrm{E}\tau I_{[|\tau|\geq N]}|\leq 2\frac{C_{2}}{N^{\delta}}$. Finally,
for the last term we get that by Cauchy-Schwarz inequality,

(48) $\displaystyle|\mathrm{E}\eta\tau I_{[|\eta|\geq N,|\tau|\geq
N]}-\mathrm{E}\eta I_{[|\eta|\geq N]}\mathrm{E}\tau I_{[|\tau|\geq N]}|$
$\displaystyle\leq\sqrt{\mathrm{Var}\left[\eta I_{[|\eta|\geq
N]}\right]\mathrm{Var}\left[\tau I_{[|\tau|\geq N]}\right]}$ (49)
$\displaystyle<2\sqrt{\mathrm{Var}\left[\eta I_{[|\eta|\geq
N]}\right]\mathrm{Var}\left[\tau I_{[|\tau|\geq N]}\right]}$ (50)
$\displaystyle\leq 2\sqrt{\mathrm{E}\left[\eta^{2}I_{[|\eta|\geq
N]}\right]\mathrm{E}\left[\tau^{2}I_{[|\tau|\geq N]}\right]}.$

Since $|\eta|>N$, $1<\frac{|\eta|^{\delta}}{N^{\delta}}$. Similarly,
$1<\frac{|\tau|^{\delta}}{N^{\delta}}$. Plugging these in the previous
equation, we get,

(51) $\displaystyle\sqrt{\mathrm{E}\left[\eta^{2}I_{[|\eta|\geq
N]}\right]\mathrm{E}\left[\tau^{2}I_{[|\tau|\geq N]}\right]}$
$\displaystyle\leq\sqrt{\frac{1}{N^{2\delta}}\mathrm{E}\left[|\eta|^{2+\delta}I_{[|\eta|\geq
N]}\right]\mathrm{E}\left[|\tau|^{2+\delta}I_{[|\tau|\geq N]}\right]}$ (52)
$\displaystyle\leq\frac{1}{N^{\delta}}\sqrt{C_{1}C_{2}}.$

Combining the four upper bounds above, we get,

(53) $\displaystyle|\mathrm{E}\eta\tau-\mathrm{E}\eta\mathrm{E}\tau|$
$\displaystyle\leq
4N^{2}\alpha_{k}+\frac{2}{N^{\delta}}(C_{1}+C_{2})+\frac{2}{N^{\delta}}\sqrt{C_{1}C_{2}}.$

Now, in particular, setting $N=n^{-1/2}\alpha_{k}^{-1/(2+\delta)}$ it follows
that

(54) $\displaystyle|\mathrm{E}\eta\tau-\mathrm{E}\eta\mathrm{E}\tau|$
$\displaystyle\leq\frac{4}{n}\alpha_{k}^{\delta/(2+\delta)}+2n^{\delta/2}\alpha_{k}^{\delta/(2+\delta)}(C_{1}+C_{2})+2n^{\delta/2}\alpha_{k}^{\delta/(2+\delta)}\sqrt{C_{1}C_{2}}$
(55)
$\displaystyle=\bigg{(}\frac{4}{n}+2n^{\delta/2}(C_{1}+C_{2})+2n^{\delta/2}\sqrt{C_{1}C_{2}}\bigg{)}\alpha_{k}^{\delta/(2+\delta)}.$

∎

######  Lemma C.4.

Let $\\{X_{t}\\}$ be an alpha mixing Markov chain with mixing coefficient
$\alpha_{k}$. Further assume that $\mathrm{E}|X_{t}|^{2+\delta}\leq
C_{1}\text{ and }\mathrm{E}|X_{t+k}|^{2+\delta}\leq C_{2}$ for some
$\delta>0$. Then, for any $t$ and any $n>0$

(56)
$|\mathrm{Cov}(X_{t},X_{t+k})|\leq\bigg{(}\frac{4}{n}+2n^{\delta/2}(C_{1}+C_{2})+2n^{\delta/2}\sqrt{C_{1}C_{2}}\bigg{)}\alpha_{k}^{\delta/(2+\delta)}.$

###### Proof.

Set $\eta=X_{t},\tau=X_{t+k}$ in Lemma C.3. ∎

###### Proof of Proposition 2.3.

Let $\\{X_{t}\\}$ be a stationary alpha-mixing Markov chain under $\theta_{1}$
with mixing coefficients $\\{\alpha_{k}\\}$. Observe that the log-likelihood
can be expressed as

$\displaystyle r_{n}(\theta_{2},\theta_{1})$
$\displaystyle=\underset{i=1}{\sum^{n}}\log\bigg{(}\frac{p_{\theta_{1}}(X_{i}|X_{i-1})}{p_{\theta_{2}}(X_{i}|X_{i-1})}\bigg{)}+\log\bigg{(}\frac{q^{(0)}_{1}(X_{0})}{q^{(0)}_{2}(X_{0})}\bigg{)}$
$\displaystyle\equiv\underset{i=1}{\sum^{n}}Y_{i}+Z_{0}.$

Therefore, the variance of the log-likelihood ratio is simply

$\displaystyle\mathrm{Var}_{\theta_{1}}\left[r_{n}(\theta_{2},\theta_{1})\right]$
$\displaystyle=\mathrm{Var}_{\theta_{1}}\left[\underset{i=1}{\sum^{n}}Y_{i}+Z_{0}\right]$
$\displaystyle=\underset{i,j=1}{\sum^{n}}\mathrm{Cov}_{\theta_{1}}(Y_{i},Y_{j})+\underset{i=1}{\sum^{n}}\mathrm{Cov}_{\theta_{1}}(Y_{i},Z_{0})+\mathrm{Cov}_{\theta_{1}}(Z_{0},Z_{0}).$

Now, using Lemma C.4 we have

$\displaystyle|\mathrm{Cov}_{\theta_{1}}(Y_{i},Y_{j})|$
$\displaystyle=|\mathrm{E}_{\theta_{1}}Y_{i}Y_{j}-\mathrm{E}_{\theta_{1}}Y_{i}\mathrm{E}_{\theta_{1}}Y_{j}|$
$\displaystyle<\left(\frac{4}{n}+2n^{\delta/2}(\mathrm{E}_{\theta_{1}}|Y_{i}|^{2+\delta}+\mathrm{E}_{\theta_{1}}|Y_{j}|^{2+\delta}+\sqrt{\mathrm{E}_{\theta_{1}}|Y_{i}|^{2+\delta}\mathrm{E}_{\theta_{1}}|Y_{j}|^{2+\delta}})\right)\alpha_{|j-i|-1}^{\delta/(2+\delta)}$
$\displaystyle=\left(\frac{4}{n}+2n^{\delta/2}(C_{\theta_{1},\theta_{2}}^{(i)}+C_{\theta_{1},\theta_{2}}^{(j)}+\sqrt{C_{\theta_{1},\theta_{2}}^{(i)}C_{\theta_{1},\theta_{2}}^{(j)}})\right)\alpha_{|j-i|-1}^{\delta/(2+\delta)}.$
Similarly, as above we can also say
$\displaystyle|\mathrm{Cov}_{\theta_{1}}(Y_{i},Z_{0})|<$
$\displaystyle\left(\frac{4}{n}+2n^{\delta/2}(C_{\theta_{1},\theta_{2}}^{(i)}+D_{1,2}+\sqrt{C_{\theta_{1},\theta_{2}}^{(i)}D_{1,2}})\right)\left(\alpha_{i-1}^{\delta/(2+\delta)}\right)$

Combining, the two upper bounds above, we get the first result:

$\displaystyle\mathrm{Var}_{\theta_{1}}\bigg{[}r_{n}(\theta_{2},\theta_{1})\bigg{]}$
$\displaystyle<\sum_{i,j=1}^{n}\left(\frac{4}{n}+2n^{\delta/2}(C_{\theta_{1},\theta_{2}}^{(i)}+C_{\theta_{1},\theta_{2}}^{(j)}+2\sqrt{C_{\theta_{1},\theta_{2}}^{(i)}C_{\theta_{1},\theta_{2}}^{(j)}})\right)\left(\alpha_{|i-j|-1}^{\delta/(2+\delta)}\right)$
$\displaystyle\qquad+\sum_{i=1}^{n}\left(\frac{4}{n^{2}}+2n^{\delta/2}(C_{\theta_{1},\theta_{2}}^{(i)}+D_{1,2}+\sqrt{C_{\theta_{1},\theta_{2}}^{(i)}D_{1,2}})\right)\left(\alpha_{i-1}^{\delta/(2+\delta)}\right)+\mathrm{Var}[Z_{0},Z_{0}].$

If $\\{X_{i}\\}$ is stationary under $\theta_{1}$, so is $\\{Y_{i}\\}$.
Therefore,
$\mathrm{E}_{\theta_{1}}|Y_{i}|^{2+\delta}=\mathrm{E}_{\theta_{1}}|Y_{1}|^{2+\delta}=C_{\theta_{1},\theta_{2}}^{(1)}\enspace\forall\enspace
i$, and

$\displaystyle\underset{i,j=1}{\sum^{n}}\mathrm{Cov}_{\theta_{1}}(Y_{i},Y_{j})$
$\displaystyle\leq\underset{i,j=1}{\sum^{n}}\left(\frac{4}{n}+6n^{\delta/2}C_{\theta_{1},\theta_{2}}^{(1)}\right)\alpha_{|j-i|-1}^{\delta/(2+\delta)}$
(57) $\displaystyle\leq
n\,\left(\frac{4}{n}+6n^{\delta/2}C_{\theta_{1},\theta_{2}}^{(1)}\right)\left(\underset{h\geq
1}{\sum}\alpha_{h-1}^{\delta/(2+\delta)}\right).$

Again, using Lemma C.4 on $\mathrm{Cov}_{\theta_{1}}(Y_{i},Z_{0})$, yields

(58)
$\underset{i=1}{\sum^{n}}\mathrm{Cov}_{\theta_{1}}(Y_{i},Z_{0})\leq\left(\frac{4}{n}+2n^{\delta/2}(C_{\theta}+D_{1,2}+\sqrt{C_{\theta}D_{1,2}})\right)\left(\sum_{h\geq
1}\alpha_{h}^{\delta/(2+\delta)}\right).$

Finally, using eq. 57 and eq. 58 we have

$\displaystyle\mathrm{Var}_{\theta_{1}}\left[r_{n}(\theta_{2},\theta_{1})\right]$
$\displaystyle\leq
n\left(\frac{4}{n}+6n^{\delta/2}C_{\theta_{1},\theta_{2}}^{(1)}\right)\left(\sum_{h\geq
1}\alpha_{h-1}^{\delta/(2+\delta)}\right)+$
$\displaystyle\left(\frac{4}{n}+2n^{\delta/2}(C_{\theta_{1},\theta_{2}}^{(1)}+D_{1,2}+\sqrt{C_{\theta_{1},\theta_{2}}^{(1)}D_{1,2}})\right)\left(\sum_{h\geq
1}\alpha_{h}^{\delta/(2+\delta)}\right)+\mathrm{Cov}_{\theta_{1}}(Z_{0},Z_{0}).$

∎

######  Lemma C.5.

Let $\\{X_{t}\\}$ be an alpha-mixing Markov Chain with mixing coefficients
$\\{\alpha_{t}\\}$. Then the process $\\{Y_{t}\\}$ where
$Y_{t}:=\log\left(\frac{p_{\theta_{0}}(X_{t}|X_{t-1})}{p_{\theta}(X_{t}|X_{t-1})}\right)$
is also alpha-mixing with mixing coefficients $\\{\tilde{\alpha}_{t}\\}$ where
$\tilde{\alpha}_{t}=\alpha_{t-1}$.

###### Proof.

By $Z_{i}$ denote the paired random measure $(X_{i},X_{i-1})$. Let
$\mathcal{M}_{i}^{j}$ denote the sigma field generated by the measures
$X_{k},\text{ where }i\leq k\leq j$. By $\mathcal{G}_{i}^{j}$ denote the sigma
field generated by the measures $Z_{k},\text{ where }i\leq k\leq j$. Let
$C\in\mathcal{M}_{i-1}^{j}$. Then, $C$ can be expressed as $(C_{i-1}\times
C_{i}\times\dots\times C_{j})$. for $C_{i-1}\in\mathcal{M}_{i-1}^{i-1}\text{,
}C_{i}\in\mathcal{M}_{i}^{i}\dots$ and so on. Now, consider a map.
$T_{i}^{j}:(C_{i-1}\times C_{i}\times\dots\times
C_{j})\xrightarrow{}(C_{i-1}\times C_{i}\times C_{i}\times\dots\times
C_{j-1}\times C_{j-1}\times C_{j})$. Note that, $T(C)\in\mathcal{G}_{i}^{j}$.
It is easy to see that
$\mathcal{G}_{i}^{j}=T_{i}^{j}(\mathcal{M}_{i-1}^{j})\cup\mathcal{M}_{i-1}^{*j}$,
where $T_{i}^{j}(\mathcal{M}_{i-1}^{j})$ is obtained by applying the map
$T_{i}^{j}$ to each element of $\mathcal{M}_{i-1}^{j}$. If we assume this
latter set to be the range and $\mathcal{M}_{i-1}^{j}$ to be the domain, then,
by construction, $T_{i}^{j}$ is a bijection. Also, the two classes are made of
disjoint sets, i.e. if $A\in T_{i}^{j}(\mathcal{M}_{i-1}^{j})\text{ and
}A^{*}\in\mathcal{M}_{i-1}^{*j}$, then $A\cap A^{*}=\phi$. Also, note that
$\mathcal{M}_{i-1}^{j*}$ is made of impossible sets. i.e.
$P(A^{*})=0\enspace\forall\enspace A^{*}\in\mathcal{M}_{i-1}^{j*}$. Now
consider the alpha mixing coefficients for $Z_{i}$. By definition, it is given
by

$\displaystyle\alpha^{z}_{k}$
$\displaystyle=\underset{i}{\sup}\underset{A\in\mathcal{G}_{-\infty}^{i},B\in\mathcal{G}_{i+k}^{\infty}}{\sup}|P(A\cap
B)-P(A)P(B)|$
$\displaystyle=\underset{i}{\sup}\underset{A\in\mathcal{G}_{-\infty}^{i},B\in\mathcal{G}_{i+k}^{\infty}}{\sup}|P((A^{o}\cup
A^{*})\cap(B^{o}\cup B^{*}))-P((A^{o}\cup A^{*}))P((B^{o}\cup B^{*}))|.$

Where,

$A=(A^{o}\cup A^{*})$ | $B=(B^{o}\cup B^{*})$
---|---
$A^{o}\in\mathcal{T}_{-\infty}^{i}({M}_{-\infty}^{i})$ | $A^{*}\in\mathcal{M}_{-\infty}^{*i}$
$B^{o}\in T_{i+k-1}^{\infty}(\mathcal{M}_{j+k-1}^{\infty})$ | $B^{*}\in\mathcal{M}_{j+k-1}^{*\infty}.$

Then, the expression for the alpha mixing coefficient can be reduced into

$\displaystyle\alpha^{z}_{k}$
$\displaystyle=\underset{i}{\sup}\underset{A^{o}\in
T_{-\infty}^{i}(\mathcal{M}_{-\infty}^{i}),B^{o}\in
T_{i+k-1}^{\infty}(\mathcal{M}_{i+k-1}^{\infty})}{\sup}|P(A^{o}\cap
B^{o})-P(A^{o})P(B^{o})|.$

Note that, by bijection property of $T_{i}^{j}$, we can find
$A^{\prime}\in\mathcal{M}_{-\infty}^{i}$ and
$B^{\prime}\in\mathcal{M}_{i+k-1}^{\infty}$ such that

$\displaystyle\alpha^{z}_{k}$
$\displaystyle=\underset{i}{\sup}\underset{A^{\prime}\in\mathcal{M}_{-\infty}^{i},B^{\prime}\in\mathcal{M}_{i+k-1}^{\infty}}{\sup}|P(T_{-\infty}^{i}(A^{\prime})\cap
T_{i+k-1}^{\infty}(B^{\prime}))-P(T_{-\infty}^{i}(A^{\prime}))P(T_{i+k-1}^{\infty}(B^{\prime}))|.$
$\displaystyle=\alpha_{k-1}.$

Now,
$\log\left(\frac{p_{\theta_{0}}(X_{n}|X_{n-1})}{p_{\theta}(X_{n}|X_{n-1})}\right)$
is just a function of the paired Markov chain $Z_{i}$, therefore it has alpha-
mixing coefficient $\alpha_{k-1}$. ∎

###  C.5. Proof of Theorem 3.1 :

###### Proof.

Part 1: Verifying condition (i) of Corollary 2.1.

We substitute the true parameter $\theta_{0}$ for $\theta_{1}$ and $\theta$
for $\theta_{2}$. We also set $q_{1}^{(0)}$ to be the invariant distribution
of the Markov chain under $\theta_{0}$, $q_{0}$, and $q_{2}^{(0)}$ as the
invariant distribution of the Markov chain under $\theta$, $q_{\theta}$.
Applying the fact that these Markov chains are stationary to Proposition 2.2,
we have

$\displaystyle\mathcal{K}(P^{(n)}_{\theta_{0}},P^{(n)}_{\theta})$
$\displaystyle=n\mathrm{E}\left[\log\left(\frac{p_{\theta_{0}}(X_{1}|X_{0})}{p_{\theta}(X_{1}|X_{0})}\right)\right]+\mathrm{E}[Z_{0}],$
(59) $\displaystyle\leq
n\sum_{j=1}^{m}\mathrm{E}\left[M^{(1)}_{j}(X_{1},X_{0})\right]|f^{(1)}_{j}(\theta,\theta_{0})|+\sum_{k=1}^{m}{\mathrm{E}[M^{(2)}_{k}(X_{0})]|f^{(2)}_{k}(\theta,\theta_{0})|},$

where the inequality follows from Assumption 3.1. Therefore, it follows that

$\displaystyle\int\mathcal{K}(P^{(n)}_{\theta_{0}},P^{(n)}_{\theta})\rho_{n}(d\theta)$
$\displaystyle\leq
n\sum_{j=1}^{m}\mathrm{E}\left[M^{(1)}_{j}(X_{1},X_{0})\right]\int|f^{(1)}_{j}(\theta,\theta_{0})|\rho_{n}(d\theta)+\sum_{k=1}^{m}\mathrm{E}[M^{(2)}_{k}(X_{0})]|\int
f^{(2)}_{k}(\theta,\theta_{0})|\rho_{n}(d\theta).$ By item i in
LABEL:{assume:gen-lip}, it follows that
$\displaystyle\int\mathcal{K}(P^{(n)}_{\theta_{0}},P^{(n)}_{\theta})\rho_{n}(d\theta)$
$\displaystyle\leq
n\sum_{j=1}^{m}\mathrm{E}\left[M^{(1)}_{j}(X_{1},X_{0})\right]\frac{C}{\sqrt{n}}+\sum_{k=1}^{m}\mathrm{E}[M^{(2)}_{k}(X_{0})]\frac{C}{\sqrt{n}}\leq
n\epsilon_{n}^{(1)},$

where $\epsilon_{n}^{(1)}\in O\left(\frac{1}{\sqrt{n}}\right)$.
Part 2: Verifying condition (ii) of Corollary 2.1. Again, using Proposition
2.3 along with the fact that the Markov chain is stationary we have

$\displaystyle\mathrm{Var}[r_{n}(\theta,\theta_{0})]$ $\displaystyle\leq
n\left(\frac{4}{n}+6n^{\delta/2}C_{\theta_{0},\theta}^{(1)}\right)\left(\sum_{k\geq
0}\alpha_{k}^{\delta/(2+\delta)}\right)$
$\displaystyle\qquad+\left(\frac{4}{n^{2}}+2n^{\delta/2}(C_{\theta_{0},\theta}^{(1)}+D_{\theta_{0},\theta}+\sqrt{C_{\theta_{0},\theta}^{(1)}D_{\theta_{0},\theta}})\right)\left(\sum_{k\geq
1}\alpha_{k}^{\delta/(2+\delta)}\right)+\mathrm{Var}[Z_{0}].$ It then follows
that
$\displaystyle\int\mathrm{Var}[r_{n}(\theta,\theta_{0})]\rho_{n}(d\theta)$
$\displaystyle\leq n\left(\frac{4}{n}+6n^{\delta/2}\int
C_{\theta_{0},\theta}^{(1)}\rho_{n}(d\theta)\right)\left(\sum_{k\geq
1}\alpha_{k-1}^{\delta/(2+\delta)}\right)+\int\mathrm{Var}[Z_{0}]\rho_{n}(d\theta)+$
$\displaystyle\left(\frac{4}{n^{2}}+2n^{\delta/2}(\int
C_{\theta_{0},\theta}^{(1)}\rho_{n}(d\theta)+\int
D_{\theta_{0},\theta}\rho_{n}(d\theta)+\int\sqrt{C_{\theta_{0},\theta}^{(1)}D_{\theta_{0},\theta}}\rho_{n}(d\theta))\right)\left(\sum_{k\geq
1}\alpha_{k}^{\delta/(2+\delta)}\right).$

First, consider the term $\int C_{\theta_{0},\theta}^{(1)}\rho_{n}(\theta)$,
and observe that

$\displaystyle\int C_{\theta_{0},\theta}^{(1)}\rho_{n}(d\theta)$
$\displaystyle=\int\mathrm{E}\log\left|\frac{p_{\theta_{0}}(X_{1}|X_{0})}{p_{\theta}(X_{1}|X_{0})}\right|^{2+\delta}\rho_{n}(d\theta).$
By 3.1, we have
$\displaystyle\int\mathrm{E}\log\left|\frac{p_{\theta_{0}}(X_{1}|X_{0})}{p_{\theta}(X_{1}|X_{0})}\right|^{2+\delta}\rho_{n}(d\theta)$
$\displaystyle\leq\int\mathrm{E}\left[\sum_{j=1}^{m}M^{(1)}_{j}(X_{1},X_{0})|f^{(1)}_{k}(\theta,\theta_{0})|\right]^{2+\delta}\rho_{n}(d\theta).$
Since the function $x\mapsto x^{2+\delta}$ is convex, we can apply Jensen’s
inequality to obtain,
$\displaystyle\left(\sum_{j=1}^{m}M^{(1)}_{j}(X_{1},X_{0})|f^{(1)}_{k}(\theta,\theta_{0})|\right)^{2+\delta}$
$\displaystyle\leq
m^{1+\delta}\sum_{k=1}^{m}M^{(1)}_{j}(X_{1},X_{0})^{2+\delta}|f^{(1)}_{k}(\theta,\theta_{0})|^{2+\delta}.$
Therefore, it follows that
$\displaystyle\int\mathrm{E}\log\left|\frac{p_{\theta_{0}}(X_{1}|X_{0})}{p_{\theta}(X_{1}|X_{0})}\right|^{2+\delta}\rho_{n}(d\theta)$
$\displaystyle\leq
m^{1+\delta}\sum_{k=1}^{m}\mathrm{E}[M^{(1)}_{k}(X_{1},X_{0})^{2+\delta}]\int|f^{(1)}_{k}(\theta,\theta_{0})|^{2+\delta}\rho_{n}(d\theta).$
By 3.1,
$\int|f_{k}(\theta,\theta_{0})|^{2+\delta}\rho_{n}(d\theta)<\frac{C}{n}$ and
$\mathrm{E}[M^{(1)}_{k}(X_{1},X_{0})^{2+\delta}]<B$, implying that
$\displaystyle\int C_{\theta_{0},\theta}^{(1)}\rho_{n}(d\theta)$
$\displaystyle\leq
m^{1+\delta}\sum_{k=1}^{m}B\frac{C}{n}=m^{2+\delta}\frac{BC}{n}.$

Since $\left(\sum_{k\geq 0}\alpha_{k}^{\delta/(2+\delta)}\right)<\infty$, it
follows that $\left(\frac{4}{n}+6n^{\delta/2}\int
C_{\theta_{0},\theta}^{(1)}\rho_{n}(d\theta)\right)\left(\sum_{k\geq
1}\alpha_{k-1}^{\delta/(2+\delta)}\right)\in\mathrm{O}(\frac{n^{\delta/2}}{n})$.
Similarly, we can show that $\int D_{\theta_{0},\theta}\rho_{n}(d\theta)\in
O(\frac{1}{n})$, and $\int\mathrm{Var}[Z_{0}]\rho_{n}(d\theta)\in
O(\frac{1}{n})$.

For the final term
$\int\sqrt{C_{\theta_{0},\theta}^{(1)}D_{\theta_{0},\theta}}\rho_{n}(d\theta)$,
use the Cauchy-Schwarz inequality to obtain the upper bound
$\left(\int{C_{\theta_{0},\theta}^{(1)}\rho_{n}(d\theta)\int
D_{\theta_{0},\theta}}\rho_{n}(d\theta)\right)^{1/2}$ which is also of order
$O(\frac{1}{n})$. Combining all of these together we have

$\displaystyle\int\mathrm{Var}[r_{n}(\theta,\theta_{0})]\rho_{n}(d\theta)\leq
n\epsilon^{(2)}_{n},$

for some $\epsilon^{(2)}_{n}\in\mathrm{O}(\frac{n^{\delta/2}}{n})$.

Since $\mathcal{K}(\rho_{n},\pi)<\sqrt{n}C=n\frac{C}{\sqrt{n}},$ it follows
that $\mathcal{K}(\rho_{n},\pi)<n\epsilon_{n}^{(3)},$ where
$\epsilon_{n}^{(3)}=\mathrm{O}(1/\sqrt{n})$ as before. Finally, by choosing
$\epsilon_{n}=\max(\epsilon_{n}^{(1)},\epsilon_{n}^{(2)},\epsilon_{n}^{(3)})$,
our theorem is proved. ∎

###  C.6. Proof of Theorem 4.1

###### Proof.

Verifying condition (i) of Corollary 2.1: As in the proof of Theorem 3.1
substitute the true parameter $\theta_{0}$ for $\theta_{1}$ and $\theta$ for
$\theta_{2}$ in . We also set $q_{1}^{(0)}$ and $q_{2}^{(0)}$ to the
distribution $q^{(0)}$. Applying Proposition 2.2 to the corresponding
transition kernels and initial distribution we have,

(60) $\displaystyle\mathcal{K}(P^{(n)}_{\theta_{0}},P^{(n)}_{\theta})$
$\displaystyle=\sum_{i=1}^{n}\mathrm{E}\left[\log\left(\frac{p_{\theta_{0}}(X_{i}|X_{i-1})}{p_{\theta}(X_{i}|X_{i-1})}\right)\right]+\mathrm{E}\left[\log\left(\frac{D(X_{0})}{D(X_{0})}\right)\right]$
$\displaystyle=\sum_{i=1}^{n}\mathrm{E}\left[\log\left(\frac{p_{\theta_{0}}(X_{i}|X_{i-1})}{p_{\theta}(X_{i}|X_{i-1})}\right)\right].$

Now, applying Assumption 3.1, we can bound the previous equation as follows,

$\displaystyle\leavevmode\nobreak\
\mathcal{K}(P^{(n)}_{\theta_{0}},P^{(n)}_{\theta})$
$\displaystyle\leq\sum_{i=1}^{n}\mathrm{E}\left[\sum_{k=1}^{m}M^{(1)}_{k}(X_{i},X_{i-1})|f^{(1)}_{k}(\theta,\theta_{0})|\right]$
(61)
$\displaystyle=\sum_{i=1}^{n}\sum_{k=1}^{m}\mathrm{E}\left[M^{(1)}_{k}(X_{i},X_{i-1})\right]|f^{(1)}_{k}(\theta,\theta_{0})|.$

Since $M^{(1)}_{k}$’s are bounded there exists a constant $Q$ so that,

$\displaystyle\int\mathcal{K}(P^{(n)}_{\theta_{0}},P^{(n)}_{\theta})\rho_{n}(d\theta)$
$\displaystyle\leq
Q\int\sum_{i=1}^{n}\sum_{k=1}^{m}|f^{(1)}_{k}(\theta,\theta_{0})|\rho_{n}(d\theta)$
$\displaystyle=Qn\sum_{k=1}^{m}\int|f^{(1)}_{k}(\theta,\theta_{0})|\rho_{n}(d\theta).$
By eq. 21 in 3.1, it follows that
$\displaystyle\int\mathcal{K}(P^{(n)}_{\theta_{0}},P^{(n)}_{\theta})\rho_{n}(d\theta)$
$\displaystyle\leq
Qn\sum_{k=1}^{m}\frac{C}{\sqrt{n}}=nmQ\frac{C}{\sqrt{n}}=n\epsilon^{(1)}_{n},$

for some $\epsilon^{(1)}_{n}\in\mathrm{O}(\frac{1}{\sqrt{n}})$.

Verifying condition (ii) of Corollary 2.1: As in the previous part, $Z_{0}=0$,
implying that $D_{\theta,\theta_{0}}$. Applying Proposition 2.3 and
integrating with respect to $\rho_{n}$, we obtain

$\displaystyle\int\mathrm{Var}\left[r_{n}(\theta,\theta_{0})\right]\rho_{n}(d\theta)$
$\displaystyle\leq\sum_{i=1}^{n}\left(\frac{4}{n}+2n^{\delta/2}\int
C_{\theta_{0},\theta}^{(i)}\rho_{n}(d\theta)\right)\left(\alpha_{i-1}^{\delta/(2+\delta)}\right)$
(62) $\displaystyle+\sum_{i,j=1}^{n}\left(\frac{4}{n}+2n^{\delta/2}(\int
C_{\theta_{0},\theta}^{(i)}\rho_{n}(d\theta)+\int
C_{\theta_{0},\theta}^{(j)}\rho_{n}(d\theta)+\int\sqrt{C_{\theta_{0},\theta}^{(i)}C_{\theta_{0},\theta}^{(j)}}\rho_{n}(d\theta))\right)\left(\alpha_{|i-j|-1}^{\delta/(2+\delta)}\right).$

First, consider the term $\int C_{\theta_{0},\theta}^{(i)}\rho_{n}(d\theta)$.
Using 3.1, we can upper bound $C_{\theta_{0},\theta}^{(i)}$ as,

$\displaystyle C_{\theta_{0},\theta}^{(i)}$
$\displaystyle\leq\mathrm{E}\left[\sum_{k=1}^{m}M^{(1)}_{k}(X_{i},X_{i-1})|f^{(1)}_{k}(\theta,\theta_{0})|\right]^{2+\delta}$
$\displaystyle\leq\sum_{k=1}^{m}m^{1+\delta}\mathrm{E}\left[\left(M^{(1)}_{k}(X_{i},X_{i-1})|f^{(1)}_{k}(\theta,\theta_{0})|\right)^{2+\delta}\right]\text{(by
Jensen's inequality)}$
$\displaystyle=\sum_{k=1}^{m}m^{1+\delta}\mathrm{E}\left[M^{(1)}_{k}(X_{i},X_{i-1})^{2+\delta}\right]|f^{(1)}_{k}(\theta,\theta_{0})|^{2+\delta}.$
Since $M^{(1)}_{k}$’s are upper bounded by $Q$, it follows that,
$C_{\theta_{0},\theta}^{(i)}\leq\sum_{k=1}^{m}m^{1+\delta}Q^{2+\delta}|f^{(1)}_{k}(\theta,\theta_{0})|^{2+\delta}$.
Hence, from 3.1, we get, $\displaystyle\int
C_{\theta_{0},\theta}^{(i)}\rho_{n}(d\theta)$
$\displaystyle\leq\sum_{k=1}^{m}m^{1+\delta}Q^{2+\delta}\int|f^{(1)}_{k}(\theta,\theta_{0})|^{2+\delta}\rho_{n}(d\theta)\leq(mQ)^{2+\delta}\frac{C}{n}.$

Using the upper bound above, we can say for an $L$ large enough, $\int
C_{\theta_{0},\theta}^{(i)}\rho_{n}(d\theta)\leq\frac{L}{n}$. Next, by the
Cauchy-Schwarz inequality, we have that
$\int\sqrt{C_{\theta_{0},\theta}^{(i)}C_{\theta_{0},\theta}^{(j)}\rho_{n}(d\theta))}<\sqrt{\int
C_{\theta_{0},\theta}^{(i)}\rho_{n}(d\theta)\int
C_{\theta_{0},\theta}^{(j)}\rho_{n}(d\theta))}\leq\frac{L}{n}$. Thus, we have
the following upper bound.

$\displaystyle\int\mathrm{Var}\left[r_{n}(\theta,\theta_{0})\right]\rho_{n}(d\theta)$
$\displaystyle\leq\sum_{i=1}^{n}\left(\frac{4}{n}+2n^{\delta/2}\frac{L}{n}\right)\left(\alpha_{i-1}^{\delta/(2+\delta)}\right)+\sum_{i,j=1}^{n}\left(\frac{4}{n}+2n^{\delta/2}(\frac{L}{n}+\frac{L}{n}+\frac{L}{n})\right)\left(\alpha_{|i-j|-1}^{\delta/(2+\delta)}\right)$
$\displaystyle=\left(\frac{4}{n}+2n^{\delta/2}\frac{L}{n}\right)\left(\sum_{i=1}^{n}\alpha_{i-1}^{\delta/(2+\delta)}\right)+\left(\frac{4}{n}+6n^{\delta/2}\frac{L}{n}\right)\left(\sum_{i,j=1}^{n}\alpha_{|i-j|-1}^{\delta/(2+\delta)}\right).$

Since $\sum_{i,j=1}^{n}\alpha_{|i-j|-1}^{\delta/(2+\delta)}<n\sum_{k\geq
1}\alpha_{k-1}^{\delta/(2+\delta)}<\infty$, we have that for some
$\epsilon_{n}^{(2)}\in\mathrm{O}(\frac{n^{\delta/2}}{n})$,

$\displaystyle\int\mathrm{Var}\left[r_{n}(\theta,\theta_{0})\right]\rho_{n}(d\theta)<n\epsilon_{n}^{(2)}.$

Since $\mathcal{K}(\rho_{n},\pi)\leq\sqrt{n}C$, following the concluding
argument in Theorem 3.1 completes the proof. ∎

###  C.7. Proposition 4.1

###### Proof of Proposition 4.1.

We verify 3.1 and the proof follows from Theorem 4.1. For
$i\in\\{1,2,\dots,K-1\\}$,

$\displaystyle p_{\theta}(j|i)=\begin{cases}\theta&\leavevmode\nobreak\
\text{if}\leavevmode\nobreak\ j=i-1,\\\ 1-\theta&\leavevmode\nobreak\
\text{if}\leavevmode\nobreak\ j=i+1.\end{cases}$

If $i=0$ or $i=K$, then the Markov chain goes back to $1$ or $K-1$
respectively with probability 1. With the convention $\log\frac{0}{0}=0$, the
log ratio of the transition probabilities becomes,

$\displaystyle|\log p_{\theta_{0}}(X_{1}|X_{0})-\log
p_{\theta}(X_{1}|X_{0})|=I_{[X_{1}=X_{0}+1]}\log\left(\frac{\theta_{0}}{\theta}\right)+I_{[X_{1}=X_{0}-1]}\log\left(\frac{1-\theta_{0}}{1-\theta}\right).$

In this case, $m=2$. $M^{(1)}_{1}(X_{1},X_{0})=I_{[X_{1}=X_{0}+1]}$ and
$M^{(1)}_{2}(X_{1},X_{0})=I_{[X_{1}=X_{0}-1]}$, both of which are bounded. Let
$f^{(1)}_{1}(\theta,\theta_{0}):=\log\left(\frac{\theta_{0}}{\theta}\right)$
suppose
$f^{(1)}_{2}(\theta,\theta_{0}):=\log\left(\frac{1-\theta_{0}}{1-\theta}\right)$.

The stationary distribution $q_{\theta}(i)=\frac{1}{K}\enspace\forall\enspace
i\in{1,2,\dots,K}$. Hence the log of the ratio of the invariant distribution
becomes

(63) $\displaystyle\log q_{0}(x)-\log q_{\theta}(x)$ $\displaystyle=0,$

and we can set $M^{(2)}_{i}(\cdot):=1$ and $f^{(2)}_{i}(\cdot,\cdot):=0$ for
$i\in\\{1,2\\}$. Thus, to prove the concentration bound for this Markov chain
it is enough to assume that $\delta=1$ and show that
$\int[f^{(1)}_{1}(\theta,\theta_{0})]^{3}\rho_{n}(d\theta)<\frac{C}{n}$ and
$\int[f^{(1)}_{2}(\theta,\theta_{0})]^{3}\rho_{n}(d\theta)<\frac{C}{n}$ for
some constant $C>0$.

As given, $\\{\rho_{n}\\}$ is a sequence of beta probability distribution
functions, with parameters $\alpha_{n},\beta_{n}$ that satisfy the constraint
$\frac{\alpha_{n}}{\alpha_{n}+\beta_{n}}=\theta_{0}$. Specifically, we choose
$\alpha_{n}=n\theta_{0}$ and (therefore) $\beta_{n}=n(1-\theta_{0})$. Thus, we
get the following,

$\displaystyle\int|f^{(1)}_{1}(\theta,\theta_{0})|^{3}\rho_{n}(d\theta)$
$\displaystyle=\int\left|\log\left(\frac{\theta_{0}}{\theta}\right)\right|^{3}\rho_{n}(d\theta)$
$\displaystyle<\int\left|\frac{\theta_{0}}{\theta}-1\right|^{3}\rho_{n}(d\theta)$
$\displaystyle=\frac{1}{\text{Beta}(\alpha_{n},\beta_{n})}\int_{0}^{1}\left|\frac{\theta_{0}-\theta}{\theta}\right|^{3}\theta^{\alpha_{n}-1}(1-\theta)^{\beta_{n}-1}d\theta.$
Since $\theta_{0},\theta\in(0,1)$, so is $\frac{|\theta_{0}-\theta|}{2}$,
giving $|\theta_{0}-\theta|^{3}<2(\theta_{0}-\theta)^{2}$. We use that fact to
arrive at
$\displaystyle\int|f^{(1)}_{1}(\theta,\theta_{0})|^{3}\rho_{n}(d\theta)$
$\displaystyle\leq\frac{2}{\text{Beta}(\alpha_{n},\beta_{n})}\int_{0}^{1}(\theta_{0}-\theta)^{2}\theta^{\alpha_{n}-3}(1-\theta)^{\beta_{n}-1}d\theta$
$\displaystyle=\frac{2\text{Beta}(\alpha_{n}-3,\beta_{n})}{\text{Beta}(\alpha_{n},\beta_{n})}\frac{(\alpha_{n}-3)(\beta_{n})}{(\alpha_{n}+\beta_{n}-3)^{2}(\alpha_{n}+\beta_{n}-2)}.$

From our choice of $\alpha_{n}$ and $\beta_{n}$,
$\frac{2\text{Beta}(\alpha_{n}-3,\beta_{n})}{\text{Beta}(\alpha_{n},\beta_{n})}=O(1)$,
and plugging the values of $\alpha_{n}$ and $\beta_{n}$ into
$\frac{(\alpha_{n}-3)(\beta_{n})}{(\alpha_{n}+\beta_{n}-3)^{2}(\alpha_{n}+\beta_{n}-2)}$,
we get
$\frac{(\alpha_{n}-3)(\beta_{n})}{(\alpha_{n}+\beta_{n}-3)^{2}(\alpha_{n}+\beta_{n}-2)}=\frac{1}{n}\frac{(\theta_{0}-\frac{3}{n})(1-\theta_{0})}{(1-\frac{3}{n})^{2}(1-\frac{2}{n})}$,
which is upper bounded by $\frac{C_{1}}{n}$ for some constant $C_{1}>0$.
Hence,

$\displaystyle\int|f^{(1)}_{1}(\theta,\theta_{0})|^{3}\rho_{n}(d\theta)$
$\displaystyle<\frac{C_{1}}{n}.$

Similarly, we can also show that,

$\displaystyle\int|f^{(1)}_{2}(\theta,\theta_{0})|^{3}\rho_{n}(d\theta)$
$\displaystyle<\frac{C_{2}}{n}.$

Finally, from Proposition B.1, we get that
$\mathcal{K}(\rho_{n},\pi)<C+\frac{1}{2}\log(n)$ for some large constant $C$.
Hence, $\mathcal{K}(\rho_{n},\pi)<C_{3}\sqrt{n}$ for some constant $C_{3}>0$.
Choosing $C=\max(C_{1},C_{2},C_{3})$, we satisfy all the conditions of 3.1 and
Theorem 4.1. ∎

###  C.8. Proof of Proposition 4.2

###### Proof.

For the purpose of this proof, we choose $\rho_{n}$’s with scaled Beta
distribution with parameters $\alpha_{n}=n(2\theta_{0})$ and
$\beta_{n}=n(1-2\theta_{0})$. Since, $\rho_{n}$ is a scaled Beta distribution
with the scaling factors $m=0.5$ and $c=0$, the pdf of $\rho_{n}$ is given by

$\displaystyle\rho_{n}(\theta)$
$\displaystyle=\frac{0.5}{\text{Beta}(\alpha_{n},\beta_{n})}\left(2\theta\right)^{\alpha_{n}}\left(1-2\theta\right)^{\beta_{n}}$

Since this is a scaled distribution,
$E_{\rho_{n}}[\theta]=0.5\frac{\alpha_{n}}{\alpha_{n}+\beta_{n}}=\theta_{0}$
and there exists a constant $\sigma>0$,
$\mathrm{Var}_{\rho_{n}}[\theta]=\frac{\sigma^{2}}{n}$. Now, we analyse the
transition probabilities. For $i\in\\{1,2,\dots\\}$, the Birth-Death process
has transition probabilities

$\displaystyle p_{\theta}(j|i)=\begin{cases}\theta&\leavevmode\nobreak\
\text{if}\leavevmode\nobreak\ j=i-1,\\\ 1-\theta&\leavevmode\nobreak\
\text{if}\leavevmode\nobreak\ j=i+1.\end{cases}$

If $i=0$, then the Markov chain goes to $1$ with probability $1$. Hence with
the convention $\log\frac{0}{0}=0$ the ratio of the log of the transition
probabilities becomes,

$\displaystyle|\log p_{\theta_{0}}(X_{1}|X_{0})-\log
p_{\theta}(X_{1}|X_{0})|=I_{[X_{1}=X_{0}+1]}\log\left[\frac{\theta_{0}}{\theta}\right]+I_{[X_{1}=X_{0}-1]}\log\left[\frac{1-\theta_{0}}{1-\theta}\right].$

In this case, $m=3$. $M^{(1)}_{1}(X_{1},X_{0})=I_{[X_{1}=X_{0}+1]}$ and
$M^{(1)}_{2}(X_{1},X_{0})=I_{[X_{1}=X_{0}-1]}$. Define
$M^{(1)}_{3}(X_{1},X_{0}):=1$. All these random variables are bounded. Define
$f^{(1)}_{1}(\theta,\theta_{0}):=\log\left[\frac{\theta_{0}}{\theta}\right],f^{(1)}_{2}(\theta,\theta_{0}):=\log\left[\frac{1-\theta_{0}}{1-\theta}\right]$
and $f^{(1)}_{3}(\theta,\theta_{0}):=0$. Similarly as in the proof on
Proposition 4.1,

$\displaystyle\int[f^{(1)}_{1}(\theta,\theta_{0})]^{3}\rho_{n}(d\theta)$
$\displaystyle<\frac{C_{1}}{n},\text{ and }$
$\displaystyle\int[f^{(1)}_{2}(\theta,\theta_{0})]^{3}\rho_{n}(d\theta)$
$\displaystyle<\frac{C_{2}}{n}.$

The stationary distribution is given by
$q_{\theta}(i)=(\frac{\theta}{1-\theta})^{i-1}q_{\theta}(1)\enspace\forall\enspace
i\in{1,2,\dots}$, so that
$q_{\theta}(i)=(1-\theta)(\frac{\theta}{1-\theta})^{i-1}$ Hence the log of the
ratio of the invariant distribution becomes

(64) $\displaystyle\log q_{0}(i)-\log q_{\theta}(i)$
$\displaystyle=\log\left[\frac{1-\theta_{0}}{1-\theta}\right]+(i-1)\log\left[\frac{\theta_{0}}{\theta}\right]-(i-1)\log\left[\frac{1-\theta_{0}}{1-\theta}\right]$

We define $M^{(2)}_{1}(X_{0}):=1$, and
$M^{(2)}_{2}(X_{0})=M^{(2)}_{3}(X_{0}):=X_{0}-1$. We can write
$\mathrm{E}_{q^{(0)}}[M^{(2)}_{2}(X_{0})]^{2}=\sum_{i=1}^{\infty}(i-1)^{2}q^{(0)}(i)<\sum_{i=1}^{\infty}i^{2}q^{(0)}(i)$.
We have chosen $q^{(0)}$ such that $\sum_{i=1}^{\infty}i^{2}q^{(0)}(i)$ is
bounded. Hence, $\mathrm{E}_{q^{(0)}}[M^{(2)}_{2}(X_{0})]^{2}<\infty$. To
verify Item i define,
$f^{(2)}_{1}(\theta,\theta_{0})=-f^{(2)}_{3}(\theta,\theta_{0}):=\log\left[\frac{1-\theta_{0}}{1-\theta}\right]$,
and define
$f^{(2)}_{2}(\theta,\theta_{0}):=\log\left[\frac{\theta_{0}}{\theta}\right]$.
Therefore following the proof of Proposition 4.1,

$\displaystyle\int|f^{(2)}_{1}(\theta,\theta_{0})|^{3}\rho_{n}(d\theta)=\int|f^{(2)}_{3}(\theta,\theta_{0})|^{3}\rho_{n}(d\theta)=$
$\displaystyle\int|f^{(1)}_{2}(\theta,\theta_{0})|^{3}\rho_{n}(d\theta)<\frac{C_{2}}{n},\text{
and },$
$\displaystyle\int|f^{(2)}_{2}(\theta,\theta_{0})|^{3}\rho_{n}(d\theta)=$
$\displaystyle\int|f^{(1)}_{1}(\theta,\theta_{0})|^{3}\rho_{n}(d\theta)<\frac{C_{1}}{n}.$

Finally, we take the KL-divergence $\mathcal{K}(\rho_{n},\pi)$. $\rho_{n}$
follows a scaled Beta distribution on $(0,1/2)$ with parameters
$\alpha_{n}=n(2\theta_{0})$ and $\beta_{n}=n(1-2\theta_{0})$, while $\pi$
follows a scaled Beta distribution on $(0,1/2)$ with parameters $\alpha$ and
$\beta$. Thus,

$\displaystyle\mathcal{K}(\rho_{n},\pi)$
$\displaystyle=\int_{0}^{\frac{1}{2}}\frac{\rho_{n}(\theta)}{\pi(\theta)}\rho_{n}(d\theta),$
which, by substituting $t=2\theta$, we get,
$\displaystyle\mathcal{K}(\rho_{n},\pi)$
$\displaystyle=2\int_{0}^{1}\frac{\rho_{n}(t)}{\pi(t)}\rho_{n}(dt).$

$\int_{0}^{1}\frac{\rho_{n}(t)}{\pi(t)}\rho_{n}(dt)$ is the KL-divergence
between a Beta distribution with parameters $\alpha_{n}$ and $\beta_{n}$ and a
Beta distribution with parameters $\alpha$ and $\beta$. An application of
proposition B.1 gives us for a constant $C_{1}>0$,

$\displaystyle\int_{0}^{1}\frac{\rho_{n}(t)}{\pi(t)}\rho_{n}(dt)<C_{1}+\frac{1}{2}\log(n).$

Hence we can say,
$\mathcal{K}(\rho_{n},\pi)<2\left[C_{1}+\frac{1}{2}\log(n)\right]$. Thus, we
now get that for some constant $C_{3}>0$,

$\displaystyle\mathcal{K}(\rho_{n},\pi)<C_{3}\sqrt{n}.$

Choosing $C=\max(C_{1},C_{2},C_{3})$ we satisfy all of the conditions of 3.1
and thus by Theorem 4.1, we are complete the proof. ∎

###  C.9. Proof of Theorem 4.3 :

###### Proof.

Verification of condition (i) of Corollary 2.1 As in the proof of Theorem 3.1
substitute the true parameter $\theta_{0}$ for $\theta_{1}$ and $\theta$ for
$\theta_{2}$. We also set $q_{1}^{(0)}$ and $q_{2}^{(0)}$ to the known initial
distribution $q^{(0)}$. Similar to the steps leading to section C.6, we get

$\displaystyle\mathcal{K}(P^{(n)}_{\theta_{0}},P^{(n)}_{\theta})$
$\displaystyle\leq\sum_{i=1}^{n}\sum_{k=1}^{m}\mathrm{E}\left[M^{(1)}_{k}(X_{i},X_{i-1})\right]|f^{(1)}_{k}(\theta,\theta_{0})|.$

Consider the term $\mathrm{E}\left[{M^{(1)}_{k}(X_{i},X_{i-1})}\right]$. With
$q^{(i-1)}_{\theta_{0}}$ the marginal distribution of $X_{i-1}$, we have

$\displaystyle\mathrm{E}\left[M^{(1)}_{k}(X_{i},X_{i-1})\right]$
$\displaystyle=\int
M^{(1)}_{k}(x_{i},x_{i-1})p_{\theta_{0}}(x_{i}|x_{i-1})q^{(i-1)}_{\theta_{0}}(x_{i-1})dx_{i}dx_{i-1}.$
$\displaystyle\mathrm{E}\left[M^{(1)}_{k}(X_{i},X_{i-1})\right]$
$\displaystyle=\int
M^{(1)}_{k}(x_{i},x_{i-1})p_{\theta_{0}}(x_{i}|x_{i-1})p_{\theta_{0}}^{i-1}(x_{i-1}|x_{0})q^{(0)}_{\theta_{0}}(x_{0})dx_{0}dx_{i}dx_{i-1}$
Recall that the marginal density satisfies
$q^{(i-1)}_{\theta_{0}}(x_{i-1})=\int
p_{\theta_{0}}^{i-1}(x_{i-1}|x_{0})q^{(0)}_{\theta_{0}}(x_{0})d(x_{0})$, where
$p_{\theta_{0}}^{i}(\cdot|x_{0})$ is the $i$-step transition probability. Then
$\displaystyle\mathrm{E}\left[M^{(1)}_{k}(X_{i},X_{i-1})\right]$
$\displaystyle=\int\mathrm{E}\left[M^{(1)}_{k}(X_{i},x_{i-1})|x_{i-1}\right]p_{\theta_{0}}^{i-1}(x_{i-1}|x_{0})q^{(0)}_{\theta_{0}}(x_{0})dx_{0}dx_{i-1}.$

Since the Markov chain $\\{X_{n}\\}$ satisfies A.1, we know by the application
of Theorem A.1 that $\\{X_{n}\\}$ is $V$-geometrically ergodic. Hence,
$\exists\enspace\tau<1$, $R<\infty$ such that $\forall\enspace|f|<V$

$\displaystyle|\int f(x_{i-1})p_{\theta_{0}}^{i-1}(x_{i-1}|x_{0})dx_{i-1}$
$\displaystyle-\int
f(x_{i-1})q_{\theta_{0}}(x_{i-1})dx_{i-1}|<RV(x_{0})\tau^{i-1},$ where
$q_{\theta_{0}}$ is the stationary distribution, implying that
$\displaystyle\int f(x_{i-1})p_{\theta_{0}}^{i-1}(x_{i-1}|x_{0})dx_{i-1}$
$\displaystyle<\int
f(x_{i-1})q_{\theta_{0}}(x_{i-1})dx_{i-1}+RV(x_{0})\tau^{i-1}.$

Using Jensen’s inequality we have
$\left(\mathrm{E}\left[M^{(1)}_{k}(X_{i},X_{i-1})|X_{i-1}\right]\right)^{2+\delta}\leq\mathrm{E}\left[M^{(1)}_{k}(X_{i},X_{i-1})^{2+\delta}|X_{i-1}\right]<V(X_{i-1})$.
Since $V(\cdot)\geq 1$, it follows that
$\mathrm{E}\left[M^{(1)}_{k}(X_{i},X_{i-1})|X_{i-1}\right]<V(X_{i-1})^{1/(2+\delta)}\leq
V(X_{i-1})$. Thus, setting
$f(x)=\mathrm{E}\left[M^{(1)}_{k}(X_{i},X_{i-1})|X_{i-1}=x\right]$, we obtain

$\displaystyle\mathrm{E}\left[M^{(1)}_{k}(X_{i},X_{i-1})\right]$
$\displaystyle<\int\left[\mathrm{E}\left[M^{(1)}_{k}(X_{i},X_{i-1})|X_{i-1}\right]q_{\theta_{0}}(x_{i})dx_{i-1}+RV(x_{0})\tau^{i-1}\right]q^{(0)}(x_{0})dx_{0}$
$\displaystyle=\mathrm{E}[M^{(1)}_{k}(X_{1},X_{0})]+\tau^{i-1}\int
RV(x_{0})q^{(0)}(x_{0})dx_{0}.$ Summing from $i=1$ to $n$, we get
$\displaystyle\sum_{i=1}^{n}\mathrm{E}\left[M^{(1)}_{k}(x_{i},x_{i-1})\right]$
$\displaystyle<n\mathrm{E}[M^{(1)}_{k}(X_{1},X_{0})]+\sum_{i=1}^{n}\tau^{i-1}\int
RV(x_{0})q^{(0)}(x_{0})dx_{0}$
$\displaystyle=n\mathrm{E}[M^{(1)}_{k}(X_{1},X_{0})]+\frac{1-\tau^{n}}{1-\tau}\int
RV(x_{0})q^{(0)}(x_{0})dx_{0}.$

This gives us the following bound on
$\int\mathcal{K}(P^{(n)}_{\theta_{0}},P^{(n)}_{\theta})\rho_{n}(d\theta)$:

$\displaystyle\int\mathcal{K}(P^{(n)}_{\theta_{0}},P^{(n)}_{\theta})\rho_{n}(d\theta)$
$\displaystyle\leq\sum_{k=1}^{m}\left[n\mathrm{E}[M^{(1)}_{k}(X_{1},X_{0})]+\frac{1-\tau^{n}}{1-\tau}\int
RV(x_{0})D(x_{0})dx_{0}\right]\int|f^{(1)}_{k}(\theta,\theta_{0})|\rho_{n}(d\theta).$

By 3.1,
$\int|f^{(1)}_{k}(\theta,\theta_{0})|\rho_{n}(d\theta)<\frac{C}{\sqrt{n}}$.
Hence, we can rewrite the previous expression as

$\displaystyle\int\mathcal{K}(P^{(n)}_{\theta_{0}},P^{(n)}_{\theta})\rho_{n}(d\theta)$
$\displaystyle\leq\sum_{k=1}^{m}\left[n\mathrm{E}[M^{(1)}_{k}(X_{1},X_{0})]+\frac{1-\tau^{n}}{1-\tau}\int
RV(x_{1})D(x_{1})dx_{1}\right]\frac{C}{\sqrt{n}}$
$\displaystyle=nm\left[\mathrm{E}[M^{(1)}_{k}(X_{1},X_{0})]+\frac{1-\tau^{n}}{n(1-\tau)}\int
RV(x_{0})D(x_{0})dx_{0}\right]\frac{C}{\sqrt{n}}.$ Since, $\tau<1$,
$0<1-\tau^{n}<1$, and we rewrite the previous equation as,
$\displaystyle\int\mathcal{K}(P^{(n)}_{\theta_{0}},P^{(n)}_{\theta})\rho_{n}(d\theta)$
$\displaystyle\leq
nm\left[\mathrm{E}[M^{(1)}_{k}(X_{1},X_{0})]+\frac{1}{n(1-\tau)}\int
RV(x_{0})D(x_{0})dx_{0}\right]\frac{C}{\sqrt{n}}.$ Hence, there exists an
$\epsilon^{(1)}_{n}\in\mathrm{O}(\frac{1}{\sqrt{n}})$ such that
$\int\mathcal{K}(P^{(n)}_{\theta_{0}},P^{(n)}_{\theta})\rho_{n}(d\theta)\leq
n\epsilon^{(1)}_{n}$.

Verification of condition (ii) of Corollary 2.1: Similar to as in the proof of
Theorem 4.1, we upper bound
$\int\mathrm{Var}\left[r_{n}(\theta,\theta_{0})\right]\rho_{n}(d\theta)$ by

(65)
$\displaystyle\int\mathrm{Var}\left[r_{n}(\theta,\theta_{0})\right]\rho_{n}(d\theta)$
$\displaystyle\leq\sum_{i,j=1}^{n}\left(\frac{4}{n}+2n^{\delta/2}(\int
C_{\theta_{0},\theta}^{(i)}\rho_{n}(d\theta)+\int
C_{\theta_{0},\theta}^{(j)}\rho_{n}(d\theta)+\int\sqrt{C_{\theta_{0},\theta}^{(i)}C_{\theta_{0},\theta}^{(j)}}\rho_{n}(d\theta))\right)\left(\alpha_{|i-j|-1}^{\delta/(2+\delta)}\right)$
$\displaystyle\qquad+\sum_{i=1}^{n}\left(\frac{4}{n}+2n^{\delta/2}\int
C_{\theta_{0},\theta}^{(i)}\rho_{n}(d\theta)\right)\left(\alpha_{i-1}^{\delta/(2+\delta)}\right),$

where $C_{\theta_{0},\theta}$ is upper bounded as

$\displaystyle C_{\theta_{0},\theta}^{(i)}$
$\displaystyle\leq\sum_{k=1}^{m}m^{1+\delta}\mathrm{E}\left[M^{(1)}_{k}(X_{i},X_{i-1})\right]^{2+\delta}|f^{(1)}_{k}(\theta,\theta_{0})|^{2+\delta}.$
Since
$\mathrm{E}\left[M^{(1)}_{k}(X_{i},X_{i-1})^{2+\delta}|X_{i-1}\right]<V(X_{i-1})$,
by a similar application of $V$-geometric ergodicity, we can say that,
$\exists\enspace 0<\tau<1$, such that
$\displaystyle\mathrm{E}\left[M^{(1)}_{k}(X_{i},X_{i-1})\right]^{2+\delta}$
$\displaystyle\leq
n\mathrm{E}[M^{(1)}_{k}(X_{1},X_{0})]^{2+\delta}+\tau^{i-1}\int
RV(x_{0})D(x_{0})dx_{0},$ which, by the fact that $\tau^{i-1}<\tau$, gives us,
$\displaystyle\mathrm{E}\left[M^{(1)}_{k}(X_{i},X_{i-1})\right]^{2+\delta}$
$\displaystyle\leq\mathrm{E}[M^{(1)}_{k}(X_{1},X_{0})]^{2+\delta}+\tau\int
RV(x_{0})D(x_{0})dx_{0}.$

By 3.1, we know that,
$\int|f^{(1)}_{k}(\theta,\theta_{0})|^{2+\delta}\rho_{n}(d\theta)<\frac{C}{n}$.
Hence, for a large constant $L$, $\int
C_{\theta_{0},\theta}^{(i)}\rho_{n}(d\theta)\leq\frac{L}{n}$. We also see that
since the chain is geometrically ergodic, by the application of eq. 11,
$\sum_{k\geq 1}\alpha_{k}^{\delta/(2+\delta)}<+\infty$. The rest of the proof
follows similarly as in the proof of Theorem 4.1, and we obtain an
$\epsilon^{(2)}_{n}\in\mathrm{O}(\frac{n^{\delta/2}}{n})$, such that,

$\displaystyle\int\mathrm{Var}[r_{n}(\theta,\theta_{0})]\rho_{n}(d\theta)<n\epsilon^{(2)}_{n}.$

Since, $\mathcal{K}(\rho_{n},\pi)\leq\sqrt{n}C$, similar arguments as in the
proof of Theorem 3.1 holds. The theorem is thus proved.

∎

###  C.10. Proof of Theorem 4.2

###### Proof.

Verification of condition (i) of Corollary 2.1 As in the proof of Theorem 3.1
substitute the true parameter $\theta_{0}$ for $\theta_{1}$ and $\theta$ for
$\theta_{2}$. We also set our initial distributions $q_{1}^{(0)}$ and
$q_{2}^{(0)}$ to the known initial distribution $q^{(0)}$. A method similar to
Section C.6, yields

$\displaystyle\mathcal{K}(P^{(n)}_{\theta_{0}},P^{(n)}_{\theta})$
$\displaystyle\leq\sum_{i=1}^{n}\sum_{k=1}^{m}\mathrm{E}\left[M^{(1)}_{k}(X_{i},X_{i-1})\right]|f^{(1)}_{k}(\theta,\theta_{0})|.$

Because $M^{(1)}_{k}$s satisfy 4.1, it follows by the application of Theorem
2.3, [12] that $\exists\enspace\lambda>0$ such that for any
$0<\kappa\leq\lambda$, and for some $\zeta\in(0,1)$ possibly depending upon
$\lambda$,

$\displaystyle\mathrm{E}\left[e^{\kappa
M^{(1)}_{k}(X_{i},X_{i-1})}\right|X_{1},X_{0}]\leq\zeta^{i-1}e^{\kappa
M^{(1)}_{k}(X_{1},X_{0})}+\frac{1-\zeta^{i}}{1-\zeta}\mathcal{D}e^{\kappa
a}\quad\text{ for all }i>1.$

We rewrite $\mathrm{E}\left[M^{(1)}_{k}(X_{i},X_{i-1})|X_{1},X_{0}\right]$ as
follows:

$\displaystyle\mathrm{E}\left[M^{(1)}_{k}(X_{i},X_{i-1})|X_{1},X_{0}\right]$
$\displaystyle=\frac{\mathrm{E}[\kappa
M^{(1)}_{k}(X_{i},X_{i-1})|X_{1},X_{0}]}{\kappa}$
$\displaystyle\leq\frac{\mathrm{E}[e^{\kappa
M^{(1)}_{k}(X_{i},X_{i-1})}|X_{1},X_{0}]}{\kappa}.$

Therefore, $\sum_{i=1}^{n}\mathrm{E}\left[M^{(1)}_{k}(X_{i},X_{i-1})\right]$
can be upper bounded as,

$\displaystyle\sum_{i=1}^{n}\mathrm{E}\left[M^{(1)}_{k}(X_{i},X_{i-1})\right]$
$\displaystyle=\sum_{i=1}^{n}\mathrm{E}\left[M^{(1)}_{k}(X_{i},X_{i-1})|X_{1},X_{0}\right]\kappa^{-1}$
$\displaystyle\leq\sum_{i=1}^{n}\left[\zeta^{i-1}\mathrm{E}e^{\kappa
M^{(1)}_{k}(X_{1},X_{0})}+\frac{1-\zeta^{i}}{1-\zeta}\mathcal{D}e^{\kappa
a}\right]\kappa^{-1}.$ Since, $\zeta\in(0,1)$, $\zeta^{i}<1$. Hence, we can
write that, $\displaystyle\sum_{i=1}^{n}\left[\zeta^{i-1}\mathrm{E}e^{\kappa
M^{(1)}_{k}(X_{1},X_{0})}+\frac{1-\zeta^{i}}{1-\zeta}\mathcal{D}e^{\kappa
a}\right]$
$\displaystyle\leq\sum_{i=1}^{n}\left[\zeta^{i-1}\mathrm{E}e^{\kappa
M^{(1)}_{k}(X_{1},X_{0})}+\frac{1}{1-\zeta}\mathcal{D}e^{\kappa
a}\right]\kappa^{-1}$
$\displaystyle=\left[\frac{1-\zeta^{n}}{1-\zeta}\mathrm{E}e^{\kappa
M^{(1)}_{k}(X_{1},X_{0})}+\frac{n}{1-\zeta}\mathcal{D}e^{\kappa
a}\right]\kappa^{-1}$ $\displaystyle\leq nL,$

for a large constant $L$. Therefore
$\int\mathcal{K}(P^{(n)}_{\theta_{0}},P^{(n)}_{\theta})\rho_{n}(d\theta)$ can
be upper bounded as follows,

$\displaystyle\int\mathcal{K}(P^{(n)}_{\theta_{0}},P^{(n)}_{\theta})\rho_{n}(d\theta)$
$\displaystyle\leq\int\sum_{k=1}^{m}nL|f^{(1)}_{k}(\theta,\theta_{0})|\rho_{n}(d\theta)$
$\displaystyle=\sum_{k=1}^{m}nL\int|f^{(1)}_{k}(\theta,\theta_{0})|\rho_{n}(d\theta).$
By 3.1, $\int|f^{(1)}_{k}(\theta,\theta_{0})|\rho_{n}(d\theta)<\frac{C}{n}$,
hence,
$\displaystyle\int\mathcal{K}(P^{(n)}_{\theta_{0}},P^{(n)}_{\theta})\rho_{n}(d\theta)$
$\displaystyle\leq nL\frac{C}{\sqrt{n}}.$

Hence, for some $\epsilon_{n}^{(1)}\in\mathrm{O}(\frac{1}{\sqrt{n}})$, we have
obtained that,
$\int\mathcal{K}(P^{(n)}_{\theta_{0}},P^{(n)}_{\theta})\rho_{n}(d\theta)\leq
n\epsilon_{n}^{(1)}$.

Verification of condition (ii) of Corollary 2.1: Similar to as in the proof of
Theorem 4.1, we upper bound
$\int\mathrm{Var}\left[r_{n}(\theta,\theta_{0})\right]\rho_{n}(d\theta)$ by

(66)
$\displaystyle\int\mathrm{Var}\left[r_{n}(\theta,\theta_{0})\right]\rho_{n}(d\theta)$
$\displaystyle\leq\sum_{i,j=1}^{n}\left(\frac{4}{n}+2n^{\delta/2}(\int
C_{\theta_{0},\theta}^{(i)}\rho_{n}(d\theta)+\int
C_{\theta_{0},\theta}^{(j)}\rho_{n}(d\theta)+\int\sqrt{C_{\theta_{0},\theta}^{(i)}C_{\theta_{0},\theta}^{(j)}}\rho_{n}(d\theta))\right)\left(\alpha_{|i-j|-1}^{\delta/(2+\delta)}\right)$
$\displaystyle\qquad+\sum_{i=1}^{n}\left(\frac{4}{n}+2n^{\delta/2}\int
C_{\theta_{0},\theta}^{(i)}\rho_{n}(d\theta)\right)\left(\alpha_{i-1}^{\delta/(2+\delta)}\right),$

where $C_{\theta_{0},\theta}$ is upper bounded as

$\displaystyle C_{\theta_{0},\theta}^{(i)}$
$\displaystyle\leq\sum_{k=1}^{m}m^{1+\delta}\mathrm{E}\left[M^{(1)}_{k}(X_{i},X_{i-1})\right]^{2+\delta}|f^{(1)}_{k}(\theta,\theta_{0})|^{2+\delta}.$

There exists a constant $C_{\delta}$ depending upon $\delta$ such that,

$\displaystyle[M^{(1)}_{k}]^{2+\delta}(X_{i},X_{i-1})$
$\displaystyle=\frac{\kappa^{2+\delta}[M^{(1)}_{k}]^{2+\delta}(X_{i},X_{i-1})^{2+\delta}}{\kappa^{2+\delta}}$
$\displaystyle\leq\frac{e^{\kappa
M^{(1)}_{k}(X_{i},X_{i-1})}+C_{\delta}}{\kappa^{2+\delta}}.$

By expressing
$\mathrm{E}\left[M^{(1)}_{k}(X_{i},X_{i-1})^{2+\delta}\right]=\mathrm{E}\left[\mathrm{E}\left[M^{(1)}_{k}(X_{i},X_{i-1})^{2+\delta}|X_{1},X_{0}\right]\right]$
and following a method similar to the previous part, we get,

$\displaystyle\mathrm{E}\left[M^{(1)}_{k}(X_{i},X_{i-1})^{2+\delta}\right]$
$\displaystyle\leq\frac{\left[\zeta^{i}\mathrm{E}e^{\kappa
M^{(1)}_{k}(X_{1},X_{0})}+\frac{1-\zeta^{i}}{1-\zeta}\mathcal{D}e^{\kappa
a}\right]+C_{\delta}}{\kappa^{2+\delta}}.$ The fact that $0<\zeta<1$ implies
that $0<\zeta^{i}<\zeta$. This gives us the following,
$\displaystyle\mathrm{E}\left[M^{(1)}_{k}(X_{i},X_{i-1})^{2+\delta}\right]$
$\displaystyle\leq\frac{\left[\zeta\mathrm{E}e^{\kappa
M^{(1)}_{k}(X_{1},X_{0})}+\frac{1}{1-\zeta}\mathcal{D}e^{\kappa
a}\right]+C_{\delta}}{\kappa^{2+\delta}}.$ Since $\kappa<\lambda$, by the
application of Jensen’s inequality, we get
$\displaystyle\mathrm{E}\left[M^{(1)}_{k}(X_{i},X_{i-1})^{2+\delta}\right]$
$\displaystyle\leq\frac{\left[\zeta\mathrm{E}e^{\lambda
M^{(1)}_{k}(X_{1},X_{0})}+\frac{1}{1-\zeta}\mathcal{D}e^{\kappa
a}\right]+C_{\delta}}{\kappa^{2+\delta}}$ $\displaystyle=\frac{\left[\zeta\int
e^{\lambda
M^{(1)}_{k}(x_{1},x_{0})}p_{\theta_{0}}(x_{1}|x_{0})D(x_{0})dx_{1}dx_{0}+\frac{1}{1-\zeta}\mathcal{D}e^{\kappa
a}\right]+C_{\delta}}{\kappa^{2+\delta}}.$

We know that
$\int|f^{(1)}_{k}(\theta,\theta_{0})|^{2+\delta}\rho_{n}(d\theta)<\frac{C}{n}$.
Thus, following 3.1 we can say that, for a large constant $L$, $\int
C_{\theta_{0},\theta}^{(i)}\rho_{n}(d\theta)\leq\frac{L}{n}$. The rest of the
proof follows similarly as in the proof of Theorem 4.1, and we obtain an
$\epsilon^{(2)}_{n}\in\mathrm{O}(\frac{n^{\delta/2}}{n})$, such that,

$\displaystyle\int\mathrm{Var}[r_{n}(\theta,\theta_{0})]\rho_{n}(d\theta)<n\epsilon^{(2)}_{n}.$

Since, $\mathcal{K}(\rho_{n},\pi)\leq\sqrt{n}C$, similar arguments as in the
proof of Theorem 3.1 holds. The theorem is thus proved. ∎

###  C.11. Proof of Proposition 4.3

###### Proof.

For the purpose of the proof, we choose $\rho_{n}$’s with scaled Beta
distribution with parameters $\alpha_{n}=n\frac{1+\theta_{0}}{2}$ and
$\beta_{n}=n\frac{1-\theta_{0}}{2}$. Since, $\rho_{n}$ is a scaled Beta
distribution with the scaling factors $m=2$ and $c=-1$, the pdf of $\rho_{n}$
is given by

$\displaystyle\rho_{n}(\theta)$
$\displaystyle=\frac{2}{\text{Beta}(\alpha_{n},\beta_{n})}\left(\frac{1+\theta}{2}\right)^{\alpha_{n}}\left(\frac{1-\theta}{2}\right)^{\beta_{n}}$

Since this is a scaled distribution,
$E_{\rho_{n}}[\theta]=2\frac{\alpha_{n}}{\alpha_{n}+\beta_{n}}-1=\theta_{0}$
and there exists a constant $\sigma>0$,
$\mathrm{Var}_{\rho_{n}}[\theta]=\frac{\sigma^{2}}{n}$. We now analyse the
log-ratio of the transition probabilities for the Markov chain,

$\displaystyle\log p_{\theta_{0}}(X_{n}|X_{n-1})-\log
p_{\theta}(X_{n}|X_{n-1})=2X_{n}X_{n-1}(\theta-\theta_{0})+X_{n-1}^{2}(\theta_{0}^{2}-\theta^{2}).$

Observe that in this setting, $M^{(1)}_{1}(X_{n},X_{n-1})=|X_{n}X_{n-1}|$ and
$M^{(1)}_{2}(X_{n},X_{n-1})=X_{n}^{2}$. Next, using the fact that

$\displaystyle\mathrm{E}[|X_{n}|^{2+\delta}|X_{n-1}]$
$\displaystyle=\mathrm{E}[|X_{n}-\theta_{0}X_{n-1}+\theta_{0}X_{n-1}|^{2+\delta}|X_{n-1}],$
and by an application of triangle inequality, we obtain
$\displaystyle\mathrm{E}[|X_{n}|^{2+\delta}|X_{n-1}]$
$\displaystyle\leq\mathrm{E}\left[\left(|X_{n}-\theta_{0}X_{n-1}|+|\theta_{0}X_{n-1}|\right)^{2+\delta}|X_{n-1}\right]$
$\displaystyle=\mathrm{E}\left[\left(2\frac{|X_{n}-\theta_{0}X_{n-1}|+|\theta_{0}X_{n-1}|}{2}\right)^{2+\delta}|X_{n-1}\right]$
$\displaystyle=\mathrm{E}\left[2^{2+\delta}\left(\frac{|X_{n}-\theta_{0}X_{n-1}|+|\theta_{0}X_{n-1}|}{2}\right)^{2+\delta}|X_{n-1}\right].$
Now by using Jensen’s inequality we get,
$\displaystyle\mathrm{E}[|X_{n}|^{2+\delta}|X_{n-1}]$
$\displaystyle\leq\mathrm{E}\left[2^{2+\delta}\left(\frac{|X_{n}-\theta_{0}X_{n-1}|^{2+\delta}+|\theta_{0}X_{n-1}|^{2+\delta}}{2}\right)|X_{n-1}\right]$
$\displaystyle=2^{1+\delta}\mathrm{E}\left[|X_{n}-\theta_{0}X_{n-1}|^{2+\delta}|X_{n-1}\right]+2^{1+\delta}|\theta_{0}X_{n-1}|.$

We know if $Y\sim N(\mu,\sigma^{2})$, then
$\mathrm{E}|Y-\mu|^{p}=\sigma^{p}\frac{2^{\frac{p}{2}\Gamma(\frac{p+1}{2})}}{\sqrt{\pi}}$.
Consequently,

(67) $\displaystyle\leavevmode\nobreak\
\mathrm{E}[|X_{n}|^{2+\delta}|X_{n-1}]$ $\displaystyle\leq
2^{1+\delta}\left[\frac{2^{\frac{2+\delta}{2}\Gamma(\frac{3+\delta}{2})}}{\sqrt{\pi}}\right]+2^{1+\delta}|\theta_{0}X_{n-1}|^{2+\delta}.$

It follows that,

$\displaystyle\mathrm{E}[M^{(1)}_{1}(X_{n},X_{n-1})^{2+\delta}|X_{n-1}]$
$\displaystyle\leq
2^{1+\delta}\left[\frac{2^{\frac{2+\delta}{2}\Gamma(\frac{3+\delta}{2})}}{\sqrt{\pi}}\right]|X_{n-1}|^{2+\delta}+2^{1+\delta}|\theta_{0}|^{2+\delta}|X_{n-1}|^{4+2\delta}$
$\displaystyle\leq\left(2^{1+\delta}\left[\frac{2^{\frac{2+\delta}{2}\Gamma(\frac{3+\delta}{2})}}{\sqrt{\pi}}\right]+2^{1+\delta}|\theta_{0}|^{2+\delta}\right)(|X_{n-1}|^{4+2\delta}+1).$
Since $\theta_{0}<1$, we can say,
$\displaystyle\mathrm{E}[M^{(1)}_{1}(X_{n},X_{n-1})^{2+\delta}|X_{n-1}]$
$\displaystyle\leq\left(2^{1+\delta}\left[\frac{2^{\frac{2+\delta}{2}\Gamma(\frac{3+\delta}{2})}}{\sqrt{\pi}}\right]+2^{1+\delta}\right)(|X_{n-1}|^{4+2\delta}+1).$
Define a constant
$C_{\delta}:=\left(2^{1+\delta}\left[\frac{2^{\frac{2+\delta}{2}\Gamma(\frac{3+\delta}{2})}}{\sqrt{\pi}}\right]+2^{1+\delta}\right)$.
The above term then becomes,