# Large Deviations for Empirical Measures of Self-Interacting Markov Chains

Amarjit Budhiraja, Adam Waterbury, Pavlos Zoubouloglou

###### Abstract

Let $\Delta^{o}$ be a finite set and, for each probability measure $m$ on
$\Delta^{o}$, let $G(m)$ be a transition probability kernel on $\Delta^{o}$.
Fix $x_{0}\in\Delta^{o}$ and consider the chain
$\\{X_{n},\;n\in\mathbb{N}_{0}\\}$ of $\Delta^{o}$-valued random variables
such that $X_{0}=x$, and given $X_{0},\ldots,X_{n}$, the conditional
distribution of $X_{n+1}$ is $G(L^{n+1})(X_{n},\cdot)$, where
$L^{n+1}=\frac{1}{n+1}\sum_{i=0}^{n}\delta_{X_{i}}$ is the empirical measure
at instant $n$. Under conditions on $G$ we establish a large deviation
principle for the empirical measure sequence $\\{L^{n},\;n\in\mathbb{N}\\}$.
As one application of this result we obtain large deviation asymptotics for
the Aldous-Flannery-Palacios (1988) approximation scheme for quasi-stationary
distributions of irreducible finite state Markov chains. The conditions on $G$
cover various other models of reinforced stochastic evolutions as well,
including certain vertex reinforced and edge reinforced random walks and a
variant of the PageRank algorithm. The particular case where $G(m)$ does not
depend on $m$ corresponds to the classical results of Donsker and Varadhan
(1975) on large deviations of empirical measures of Markov processes. However,
unlike this classical setting, for the general self-interacting models
considered here, the rate function takes a very different form; it is
typically non-convex and is given through a dynamical variational formula with
an infinite horizon discounted objective function.

Keywords: reinforced random walks, quasi-stationary distributions, empirical
measure, large deviations, stochastic approximations, self-interacting Markov
chains, multiscale systems.

##  1 Introduction

In this work we are interested in the large deviations behavior of certain
types of self-interacting Markov chains. The terminology ‘Markov chain’ is in
fact a misnomer as these processes are very far from being Markovian, and the
conditional law of the state at the next time instant, given the past, depends
on the whole history of the process through its empirical distribution. The
general setting is as follows. Consider a finite set
$\Delta^{o}\doteq\\{1,\ldots,d\\}$ and let $G$ be a map from
$\mathcal{P}(\Delta^{o})$ (the space of probability measures on $\Delta^{o}$)
to the space $\mathcal{K}(\Delta^{o})$ of transition probability kernels on
$\Delta^{o}$. Fix $x_{0}\in\Delta^{o}$ and let
$\\{X_{n},\;n\in\mathbb{N}_{0}\\}$ be a sequence of $\Delta^{o}$-valued random
variables defined recursively as follows: $X_{0}=x_{0}$, and given
$X_{0},\ldots,X_{n}$, the conditional law of $X_{n+1}$ is
$G(L^{n+1})(X_{n},\cdot)$, where
$L^{n+1}\doteq\frac{1}{n+1}\sum_{i=0}^{n}\delta_{X_{i}}$ is the empirical
measure at time instant $n$. Many types of reinforced stochastic dynamical
systems fall within this framework and such processes arise in several
different contexts, e.g., Monte-Carlo methods for quasi-stationary
distributions [1, 5, 9], population growth models in mathematical ecology [33,
34], self organization in dynamical models of social networks, models for
random monopolies in economics, models for neuron growth, bandit problems in
sequential analysis, generalized Pólya’s urn models, and many others; see the
excellent survey by Pemantle [31] for discussion of these diverse
applications. Using techniques from stochastic approximation theory and
branching processes, under suitable conditions on $G$, law of large numbers
and central limit results for the empirical measure sequence
$\\{L^{n},\;n\in\mathbb{N}\\}$ have been studied in various works [1, 5, 7,
31]. The goal of the current work is to establish a large deviation principle
(LDP) for the sequence $\\{L^{n},\;n\in\mathbb{N}\\}$ under a broad set of
conditions on the map $G$. Our main result, Theorem 2.4 provides a large
deviation upper bound only requiring that the map $G$ is Lipschitz (Assumption
2.1). Furthermore, this theorem shows that under a stronger condition
(Assumption 2.2) the matching large deviation lower bound holds as well, thus
establishing a LDP for $\\{L^{n},\;n\in\mathbb{N}\\}$. Assumption 2.2 imposes
four main conditions on the model: The first condition says that $G$ is an
affine map; the second condition imposes a natural communicability structure
on the transition probability matrix $G(m)$ for $m\in\mathcal{P}(\Delta^{o})$;
the third condition requires that the fixed point equation
$\pi^{*}G(\pi^{*})=\pi^{*}$ admits a strictly positive solution in
$\mathcal{P}(\Delta^{o})$; and, finally, the fourth condition says that the
empirical measure $L^{n}$ eventually charges all points in $\Delta^{o}$, a.s.
As discussed in Example 2.6, Remark 2.3, and Section 8, these conditions are
satisfied for many interesting settings.

One of the main motivating applications for this work is the reinforced Markov
chain Monte-Carlo scheme for approximating quasi-stationary distributions
(QSD) of finite state Markov chains that was introduced in the work of Aldous
et al.[1]. For an overview of QSD, see [18] and see Example 2.6 for a precise
definition of a QSD. Let $P$ be the transition kernel of a
$\Delta=\Delta^{o}\cup\\{0\\}$-valued Markov chain that is absorbed at $0$,
and consider the substochastic kernel $P^{o}$ obtained by restricting $P$ to
$\Delta^{o}$. Suppose that $P^{o}$ is irreducible. Then, there is a unique QSD
of $P$ which is characterized as the normalized Perron-Frobenius eigenvector
of $P^{o}$. The QSD captures the long-term pre-absorption behavior of the
Markov chain with transition kernel $P$, consequently, QSD are widely used to
understand metastability behavior of stochastic systems in ecology and biology
[13, 25, 26], chemical kinetics [30, 32], epidemiology [2, 3, 4], and other
fields. In particular numerical approximation of QSD is of significant
interest. Various numerical methods have been proposed to approximate QSD, and
one important family of methods are described in terms of self-interacting
chains [1, 5, 9, 17]. The precise description of this approximation scheme is
recalled in Example 2.6; here we merely note that the scheme corresponds to
simulating a self-interacting Markov chain for which the function $G$ is given
as $G(m)(x,y)\doteq P(x,y)+P(x,0)m(y)$, for $x,y\in\Delta^{o}$, and
$m\in\mathcal{P}(\Delta^{o})$. The law of large numbers (LLN) for the
empirical measure sequence $\\{L^{n},\;n\in\mathbb{N}\\}$ associated with this
Monte-Carlo method giving a.s. convergence to the QSD has been established in
[1, 5]. Under exactly the conditions for the LLN, the current work establishes
a LDP for this sequence. Beyond this example, as discussed in Section 8, the
Assumptions of Theorem 2.4 cover many other types of self-interacting Markov
chains as well, including certain variants of edge reinforced and vertex
reinforced random walks, a type of personalized PageRank algorithm, and
certain generalized Pólya urn schemes.

In the special case where $G(m)=P^{o}$ is independent of $m$, the LDP in the
current work reduces to the classical empirical measure LDP for finite state
Markov chains [19, 20]. As is well known, in this case the rate function takes
the following simple form

$\tilde{I}(m)=\inf_{\gamma\in\mathcal{I}(m)}R(\gamma\|m\otimes
P^{o}),\;m\in\mathcal{P}(\Delta^{o}),$ (1.1)

where
$\mathcal{I}(m)\doteq\\{\gamma\in\mathcal{P}(\Delta^{o}\times\Delta^{o}):\gamma(\Delta^{o}\times\cdot)=\gamma(\cdot\times\Delta^{o})=m(\cdot)\\}$,
$m\otimes P^{o}\in\mathcal{P}(\Delta^{o}\times\Delta^{o})$ is defined as
$m\otimes P^{o}(x,y)=m(x)P^{o}(x,y)$, $x,y\in\Delta^{o}$, and $R$ is the
relative entropy function. This rate function can be interpreted as saying
that the most likely way the empirical measure is asymptotically close to a
given probability measure $m$ is for the realization of the sequence
$\\{X_{n},\;n\in\mathbb{N}_{0}\\}$ to behave like that from a Markov chain
with transition probability kernel $\gamma_{2|1}(\cdot\mid\cdot)$, where with
$x,y\in\Delta^{o}$, $\gamma(x,y)=\gamma_{2|1}(y\mid x)m(x)$ defines the
disintegration of the probability measure $\gamma$ that achieves the infimum
in the above variational formula. Indeed, this insight and an appropriate use
of the ergodic theorem are the key ingredients in the proof of the large
deviation lower bound in this classical setting. In contrast, for the self-
interacting Markov chains considered in the current work, the atypical
behaviors for which the empirical measure sequence is asymptotically close to
a given $m\in\mathcal{P}(\Delta^{o})$ are significantly more complex. Roughly
speaking, after a long period of time, the suitably interpolated path
constructed from the empirical measure sequence $\\{L^{n},\;n\in\mathbb{N}\\}$
behaves like a trajectory, with a linear velocity, that converges to $m$ and
whose evolution is governed by certain dynamic local equilibria associated
with time-dependent transition probability kernels on
$\Delta^{o}\times\Delta^{o}$ (cf. (P2), (P3)). The instantaneous local
averaging that is manifested in the form of the rate function is somewhat akin
to the forms of rate functions for large deviations from stochastic averaging
principles for multiscale stochastic dynamical systems [15, 22, 35]. This
atypical behavior that produces a given $m\in\mathcal{P}(\Delta^{o})$ can be
seen from the definition of the rate function $I$ in (2.7), which is described
in terms of time-reversal of such linear paths, so that the convergence to $m$
at $\infty$ is replaced with the initial condition of the path being equal to
$m$. The infinite horizon discount in the variational formula for the rate
function arises due to the natural time interpolation that is associated with
the discrete evolution of $L^{n}$ with steps of sizes $1/(n+1)$ (see (3.2)).
Such time interpolation is quite standard in the asymptotic analysis of
stochastic approximation schemes [6, 8, 10, 28] and indeed a discounted cost
has been previously observed in a rate function for certain large deviation
problems arising from some stochastic approximation schemes with Gaussian
noises [29]. We remark that in the special case when $G(m)=P^{o}$ (i.e.,
$G(m)$ is independent of $m$), the rate function in (2.7) is easily seen to
reduce to the classical formula in (1.1) (see Example 1 in Section 8). We also
note that the natural analogue of $\tilde{I}$ in the general self-interacting
setting, defined as

$\tilde{I}(m)=\inf_{\gamma\in\mathcal{I}(m)}R(\gamma\|m\otimes
G(m)),\;m\in\mathcal{P}(\Delta^{o}),$ (1.2)

satisfies the inequality $I(m)\leq\tilde{I}(m)$,
$m\in\mathcal{P}(\Delta^{o})$; see Remark 2.5.

We now make some comments on proof techniques. The basic idea is to use
stochastic control representations for Laplace functionals of the form in
(3.11) [14, 21]. Using this variational formula, the proof of the upper bound
proceeds via natural tightness and weak convergence arguments. The main
challenges and novelty are in the proof of the large deviation lower bound and
so we limit our remarks to this inequality. The basic idea is to choose a
near-optimal control $\eta$, and the corresponding trajectory $M$ given
through (P3), in the variational formula for the rate function $I(m)$ in
(2.7), and then construct controlled empirical measures as in (3.2) that
suitably approximate $M$ and for which the associated cost, as given by the
second term on the right side of (3.11), appropriately approximates the cost
associated with $\eta$ in (2.7). However, such a construction for an arbitrary
near-optimal control $\eta$ appears quite daunting, mainly due to the local
equilibrium property (P2) that the constructed stochastic controls are
required to achieve asymptotically. In order to handle this, we proceed by a
series of approximations that lead to a ‘well behaved’ simple form near-
optimal control that is more tractable for a suitable construction of
controlled empirical measures. This is the main content of Section 5. Next, in
Section 6 we proceed to the construction of controlled empirical measures that
are designed to suitably approximate the simple form near-optimal path
constructed in Section 5. This construction and proof of convergence are
technically the most involved part of the proof. Detailed discussion of the
construction can be found at the start of Section 6, but at a high level the
idea is to employ the ergodic theorem in a dynamic fashion to successively
approximate all the local equilibria that make up the simple form control
$\eta$ using suitably controlled empirical measures in such a manner that the
associated costs also have the correct asymptotic behavior.

Finally, we discuss some related literature on large deviations. The model
that we consider can be formulated as a type of urn model. Large deviations
for a family of urn models (that are very different from the one considered
here) have been studied in [23]. The paper [12] studies large deviations
associated with a preferential attachment random graph by viewing it as a
special type of an urn model. In the case $d=2$, large deviations for certain
generalized Pólya urns have been studied in [24]. For a special choice of the
‘urn function’ in [24], this model reduces to a model of the form considered
in the current work with $d=2$ and $G(m)(x,y)=(mP^{o})(y)$,
$x,y\in\Delta^{o}$, $m\in\mathcal{P}(\Delta^{o})$ where $P^{o}$ is a $2\times
2$ transition probability matrix with strictly positive entries. Large
deviations for a similar model but with a general $d$ was recently studied in
[16] under the condition that $P^{o}(x,y)>0$ for all $x,y\in\Delta^{o}$. The
proofs in the latter paper also use stochastic control representations as in
the current work, however the arguments there are significantly simpler due to
fact that $G(m)(x,y)$ does not depend on $x$; in particular the main technical
challenge of time varying equilibria does not arise in [16]. In fact as a
corollary of the current work we obtain a substantial extension of the result
in [16] where the condition $P^{o}(x,y)>0$ for all $x,y\in\Delta^{o}$ is
relaxed to the requirement that $P^{o}$ is an irreducible transition
probability matrix (see Section 8, Example 2). Our results also cover certain
types of edge reinforced random walks (see Section 8, Example 5). Some results
on large deviations for specific kinds of edge reinforced random walks (once-
reinforced random walks) can be found in [27] and [37].

###  1.1 Outline

This paper is organized as follows. In Section 1.2 we introduce some notation
that is used throughout this work. In Section 2 we introduce the model of
interest, state our main large deviation result (Theorem 2.4), and provide one
basic example that motivates this study. In Section 3 we present the
stochastic control representation that is used to in the proof of Theorem 2.4;
both in proving the large deviation upper bound and lower bound. The large
deviation upper bound is proved in Section 4. In Section 5, through
appropriate perturbation, mollification, and discretization, we construct
simple form near-optimal trajectories and controls that are tractable for
constructing suitable controlled empirical measures for the proof of the large
deviation lower bound. In Section 6 we proceed with this construction and
provide the proof of the convergence of the controlled processes and costs,
which finishes the proof of the large deviation lower bound. In Section 7 we
show that the function $I$ introduced in (2.7) is a rate function, namely it
has compact sublevel sets. Finally in Section 8 we present several examples
for which the assumptions of Theorem 2.4 are satisfied.

###  1.2 Notation

In this section we introduce some notation that is used throughout this work.
Fix $d\in\mathbb{N}$, and let $\Delta^{o}=\\{1,\ldots,d\\}$. For a metric
space $S$, $\mathcal{B}(S)$ denotes the corresponding Borel $\sigma$-field and
$\mathcal{P}(S)$ denotes the space of probability measures on
$(S,\mathcal{B}(S))$ equipped with the topology of weak convergence. When $S$
is a finite set, we let
$\mathcal{P}_{+}(S)\doteq\left\\{m\in\mathcal{P}(S):\min_{x\in
S}m(x)>0\right\\}$. Recall that a function $I:S\to[0,\infty]$ is called a rate
function if it has compact sublevel sets, namely $S_{k}\doteq\\{x\in
S:I(x)\leq k\\}$ is compact for every $k\in[0,\infty)$. For $x\in S$,
$\delta_{x}\in\mathcal{P}(S)$ denotes the Dirac probability measure
concentrated at $x$. For a probability measure $\eta$ on $S_{1}\times
S_{2}\times S_{3}$, $\eta_{(i)}$ denotes the marginal distribution of $\eta$
on $S_{i}$, $i=1,2,3$, and for $i<j$, $\eta_{(i,j)}$ denotes the marginal
distribution of $\eta$ on $S_{i}\times S_{j}$. Similar notation is used for
probability measures on other product spaces. For $\mu,\nu\in\mathcal{P}(S)$,
we denote the relative entropy of $\nu$ with respect to $\mu$ as
$R(\nu\|\mu)$, which is the extended real number defined as

$R(\nu\|\mu)\doteq\int_{S}\left(\log\frac{d\nu}{d\mu}\right)d\nu,$

if $\nu$ is absolutely continuous with respect to $\mu$, and $+\infty$
otherwise. Let $\mathcal{V}^{d}\doteq\\{e_{1},\ldots,e_{d}\\}$, where $e_{x}$
is the $x$-th unit coordinate vector in $\mathbb{R}^{d}$. For a locally
compact space $S$, let $\mathcal{M}(S)$ denote the space of locally finite
measures on $S$ equipped with the vague topology. We denote by
$C_{b}(\mathcal{P}(\Delta^{o}))$ the space of bounded continuous functions
from $\mathcal{P}(\Delta^{o})$ to $\mathbb{R}$. For
$m,\tilde{m}\in\mathcal{P}(\Delta^{o})$, we write
$\|m-\tilde{m}\|\doteq\sum_{x\in\Delta^{o}}|m(x)-\tilde{m}(x)|$, and we use
the same notation for the norm of a vector in $\mathbb{R}^{d}$. For a Polish
space $S$, $C([0,\infty):S)$ will denote the space of continuous functions
from $[0,\infty)$ to $S$, equipped with the topology of local uniform
convergence. As a convention $\int_{a}^{b}f(s)ds$ is taken to be $0$ if $a\geq
b$ and $\sum_{i=k}^{j}a_{i}$ is taken to be $0$ if $k>j$. For
$v\in\mathbb{R}^{d}$ we use $v_{x}$ and $v(x)$ interchangeably to denote the
$x$-th coordinate of $v$. A transition kernel $K$ on a finite set $S$ is a map
$K:S\times S\to[0,1]$ such that $\sum_{y\in S}K(x,y)=1$ for all $x\in S$. For
such a kernel and $x,y\in S$, we use $K_{x,y}$ and $K(x,y)$ interchangeably,
and we write $\mathcal{K}(S)$ to denote the set of transition kernels on $S$.
We write $I_{d}$ to denote the $d\times d$ identity matrix. For a matrix $A$,
we write $A>0$ to denote that all of its entries are strictly positive.
Finally, we write $\mathbb{R}_{+}$ to denote $[0,\infty)$.

##  2 Setting and Main Result

###  2.1 Description of the Model

Consider a map $G:\mathcal{P}(\Delta^{o})\to\mathcal{K}(\Delta^{o})$ and fix
$x_{0}\in\Delta^{o}$. We consider a collection
$\\{X_{n},\;n\in\mathbb{N}_{0}\\}$ of $\Delta^{o}$-valued random variables, a
collection $\\{L^{n},\;n\in\mathbb{N}\\}$ of $\mathcal{P}(\Delta^{o})$-valued
random measures, and a filtration $\\{\mathcal{F}_{n},\;n\in\mathbb{N}_{0}\\}$
on some probability space $(\Omega,\mathcal{F},P)$, defined recursively as
follows. Let $X_{0}\doteq x_{0}$,
$\mathcal{F}_{0}\doteq\\{\emptyset,\Omega\\}$, and
$L^{1}\doteq\delta_{x_{0}}$. Having defined $\\{X_{i},L^{i+1},\;0\leq i\leq
n\\}$ and $\sigma$-fields $\\{\mathcal{F}_{i},\;i\leq n\\}$ for some
$n\in\mathbb{N}_{0}$, define

$P(X_{n+1}=y\mid\mathcal{F}_{n})\doteq
G(L^{n+1})_{X_{n},y},\;\;y\in\Delta^{o},$

$\mathcal{F}_{n+1}\doteq\sigma\\{X_{k},\;k\leq n+1\\}$, and

$L^{n+2}\doteq\frac{1}{n+2}\sum\limits_{i=0}^{n+1}\delta_{X_{i}}.$ (2.1)

###  2.2 Statement of Results

We introduce the following two assumptions on the operator $G$.

######  Assumption 2.1.

[Lipschitz Continuity] There is $L_{G}\in(0,\infty)$ such that for all
$m,\tilde{m}\in\mathcal{P}(\Delta^{o})$,

$\sum\limits_{x,y\in\Delta^{o}}|G(m)_{x,y}-G(\tilde{m})_{x,y}|\leq
L_{G}\|m-\tilde{m}\|.$ (2.2)

The above assumption is the only requirement for the large deviation upper
bound. A $d\times d$ matrix $A$ is called an adjacency matrix if it has
entries $0$ or $1$; and it is called an irreducible adjacency matrix if for
each $x,y\in\Delta^{o}$ there is a $m\in\mathbb{N}$ such that $A^{m}(x,y)>0$.

We denote by $\mathcal{A}$ the collection of all adjacency matrices $A$ that
have the property that, for each $(x,y)\in\Delta^{o}\times\Delta^{o}$,
$A(x,y)=0$ implies $G(m)(x,y)=0$ for all $m\in\mathcal{P}(\Delta^{o})$. We
write

$A_{+}\doteq\\{(x,y)\in\Delta^{o}\times\Delta^{o}:A_{x,y}=1\\}.$ (2.3)

Note that the class $\mathcal{A}$ is nonempty as it contains the matrix with
all ones (in that case the above property is vacuously true). In fact we will
establish a collection of large deviation upper bounds, one for each choice of
$A\in\mathcal{A}$.

For the lower bound we need additional assumptions as follows, which in
particular associate a ‘minimal’ $A$ associated with the map $G$.

######  Assumption 2.2.

  1. 1.

[Linearity] For all $\kappa\in[0,1]$ and
$m,\tilde{m}\in\mathcal{P}(\Delta^{o})$,

$G(\kappa m+(1-\kappa)\tilde{m})=\kappa G(m)+(1-\kappa)G(\tilde{m}).$

  2. 2.

[Communication Structure] There is an irreducible adjacency matrix $A$ such
that the following hold:

    1. (a)

$A\in\mathcal{A}$.

    2. (b)

There is a $\delta_{0}^{A}\in(0,\infty)$ such that if $(x,y)\in A_{+}$, then

$G(m)_{x,y}\geq\delta_{0}^{A}\min_{z\in\Delta^{o}}m_{z},\;\;m\in\mathcal{P}(\Delta^{o}).$

  3. 3.

[Positive Fixed Point] There is a $\pi^{*}\in\mathcal{P}_{+}(\Delta^{o})$ such
that $\pi^{*}G(\pi^{*})=\pi^{*}$.

  4. 4.

[Nondegeneracy of Empirical measure] For every $x\in\Delta^{o}$

$P(\omega\in\Omega:\mbox{ for some }n\in\mathbb{N},L^{n}(\omega)(x)>0)=1.$

######  Remark 2.3.

  1. 1.

Note that Assumption 2.2 (1) implies that Assumption 2.1 holds with $L_{G}=1$.

  2. 2.

In many examples of interest we will have that a strong law of large numbers
holds and that the limiting measure is non-degenerate, namely
$L^{n}\to\pi^{*}$ a.s. for some $\pi^{*}\in\mathcal{P}_{+}(\Delta^{o})$ as
$n\to\infty$. In such a case, Assumption 2.2 (4) clearly holds. Also, in such
a case, is easy to verify that $\pi^{*}$ is a fixed point, namely
$\pi^{*}G(\pi^{*})=\pi^{*}$. Thus, Assumption 2.2 (3) holds as well.

  3. 3.

Consider the map $T:\mathcal{P}(\Delta^{o})\to\mathcal{P}(\Delta^{o})$ given
by $Tm\doteq mG(m)$. Since $\mathcal{P}(\Delta^{o})$ is compact and convex,
Assumption 2.2 and Brouwer’s fixed point theorem ensure that there is some
$\pi^{*}\in\mathcal{P}(\Delta^{o})$ such that
$T\pi^{*}=\pi^{*}G(\pi^{*})=\pi^{*}$. In addition, in many situations of
interest $G(m)$ will be an irreducible transition probability kernel for all
$m\in\mathcal{P}(\Delta^{o})$. In such cases we have in fact that
$\pi^{*}\in\mathcal{P}_{+}(\Delta^{o})$ and so Assumption 2.2 (3) holds.
Suppose the following stronger form of irreducibility holds:

$\mbox{ For some }K\in\mathbb{N}\mbox{ and all
}m_{1},\ldots,m_{K}\in\mathcal{P}(\Delta^{o}),\;\;\sum_{j=1}^{K}G(m_{1})G(m_{2})\cdots
G(m_{j})>0.$ (2.4)

Then, as shown in Lemma A.2 in the Appendix, in this case Assumption 2.2 (4)
holds as well.

In Section 8 we present several examples for which the assumptions of Theorem
2.4 are satisfied; see also Example 2.6 below.

We now introduce the rate function that governs the large deviation
asymptotics. This function will be defined in terms of a matrix
$A\in\mathcal{A}$ but this dependence will be suppressed in the notation.

Let

$\displaystyle\mathcal{P}^{*}(\Delta^{o})$
$\displaystyle\doteq\\{m\in\mathcal{P}(\Delta^{o}):\mbox{ for some
}\bar{m}\in\mathcal{P}(\Delta^{o}\times\Delta^{o}),$ (2.5)
$\displaystyle\quad\quad\bar{m}_{(2)}=\bar{m}_{(1)}=m\mbox{ and
}\bar{m}(x,y)=0\mbox{ for all }(x,y)\in(A_{+})^{c}\\}.$

The class $\mathcal{P}^{*}(\Delta^{o})$ consists of all probability measures
$m$ that are invariant measures for some transition probability kernel for
which, at each state charged by $m$, jumps can only occur to neighbors as
defined by the adjacency matrix $A$. Let $\mathcal{U}$ denote the collection
of all measurable maps from $\mathbb{R}_{+}$ to
$\mathcal{P}(\Delta^{o}\times\Delta^{o})$. Fix $m\in\mathcal{P}(\Delta^{o})$
and suppose that a $\eta\in\mathcal{U}$ satisfies the following properties:

  1. (a)

For $x,y\in\Delta^{o}$ and $t\in\mathbb{R}_{+}$, let

$\beta(\\{x\\}\times\\{y\\}\times[0,t])\doteq\int_{0}^{t}\eta(\\{x\\}\times\\{y\\},s)ds.$

Then,

$\beta(\\{x\\}\times\\{y\\}\times[0,t])=0,\;\;\text{for all
}\;(x,y)\in(A_{+})^{c}\mbox{ and }t\in\mathbb{R}_{+}.$ (P1)

  2. (b)

For a.e. $s\in\mathbb{R}_{+}$, the two marginals of $\eta(\cdot\mid s)$ are
the same, namely, disintegrating $\eta(x,y\mid
s)\doteq\eta(\\{x\\}\times\\{y\\},s)$ as

$\eta(x,y\mid s)=\eta_{(1)}(x\mid s)\eta_{2|1}(y\mid s,x),$

we have

$\begin{split}\eta_{(1)}(x\mid s)&=\sum_{z\in\Delta^{o}}\eta(z,x\mid
s)\doteq\eta_{(2)}(x\mid s),\mbox{ for all }x\in\Delta^{o},\mbox{ a.e.
}s\in\mathbb{R}_{+}.\end{split}$ (P2)

  3. (c)

If $M:\mathbb{R}_{+}\to\mathbb{R}^{d}$ satisfies,

$M(t)=m-\int_{0}^{t}\eta_{(1)}(s)ds+\int_{0}^{t}M(s)ds,\;\;t\in\mathbb{R}_{+},$
(P3)

where $\eta_{(1)}(s)\doteq\eta_{(1)}(\cdot\mid s)$, then $M\in
C(\mathbb{R}_{+}:\mathcal{P}(\Delta^{o}))$. Furthermore, there is a
$\mathcal{T}\in C(\mathbb{R}_{+}:\mathcal{P}(\Delta^{o}\times\Delta^{o}))$
satisfying, for all $s,t\in\mathbb{R}_{+}$,
$\|\mathcal{T}(t)-\mathcal{T}(s)\|\leq 2|t-s|$,
$M(t)=(\mathcal{T}(t))_{(1)}=(\mathcal{T}(t))_{(2)}$, and
$\mathcal{T}(t)(x,y)=0$ for all $(x,y)\in(A_{+})^{c}$. In particular, for all
$t\in\mathbb{R}_{+}$, $M(t)\in\mathcal{P}^{*}(\Delta^{o})$.

Let

$\mathcal{U}(m)=\\{\eta\in\mathcal{U}:\eta\>\text{satisfies}\>(a),(b),(c)\\}.$
(2.6)

Note that for each $\eta\in\mathcal{U}$ and $m\in\mathcal{P}(\Delta^{o})$,
there is a unique $M\in C(\mathbb{R}_{+}:\mathbb{R}^{d})$ that solves (P3);
however, for $\eta$ to belong to $\mathcal{U}(m)$ we require the stronger
condition that for each $t\geq 0$, $M(t)\in\mathcal{P}^{*}(\Delta^{o})$. If,
for some $m\in\mathcal{P}(\Delta^{o})$ and $\eta\in\mathcal{U}(m)$, we have
that $M\in C(\mathbb{R}_{+}:\mathcal{P}(\Delta^{o}))$ solves (P3), we say that
$M$ solves $\mathcal{U}(m,\eta)$.

For $m\in\mathcal{P}(\Delta^{o})$, define
$I:\mathcal{P}(\Delta^{o})\to[0,\infty]$ as

$I(m)\doteq\inf_{\eta\in\mathcal{U}(m)}\int_{0}^{\infty}\exp(-s)\sum_{x\in\Delta^{o}}\eta_{(1)}(x\mid
s)R\left(\eta_{2|1}(\cdot\mid s,x)\|G(M(s))(x,\cdot)\right)ds,$ (2.7)

where $M$ solves $\mathcal{U}(m,\eta)$. By the chain rule for relative entropy
and (P2),

$I(m)=\inf_{\eta\in\mathcal{U}(m)}\int_{0}^{\infty}\exp(-s)R\left(\eta(\cdot\mid
s)\|\eta_{(1)}(\cdot\mid s)\otimes G(M(s))(\cdot,\cdot)\right)ds,$ (2.8)

where $\eta_{(1)}(\cdot\mid s)\otimes
G(M(s))(\cdot,\cdot)\in\mathcal{P}(\Delta^{o}\times\Delta^{o})$ is defined as

$\eta_{(1)}(\cdot\mid s)\otimes
G(M(s))(\\{x\\}\times\\{y\\})\doteq\eta_{(1)}(x\mid
s)G(M(s))_{x,y},\;\;x,y\in\Delta^{o}.$

The following theorem is the main result of this work, which establishes a
Large Deviation Principle (LDP) for $\\{L^{n},\;n\in\mathbb{N}\\}$.

######  Theorem 2.4.

Fix $A\in\mathcal{A}$ and let $I:\mathcal{P}(\Delta^{o})\to[0,\infty]$ be the
function defined in (2.7). Suppose that Assumption 2.1 is satisfied. Then $I$
is a rate function and the sequence $\\{L^{n+1},\;n\in\mathbb{N}_{0}\\}$
defined in (2.1) satisfies the LDP upper bound with rate function $I$, namely,
for each closed set $F\subseteq\mathcal{P}(\Delta^{o})$,

$\limsup_{n\to\infty}n^{-1}\log P(L^{n+1}\in F)\leq-\inf_{m\in F}I(m).$

Suppose in addition that Assumption 2.2 is satisfied. Then, the LDP lower
bound holds as well, with the rate function $I$ and the adjacency matrix $A$
given as in Assumption 2.2, namely, for each open set
$G\subseteq\mathcal{P}(\Delta^{o})$,

$\liminf_{n\to\infty}n^{-1}\log P(L^{n+1}\in G)\geq-\inf_{m\in G}I(m).$

###### Proof.

Large deviation upper and lower bounds are proved in Theorem 4.1 and Theorem
5.1 respectively. In Section 7 we show that $I$ is a rate function, namely it
has compact sublevel sets. ∎

######  Remark 2.5.

Recall the function $\tilde{I}$ from (1.2). We now show that
$I(m)\leq\tilde{I}(m)$ for all $m\in\mathcal{P}(\Delta^{o})$. Without loss of
generality suppose that $\tilde{I}(m)<\infty$ and consider
$\gamma\in\mathcal{I}(m)$ with $R(\gamma\|m\otimes G(m))<\infty$. Then we must
have that $\gamma(x,y)=0$ for all $(x,y)\in(A_{+})^{c}$. Thus, if we define
$\eta\in\mathcal{U}$ by $\eta(\cdot\mid s)\doteq\gamma$ for all
$s\in\mathbb{R}_{+}$, then $\eta$ satisfies (P1) and (P2). Furthermore, since
$\eta_{(1)}(s)=\gamma_{(1)}=m$, (P3) is satisfied with $M(t)=m$,
$t\in\mathbb{R}_{+}$. This shows that $\eta\in\mathcal{U}(m)$ and that $M$
solves $\mathcal{U}(m,\eta)$. Note that the cost on the right side of (2.7),
with this choice of $\eta\in\mathcal{U}(m)$, is

$\int_{0}^{\infty}\exp(-s)R\left(\gamma\|\gamma_{(1)}\otimes
G(m)\right)ds=R\left(\gamma\|m\otimes G(m)\right).$

Thus, $I(m)\leq R\left(\gamma\|m\otimes G(m)\right)$, from which the
inequality $I(m)\leq\tilde{I}(m)$ follows on taking infimum over $\gamma$. In
Section 8, Example 1, we show that when $G(m)$ is independent of $m$ then the
reverse inequality holds as well.

We now give one basic example for which our assumptions (namely Assumption
2.2) are satisfied. Several other examples are discussed in Section 8.

######  Example 2.6 (Quasi-Stationary Distributions).

Let $\Delta=\Delta^{o}\cup\\{0\\}$, $P\in\mathcal{K}(\Delta)$, and let
$\\{Y_{n},\;n\in\mathbb{N}_{0}\\}$ be a Markov chain with transition
probability kernel $P$. Then $\pi^{*}\in\mathcal{P}(\Delta^{o})$ is called a
quasi-stationary distribution for the chain $\\{Y_{n},\;n\in\mathbb{N}_{0}\\}$
if

$P_{\pi^{*}}(Y_{n}=x\mid
Y_{n}\in\Delta^{o})=\pi^{*}_{x},\;\;x\in\Delta^{o},n\in\mathbb{N}_{0},$

where $P_{\pi^{*}}$ denotes the probability measure under which $Y_{0}$ is
distributed as $\pi^{*}$. Suppose that the substochastic matrix $P^{o}$
defined by

$P^{o}_{x,y}\doteq P_{x,y},\;\;x,y\in\Delta^{o}$

is irreducible. Then it is known that there is a unique QSD for the Markov
chain $\\{Y_{n},\;n\in\mathbb{N}_{0}\\}$ [18]. In [1] a basic Monte-Carlo
method for computing this QSD was introduced. Define
$G:\mathcal{P}(\Delta^{o})\to\mathcal{K}(\Delta^{o})$ as

$G(m)_{x,y}\doteq
P_{x,y}+P_{x,0}m_{y},\;\;x,y\in\Delta^{o},m\in\mathcal{P}(\Delta^{o})$ (2.9)

and construct $\\{X_{n},L^{n+1},\;n\in\mathbb{N}_{0}\\}$ as in Section 2.1.
Then [1, 5] show that $L^{n}$ converges a.s. to the unique QSD $\pi^{*}$ of
the chain $\\{Y_{n},\;n\in\mathbb{N}_{0}\\}$. The current work establishes a
large deviation principle for the sequence $\\{L^{n},\;n\in\mathbb{N}_{0}\\}$
under the same irreducibility assumption on $P^{o}$ made in [5]. To see that
Assumption 2.2 is satisfied, note that Part 1 of this Assumption is clearly
satisfied by $G$. Part 3 is also satisfied under the above irreducibility
assumption (see [18]). From [1], $L^{n}$ converges a.s. to the unique QSD
$\pi^{*}$, so Part 4 holds as well. Finally, for Part 2, define
$A_{+}\doteq\\{(x,y)\in\Delta^{o}\times\Delta^{o}:P_{x,y}+P_{x,0}>0\\}$ and
$A_{x,y}=\bm{1}_{\\{(x,y)\in A_{+}\\}}$. Clearly $A$ is irreducible and parts
2a and 2b of Assumption 2.2 are satisfied with this choice of the adjacency
matrix $A$. Thus, the conditions for Theorem 2.4 are satisfied and one has a
large deviation principle for the empirical measure associated with the self-
interacting chain introduced in [1] for the approximation of the QSD of
$\\{Y_{n},\;n\in\mathbb{N}_{0}\\}$. We remark that the model in (2.9) can also
be viewed as a type of a vertex-reinforced random walk on $\Delta^{o}$. In
this walk, given that at some instant the walker is at site $x$, it jumps to a
site $y$ with probability that depends on the fraction of time the walker has
previously visited the site $y$, as given by the formula $P(x,y)+P(x,0)m_{y}$.

##  3 A Stochastic Control Representation

Throughout this section and next we fix $A\in\mathcal{A}$. It will be
convenient to consider the following pathwise construction of the collection
$\\{X_{n},L^{n+1},\;n\in\mathbb{N}_{0}\\}$ which will be used throughout. For
this construction it is useful to identify the state space with the space
$\mathcal{V}^{d}$ introduced in Section 1.2. In particular, note that each
$K\in\mathcal{K}(\Delta^{o})$ can be associated with a unique
$K^{\mathcal{V}}\in\mathcal{K}(\mathcal{V}^{d})$ through the identity

$K^{\mathcal{V}}_{e_{x},e_{y}}=K_{x,y},\;x,y\in\Delta^{o}.$

Similarly, define the operator
$G^{\mathcal{V}}:\mathcal{P}(\Delta^{o})\to\mathcal{K}(\mathcal{V}^{d})$ by

$G^{\mathcal{V}}(m)_{e_{x},e_{y}}\doteq G(m)_{x,y},\;x,y\in\Delta^{o}.$

Let
$\\{\nu^{k}(x,m),\;x\in\Delta^{o},m\in\mathcal{P}(\Delta^{o}),k\in\mathbb{N}\\}$
be iid $\mathcal{V}^{d}$-valued random fields such that, for each
$x\in\Delta^{o}$ and $m\in\mathcal{P}(\Delta^{o})$,

$\displaystyle
P(\nu^{1}(x,m)=e_{y})=G^{\mathcal{V}}(m)_{e_{x},e_{y}}=G(m)_{x,y},\quad
y\in\Delta^{o}.$

Then, the collection $\\{X_{n},L^{n+1},\;n\in\mathbb{N}_{0}\\}$ has the
following distributionally equivalent representation:
$(X_{0},L^{1})=(x_{0},\delta_{x_{0}})$,

$L^{k+1}=L^{k}+\frac{1}{k+1}\left[\nu^{k}(X_{k-1},L^{k})-L^{k}\right],\quad
e_{X_{k}}=\nu^{k}(X_{k-1},L^{k}),\;\;k\in\mathbb{N}.$ (3.1)

To prove the upper and lower bounds in Theorems 4.1 and 5.1, we rely on a
certain stochastic control representation for exponential moments of
functionals of $\\{L^{n},\;n\in\mathbb{N}\\}$ presented below. This
representation is given in terms of certain controlled analogues of
$\\{\nu^{k}(X_{k-1},L^{k}),L^{k+1},\;k\in\mathbb{N}\\}$.

For each $n\in\mathbb{N}$, the controlled stochastic system is a sequence
$\\{\bar{L}^{n,k},\;k\in\mathbb{N}\\}$ of $\mathcal{P}(\Delta^{o})$-valued
random variables which is defined recursively in terms of a collection of
random probability measures on $\mathcal{V}^{d}$,
$\\{\bar{\mu}^{n,k},\;k\in\mathbb{N}\\}$, where for each $k\in\mathbb{N}$,
$\bar{\mu}^{n,k}$ is
$\bar{\mathcal{F}}^{n,k}\doteq\sigma(\\{\bar{L}^{n,j},\;1\leq j\leq k\\})$
measurable, $\bar{L}^{n,1}\doteq\delta_{x_{0}}$, and, having defined
$\\{\bar{L}^{n,j},1\leq j\leq k\\}$, $\bar{L}^{n,k+1}$ is defined as

$\bar{L}^{n,k+1}\doteq\bar{L}^{n,k}+\frac{1}{k+1}\left[\bar{\nu}^{n,k}-\bar{L}^{n,k}\right],\;\;k\in\mathbb{N},$
(3.2)

where $\bar{\nu}^{n,k}$ is a $\mathcal{V}^{d}$-valued random variable such
that

$P[\bar{\nu}^{n,k}=e_{x}\mid\bar{\mathcal{F}}^{n,k}]=\bar{\mu}^{n,k}(e_{x}),\;\;x\in\Delta^{o}.$
(3.3)

We set $\bar{\nu}^{n,0}\doteq\delta_{x_{0}}$, and, for reach $n\in\mathbb{N}$
and $k\in\mathbb{N}_{0},$ we let $\bar{X}^{n,k}$ denote the
$\Delta^{o}$-valued random variable such that
$e_{\bar{X}^{n,k}}=\bar{\nu}^{n,k}$. We note that the evolution equation (3.2)
can be viewed as a ‘controlled’ analogue of (3.1). For the stochastic control
representation we give, it suffices, as discussed below (3.11), to consider
controlled processes for which, a.s., for each $k\in\mathbb{N}_{0}$,

$\delta_{\bar{\nu}^{n,k}}\otimes\bar{\mu}^{n,k+1}(e_{x},e_{y})=0,\mbox{ for
all }(x,y)\in(A_{+})^{c}.$ (3.4)

We denote the collection of all such control sequences
$\\{\bar{\mu}^{n,k},\;k\in\mathbb{N}\\}$ as $\Theta^{n}$.

It will be convenient to also consider the following collection of
$\mathcal{P}(\Delta^{o}\times\Delta^{o})$-valued random variables. Let
$\bar{\mathcal{T}}^{n,1}\doteq\delta_{(x_{0},\bar{X}^{n,1})}$, and, having
defined $\\{\bar{\mathcal{T}}^{n,j},\;1\leq j\leq k\\}$, define
$\bar{\mathcal{T}}^{n,k+1}$ as

$\bar{\mathcal{T}}^{n,k+1}\doteq\bar{\mathcal{T}}^{n,k}+\frac{1}{k+1}\left[\bar{\nu}^{n,k}\otimes\bar{\nu}^{n,k+1}-\bar{\mathcal{T}}^{n,k}\right],\;\;k\in\mathbb{N},$
(3.5)

where, with a slight abuse of notation,
$\bar{\nu}^{n,k}\otimes\bar{\nu}^{n,k+1}$ is a
$\mathcal{P}(\Delta^{o}\times\Delta^{o})$-valued random variable defined, for
$(x,y)\in\Delta^{o}\times\Delta^{o}$, as
$\bar{\nu}^{n,k}\otimes\bar{\nu}^{n,k+1}(x,y)=1$, if $\bar{\nu}^{n,k}=e_{x}$
and $\bar{\nu}^{n,k+1}=e_{y}$; and $0$ otherwise.

Since it is more convenient to work with processes indexed with a continuous
time parameter, we consider the following time interpolation sequence
$\\{t_{k},\;k\in\mathbb{N}_{0}\\}$ defined by

$t_{0}\doteq 0,\;\;t_{k}=\sum_{j=1}^{k}(j+1)^{-1},\;\;k\in\mathbb{N}.$

Such a time interpolation is standard in study of stochastic approximation
schemes [6, 8, 10, 28]. For each $n\in\mathbb{N}$, define the
$C(\mathbb{R}_{+}:\mathcal{P}(\Delta^{o}))$-valued (resp.
$C(\mathbb{R}_{+}:\mathcal{P}(\Delta^{o}\times\Delta^{o}))$-valued) random
variable $\bar{L}^{n}$ (resp. $\bar{\mathcal{T}}^{n}$) by linear
interpolation:

$\bar{L}^{n}(t)\doteq\bar{L}^{n,k+1}+(k+2)(t-t_{k})[\bar{L}^{n,k+2}-\bar{L}^{n,k+1}],\;\;t\in[t_{k},t_{k+1}),\;k\in\mathbb{N}_{0},$
(3.6)
$\bar{\mathcal{T}}^{n}(t)\doteq\bar{\mathcal{T}}^{n,k+1}+(k+2)(t-t_{k})[\bar{\mathcal{T}}^{n,k+2}-\bar{\mathcal{T}}^{n,k+1}],\;\;t\in[t_{k},t_{k+1}),\;k\in\mathbb{N}_{0},$
(3.7)

Consider random measures on $\mathcal{V}^{d}\times[0,t_{n}]$ and
$\mathcal{V}^{d}\times\mathcal{V}^{d}\times[0,t_{n}]$ defined as follows: for
$A\subseteq\mathcal{V}^{d}$, $C\subseteq\mathcal{V}^{d}$ and
$B\in\mathcal{B}[0,t_{n}]$,

$\displaystyle\bar{\Lambda}^{n}(A\times
B)\doteq\int_{B}\bar{\Lambda}^{n}(A\mid t)dt,$ (3.8)
$\displaystyle\bar{\xi}^{n}(A\times C\times
B)\doteq\int_{B}\bar{\xi}^{n}(A\times C\mid t)dt,\;\;\bar{\Xi}^{n}(A\times
C\times B)\doteq\int_{B}\bar{\Xi}^{n}(A\times C\mid t)dt$

where, for $k\leq n-1$ and $t\in[t_{k},t_{k+1})$,

$\displaystyle\bar{\Lambda}^{n}(\cdot\mid
t)\doteq\delta_{\bar{\nu}^{n,k+1}}(\cdot),\;\;\bar{\xi}^{n}(\cdot\mid
t)\doteq\delta_{\bar{\nu}^{n,k}}\otimes\bar{\mu}^{n,k+1}(\cdot),\;\;\bar{\Xi}^{n}(\cdot\mid
t)\doteq\delta_{\bar{\nu}^{n,k+1}}\otimes\delta_{\bar{\nu}^{n,k+2}}(\cdot).$
(3.9)

From (3.4), it follows that if $(x,y)\in(A_{+})^{c}$, then, for a.e.
$t\in\mathbb{R}_{+}$,

$\bar{\xi}^{n}(e_{x},e_{y}\mid t)=0,\;\;\bar{\Xi}^{n}(e_{x},e_{y}\mid
t)=0,\;\mbox{a.s.}$ (3.10)

The following variational representation follows from [21, Theorem 4.2.2],
[14, Theorem 4.5]. For each $F\in C_{b}(\mathcal{P}(\Delta^{o}))$,

$-n^{-1}\log E\exp[-nF(L^{n+1})]\\\
=\inf_{\\{\bar{\mu}^{n,i}\\}\in\Theta^{n}}E\left[F(\bar{L}^{n}(t_{n}))+n^{-1}\sum\limits_{k=0}^{n-1}R\left(\delta_{\bar{\nu}^{n,k}}\otimes\bar{\mu}^{n,k+1}\|\delta_{\bar{\nu}^{n,k}}\otimes
G^{\mathcal{V}}(\bar{L}^{n,k+1})(\bar{\nu}^{n,k},\cdot)\right)\right].$ (3.11)

The fact that in the infimum on the right side we can restrict, without loss
of generality, to sequences $\\{\bar{\mu}^{n,i},\;i\in\mathbb{N}\\}$ for which
(3.4) holds a.s. is because, if this property is violated, then the expression
on the right side is $\infty$ since $A\in\mathcal{A}$. Using (3.6) and the
representation in (3.8), we can rewrite the right side of the identity in
(3.11) as follows. For $s\in\mathbb{R}_{+}$, let

$m(s)\doteq\sup\\{k:t_{k}\leq s\\},\quad a(s)\doteq t_{m(s)}.$ (3.12)

For each $n\in\mathbb{N}$, define the random measure $\bar{\zeta}^{n}$ on
$\mathcal{V}^{d}\times\mathcal{V}^{d}\times[0,t_{n}]$ as follows: for
$A\subseteq\mathcal{V}^{d}$, $C\subseteq\mathcal{V}^{d}$ and
$B\in\mathcal{B}[0,t_{n}]$,

$\displaystyle\bar{\zeta}^{n}(A\times C\times
B)\doteq\int_{B}\bar{\zeta}^{n}\left(A\times C\mid
t,\bar{L}^{n}(a(t))\right)dt,$ (3.13)

where for $k\leq n-1$, $m\in\mathcal{P}(\Delta^{o})$ and
$t\in[t_{k},t_{k+1})$,

$\displaystyle\bar{\zeta}^{n}\left(\cdot\mid
t,m\right)\doteq\delta_{\bar{\nu}^{n,k}}\otimes
G^{\mathcal{V}}(m)(\bar{\nu}^{n,k},\cdot)(\cdot).$

From (3.2), (3.5), (3.6), and (3.9) it follows that, for $t\in[0,t_{n}]$,

$\begin{split}\bar{L}^{n}(t)&=\bar{L}^{n}(0)+\int_{0}^{t}\sum\limits_{v\in\mathcal{V}^{d}}(v-\bar{L}^{n}(a(s)))\bar{\Lambda}^{n}(v\mid
s)ds,\end{split}$ (3.14)

and, for $(x,y)\in\Delta^{o}\times\Delta^{o}$,

$\begin{split}\bar{\mathcal{T}}^{n}(t)(x,y)&=\bar{\mathcal{T}}^{n}(0)(x,y)+\int_{0}^{t}\sum_{v,v^{\prime}\in\mathcal{V}^{d}}(\bm{1}_{\\{v=e_{x},v^{\prime}=e_{y}\\}}-\bar{\mathcal{T}}^{n}(a(s))(x,y))\bar{\Xi}^{n}(v,v^{\prime}\mid
s)ds.\end{split}$ (3.15)

Define $\psi_{e}:\mathbb{R}_{+}\to\\{2,3,\dots\\}$ as

$\psi_{e}(t)\doteq\sum\limits_{k=0}^{\infty}(k+2)\bm{1}_{[t_{k},t_{k+1})}(t),$
(3.16)

so that

$\displaystyle
n^{-1}\sum\limits_{k=0}^{n-1}R\left(\delta_{\bar{\nu}^{n,k}}\otimes\bar{\mu}^{n,k+1}\|\delta_{\bar{\nu}^{n,k}}\otimes
G^{\mathcal{V}}(\bar{L}^{n,k+1})(\bar{\nu}^{n,k},\cdot)\right)$ (3.17)
$\displaystyle=n^{-1}\int_{0}^{t_{n}}\psi_{e}(s)R\left(\bar{\xi}^{n}(\cdot\mid
s)\|\bar{\zeta}^{n}\left(\cdot\mid s,\bar{L}^{n}(a(s))\right)\right)ds.$

Define $\mathcal{P}(\mathcal{V}^{d}\times\mathbb{R}_{+})$ and
$\mathcal{P}(\mathcal{V}^{d}\times\mathcal{V}^{d}\times\mathbb{R}_{+})$-valued
random variables as follows: for $t\in\mathbb{R}_{+}$ and $x,y\in\Delta^{o}$,
let

$\displaystyle\gamma^{n}(\\{e_{x}\\}\times[0,t])$ $\displaystyle\doteq
n^{-1}\int_{0}^{t_{n}\wedge t}\psi_{e}(t_{n}-s)\bar{\Lambda}^{n}(e_{x}\mid
t_{n}-s)ds$ (3.18)
$\displaystyle\beta^{n}(\\{e_{x}\\}\times\\{e_{y}\\}\times[0,t])$
$\displaystyle\doteq n^{-1}\int_{0}^{t_{n}\wedge
t}\psi_{e}(t_{n}-s)\bar{\xi}^{n}((e_{x},e_{y})\mid t_{n}-s)ds$
$\displaystyle\theta^{n}(\\{e_{x}\\}\times\\{e_{y}\\}\times[0,t])$
$\displaystyle\doteq n^{-1}\int_{0}^{t_{n}\wedge
t}\psi_{e}(t_{n}-s)\bar{\zeta}^{n}\left((e_{x},e_{y})\mid
t_{n}-s,\bar{L}^{n}(a(t_{n}-s))\right)ds.$

The fact that the quantities in (3.18) define probability measures on
$\mathcal{V}^{d}\times\mathbb{R}_{+}$ (resp.
$\mathcal{V}^{d}\times\mathcal{V}^{d}\times\mathbb{R}_{+}$) follows on
observing that, for each $n\in\mathbb{N}$,

$n^{-1}\int_{0}^{t_{n}}\psi_{e}(s)ds=1.$

Also, from (3.10) it follows that if $(x,y)\in(A_{+})^{c}$, then, for each
$t\in\mathbb{R}_{+}$,

$\beta^{n}(\\{e_{x}\\}\times\\{e_{y}\\}\times[0,t])=0,\mbox{ a.s. }$ (3.19)

From (3.17) and chain rule for relative entropies (see [14, Corollary 2.7]),
it follows that

$n^{-1}\sum\limits_{k=0}^{n-1}R\left(\delta_{\bar{\nu}^{n,k}}\otimes\bar{\mu}^{n,k+1}\|\delta_{\bar{\nu}^{n,k}}\otimes
G^{\mathcal{V}}(\bar{L}^{n,k+1})(\bar{\nu}^{n,k},\cdot)\right)=R\left(\beta^{n}\|\theta^{n}\right).$
(3.20)

With the identity in (3.20), the expectation on the right side of (3.11) can
be rewritten as

$E\left[F(\bar{L}^{n}(t_{n}))+R\left(\beta^{n}\|\theta^{n}\right)\right].$
(3.21)

In our proofs it will be convenient to consider the dynamics of $\bar{L}^{n}$
viewed backwards in time. Towards that end, for each $n\in\mathbb{N}$, define
the $C(\mathbb{R}_{+}:\mathcal{P}(\Delta^{o}))$-valued (resp.
$C(\mathbb{R}_{+}:\mathcal{P}(\Delta^{o}\times\Delta^{o}))$-valued) random
variable $\check{\mathbf{L}}^{n}$ (resp. $\check{\mathbf{\mathcal{T}}}^{n}$)
by

$(\check{\mathbf{L}}^{n}(t),\check{\mathbf{\mathcal{T}}}^{n}(t))\doteq\begin{cases}(\bar{L}^{n}(t_{n}-t),\bar{\mathcal{T}}^{n}(t_{n}-t))&0\leq
t\leq t_{n}\\\ (\bar{L}^{n}(0),\bar{\mathcal{T}}^{n}(0))&t\geq
t_{n}.\end{cases}$ (3.22)

Also, for each $n\in\mathbb{N}$, define the
$\mathcal{M}(\mathcal{V}^{d}\times\mathbb{R}_{+})$-valued random variable
$\check{\Lambda}^{n}$ by, for $A\subseteq\mathcal{V}^{d}$ and
$t\in\mathbb{R}_{+}$,

$\check{\Lambda}^{n}(A\times[0,t])\doteq\int_{t_{n}-t}^{t_{n}}\bar{\Lambda}^{n}(A\mid
s)ds=\int_{0}^{t}\check{\Lambda}^{n}(A\mid s)ds,$ (3.23)

where $\bar{\Lambda}^{n}(A\mid s)\doteq 0$ for $s\leq 0$, and
$\check{\Lambda}^{n}(A\mid s)\doteq\bar{\Lambda}^{n}(A\mid t_{n}-s)$ for
$s\in\mathbb{R}_{+}$. For each $n\in\mathbb{N}$, define the quantities
$\check{\Xi}^{n}$ and $\check{\Xi}^{n}(\cdot\mid s)$ similarly. From (3.14) we
see that these time-reversed controlled processes satisfy the following
evolution equation: for $t\in\mathbb{R}_{+}$ and $n\geq m(t)$,

$\begin{split}\check{\mathbf{L}}^{n}(t)&=\check{\mathbf{L}}^{n}(0)-\int_{0}^{t}\sum\limits_{v\in\mathcal{V}^{d}}v\check{\Lambda}^{n}(v\mid
s)ds+\int_{t_{n}-t}^{t_{n}}\check{\mathbf{L}}^{n}(t_{n}-a(s))ds,\\\
\end{split}$ (3.24)

and, for $(x,y)\in\Delta^{o}\times\Delta^{o}$,

$\begin{split}\check{\mathbf{\mathcal{T}}}^{n}(t)(x,y)&=\check{\mathbf{\mathcal{T}}}^{n}(0)(x,y)-\int_{0}^{t}\sum_{v,v^{\prime}\in\mathcal{V}^{d}}\bm{1}_{\\{v=e_{x},v^{\prime}=e_{y}\\}}\check{\Xi}^{n}(v,v^{\prime}\mid
s)ds+\int_{t_{n}-t}^{t_{n}}\check{\mathbf{\mathcal{T}}}^{n}(t_{n}-a(s))(x,y)ds.\\\
\end{split}$ (3.25)

Furthermore, from (3.11) and (3.21) we have that

$-n^{-1}\log
E\exp[-nF(L^{n+1})]=\inf_{\\{\bar{\mu}^{n,i}\\}\in\Theta^{n}}E\left[F(\check{\mathbf{L}}^{n}(0))+R\left(\beta^{n}\|\theta^{n}\right)\right].$
(3.26)

##  4 Laplace Upper Bound

Recall that we fix $A\in\mathcal{A}$. The main result of the section is the
following theorem, which gives the large deviations upper bound.

######  Theorem 4.1.

Suppose that Assumption 2.1 is satisfied. Then, for every $F\in
C_{b}(\mathcal{P}(\Delta^{o}))$,

$\liminf_{n\to\infty}-n^{-1}\log
E\exp[-nF(L^{n+1})]\geq\inf_{m\in\mathcal{P}(\Delta^{o})}[F(m)+I(m)].$

Assumption 2.1 will be taken to hold for the rest of this section.

###  4.1 Tightness and Weak Convergence

A key step in the proof of Theorem 4.1 will be establishing the tightness of
suitable controlled quantities and identifying their weak limit points. In
preparation for that we first recall the following estimate for the harmonic
series (cf. [16]). For any $n\geq 2$

$\gamma+\frac{1}{2(n+1)}<\sum\limits_{k=1}^{n}k^{-1}-\log
n<\gamma+\frac{1}{2(n-1)},$ (4.1)

where $\gamma\approx 0.57721$ is the Euler-Mascheroni constant. Recall the map
$m:\mathbb{R}_{+}\to\mathbb{N}_{0}$ (resp.
$\psi_{e}:\mathbb{R}_{+}\to\\{2,3,\ldots\\}$) from (3.12) (resp. (3.16)). By
(4.1) and the observation that $t_{n}-s\leq t_{m(t_{n}-s)+1}$, we see that for
all $n\in\mathbb{N}$ and $s\in\mathbb{R}_{+}$,

$\log(n+1)+\frac{1}{2(n+2)}-(s+1)\leq t_{n}-s-\gamma\leq
t_{m(t_{n}-s)+1}-\gamma\leq\log(m(t_{n}-s)+2)-1+\frac{1}{2(m(t_{n}-s)+1)}.$
(4.2)

As a consequence of this inequality we have the following lemma.

######  Lemma 4.2.

For each $t\in\mathbb{R}_{+}$, as $n\to\infty$, $n^{-1}m(t_{n}-t)\to\exp(-t).$
Additionally, for each $t\in\mathbb{R}_{+}$, as $n\to\infty$,

$\sup_{s\in[0,t]}\left|n^{-1}\psi_{e}(t_{n}-s)-\exp(-s)\right|\to 0.$ (4.3)

###### Proof.

The first statement in the lemma is immediate from the second on observing
that for all $t\in\mathbb{R}_{+}$, $m(t_{n}-t)-\psi_{e}(t_{n}-t)=2$. We now
prove the second statement. For $s\in\mathbb{R}_{+}$ and $n\in\mathbb{N}$, let
$k_{s,n}\doteq m(t_{n}-s)$, so that

$n^{-1}\psi_{e}(t_{n}-s)=n^{-1}(k_{s,n}+2).$ (4.4)

From (4.2), for all $s\in\mathbb{R}_{+}$ and $n\in\mathbb{N}$,

$\gamma+\log(n+1)+(2n+4)^{-1}-(s+1)\leq t_{n}-s|\leq
t_{k_{s,n}+1}\leq\log(k_{s,n}+2)-1+\gamma+(2k_{s,n}+2)^{-1},$ (4.5)

from which it follows that
$e^{-s}\leq(n+1)^{-1}(k_{s,n}+2)e^{\frac{1}{2k_{s,n}+2}}$, and therefore that

$(e^{-\frac{1}{2k_{s,n}+3}}-1)e^{-s}\leq n^{-1}(k_{s,n}+2)-e^{-s}.$ (4.6)

Next, using the estimate

$\gamma+\log(k_{s,n}+1)\leq\gamma+\log(k_{s,n}+1)+(2k_{s,n}+4)^{-1}\leq
t_{k_{s,n}}+1\leq t_{n}-s+1\leq\gamma+\log(n+1)+\frac{1}{2n}-s,$

we have that $\log\left(\frac{k_{s,n}+1}{n+1}\right)\leq(2n)^{-1}-s$, which,
along with the fact that $k_{s,n}\leq n$, ensures that $n^{-1}k_{s,n}\leq
e^{-s}e^{\frac{1}{2n}}$ Consequently,

$n^{-1}(k_{s,n}+2)-e^{-s}\leq e^{-s}(e^{\frac{1}{2n}}-1)+2n^{-1}\leq
e^{\frac{1}{2n}}+n^{-1}(2-n).$ (4.7)

Once more using (4.5), we see that
$\log(n+1)-s\leq\log(k_{s,n}+2)+(2k_{s,n}+2)^{-1}$, so, for fixed
$t\in\mathbb{R}_{+}$ and for each $s\in[0,t]$ and all $n\in\mathbb{N}$,

$(n+1)e^{-t-1}\leq(n+1)e^{-s-1}\leq k_{s,n}+2.$ (4.8)

Using (4.8), we see that for each $n\in\mathbb{N}$,

$\sup\nolimits_{s\in[0,t]}\left|e^{-\frac{1}{2k_{s,n}+3}}-1\right|\leq
1-\exp\left(-(2(n+1)e^{-t-1}-1)^{-1}\right)$

which shows that, as $n\to\infty$,

$\sup\nolimits_{s\in[0,t]}\left|e^{-\frac{1}{2k_{s,n}+3}}-1\right|\to 0.$
(4.9)

Combining (4.6) and (4.7), we see that for each $s\geq 0$ and
$n\in\mathbb{N}$,

$\left(e^{-\frac{1}{2k_{s,n}+3}}-1\right)e^{-s}\leq\frac{k_{s,n}+2}{n}-e^{-s}\leq
e^{\frac{1}{2n}}+\frac{2-n}{n},$

so, from (4.4), for each $n\in\mathbb{N}$,

$\sup\nolimits_{s\in[0,t]}\left|n^{-1}\psi_{e}(t_{n}-s)-e^{-s}\right|\leq\max\left\\{\sup\nolimits_{s\in[0,t]}(1-e^{-\frac{1}{2k_{s,n}+3}}),e^{\frac{1}{2n}}+n^{-1}(2-n)\right\\}.$
(4.10)

Combining (4.9) and (4.10), we obtain (4.3). ∎

The next lemma shows that the sequences of various quantities, introduced in
Section 3, associated with a sequence of controls
$\\{\bar{\mu}^{n,i}\\}\in\Theta^{n}$, is tight.

######  Lemma 4.3.

Let for $n\in\mathbb{N}$, $\\{\bar{\mu}^{n,i}\\}\in\Theta^{n}$. The collection
$\\{(\check{\mathbf{L}}^{n},\check{\mathbf{\mathcal{T}}}^{n},\check{\Lambda}^{n},\gamma^{n},\beta^{n},\theta^{n}),\;n\in\mathbb{N}\\}$,
associated with the sequence of controls
$\\{\bar{\mu}^{n,i},\;n\in\mathbb{N}\\}$, as defined in Section 3, is tight in
$C(\mathbb{R}_{+}:\mathcal{P}(\Delta^{o}))\times
C(\mathbb{R}_{+}:\mathcal{P}(\Delta^{o}\times\Delta^{o}))\times\mathcal{M}(\mathcal{V}^{d}\times\mathbb{R}_{+})\times\mathcal{P}(\mathcal{V}^{d}\times\mathbb{R}_{+})\times(\mathcal{P}(\mathcal{V}^{d}\times\mathcal{V}^{d}\times\mathbb{R}_{+}))^{2}$.

###### Proof.

We begin by showing that $\\{\check{\mathbf{L}}^{n},\;n\in\mathbb{N}\\}$ is
tight. Since $\mathcal{P}(\Delta^{o})$ is compact, it suffices to show that
for some $C\in(0,\infty)$, and for all $n\in\mathbb{N}$ and
$s,t\in\mathbb{R}_{+}$,
$\|\check{\mathbf{L}}^{n}(t)-\check{\mathbf{L}}^{n}(s)\|\leq C|t-s|$, a.s.
However, this is immediate from (3.24) (or equivalently (3.14)), on using the
fact that $\|v-\bar{L}^{n}(a(s))\|\leq 2$ for all $s\in\mathbb{R}_{+}$ and
$v\in\mathcal{V}^{d}$. The tightness of
$\\{\check{\mathbf{\mathcal{T}}}^{n},\;n\in\mathbb{N}\\}$ is argued similarly.

The tightness of $\\{\check{\Lambda}^{n},\;n\in\mathbb{N}\\}$ in
$\mathcal{M}(\mathcal{V}^{d}\times\mathbb{R}_{+})$ under the vague topology is
immediate on observing that for each $k\in\mathbb{N}$,
$\sup_{n\in\mathbb{N}}\check{\Lambda}^{n}(\mathcal{V}^{d}\times[0,k])=k$.
Next, since $\mathcal{V}^{d}$ is compact, the sequences
$\\{\gamma^{n}_{(1)},\;n\in\mathbb{N}\\}$,
$\\{\beta^{n}_{(1)},\;n\in\mathbb{N}\\}$,
$\\{\beta^{n}_{(2)},\;n\in\mathbb{N}\\}$,
$\\{\theta^{n}_{(1)},\;n\in\mathbb{N}\\}$ and
$\\{\theta^{n}_{(2)},\;n\in\mathbb{N}\\}$, are obviously tight. Also, for each
$n\in\mathbb{N}$, $\gamma^{n}_{(2)}=\beta^{n}_{(3)}=\theta^{n}_{(3)}$, so to
complete the proof it suffices to show that the sequence
$\\{\gamma^{n}_{(2)},\;n\in\mathbb{N}\\}$ is tight. Observe that, for each
$n\in\mathbb{N}$, if $n\geq m(t)$, then, since $t_{n}-t\leq t_{m(t_{n}-t)+1}$,

$\gamma^{n}_{(2)}([0,t])=n^{-1}\int_{0}^{t}\psi_{e}(t_{n}-s)ds=n^{-1}\int_{t_{n}-t}^{t_{n}}\psi_{e}(s)ds\\\
\geq
n^{-1}\sum\limits_{k=m(t_{n}-t)+1}^{n-1}\int_{t_{k}}^{t_{k+1}}\psi_{e}(s)ds=1-n^{-1}(m(t_{n}-t)+1).$

Fix $\varepsilon>0$ and $t>\log(3\varepsilon^{-1})$. Then, from Lemma 4.2, we
can find some $n_{0}>2\varepsilon^{-1}$ such that $n_{0}\geq m(t)$ and

$\sup_{n\geq n_{0}}|n^{-1}m(t_{n}-t)-e^{-t}|\leq 2^{-1}\varepsilon.$

Thus, $\inf\nolimits_{n\geq n_{0}}\gamma^{n}_{(2)}([0,t])\geq 1-\varepsilon$.
Since $\varepsilon>0$ is arbitrary, the desired tightness follows. ∎

The next lemma provides a useful characterization of the weak limit points of
the tight collection in Lemma 4.3.

######  Lemma 4.4.

Let the sequence
$\\{(\check{\mathbf{L}}^{n},\check{\mathbf{\mathcal{T}}}^{n},\check{\Lambda}^{n},\gamma^{n},\beta^{n},\theta^{n}),\;n\in\mathbb{N}\\}$
be as in Lemma 4.3 and let
$(\check{\mathbf{L}}^{*},\check{\mathbf{\mathcal{T}}}^{*},\check{\Lambda}^{*},\gamma^{*},\beta^{*},\theta^{*})$
be a weak limit point of the sequence. Then, the following hold a.s.

  1. (a)

The measure $\check{\Lambda}^{*}$ can be disintegrated as
$\check{\Lambda}^{*}(dv,ds)=\check{\Lambda}^{*}(dv\mid s)ds$.

  2. (b)

For $t\in\mathbb{R}_{+}$

$\check{\mathbf{L}}^{*}(t)=\check{\mathbf{L}}^{*}(0)-\int_{0}^{t}\sum\limits_{v\in\mathcal{V}^{d}}v\check{\Lambda}^{*}(v\mid
s)ds+\int_{0}^{t}\check{\mathbf{L}}^{*}(s)ds.$ (4.11)

  3. (c)

$\beta^{*}_{(1,3)}=\beta^{*}_{(2,3)}=\theta^{*}_{(1,3)}=\gamma^{*}$.

  4. (d)

For $t\in\mathbb{R}_{+}$ and $x\in\Delta^{o}$,
$\gamma^{*}(\\{e_{x}\\}\times[0,t])=\int_{0}^{t}\exp(-s)\check{\Lambda}^{*}(e_{x}\mid
s)ds$.

  5. (e)

For all $t\in\mathbb{R}_{+}$ and $(x,y)\in(A_{+})^{c}$,
$\beta^{*}(\\{e_{x}\\}\times\\{e_{y}\\}\times[0,t])=0$.

  6. (f)

For $t\in\mathbb{R}_{+}$ and $x,y\in\Delta^{o}$,

$\theta^{*}(\\{e_{x}\\}\times\\{e_{y}\\}\times[0,t])=\int_{0}^{t}\exp(-s)\check{\Lambda}^{*}(e_{x}\mid
s)G^{\mathcal{V}}(\check{\mathbf{L}}^{*}(s))(e_{x},e_{y})ds.$

  7. (g)

For $t\in\mathbb{R}_{+}$,
$(\check{\mathbf{\mathcal{T}}}^{*}(t))_{(1)}=(\check{\mathbf{\mathcal{T}}}^{*}(t))_{(2)}=\check{\mathbf{L}}^{*}(t)$.
Furthermore, for all $t\in\mathbb{R}_{+}$ and $(x,y)\in(A_{+})^{c}$,
$\check{\mathbf{\mathcal{T}}}^{*}(t)(x,y)=0$, and for all
$s,t\in\mathbb{R}_{+}$,
$\|\check{\mathbf{\mathcal{T}}}^{*}(t)-\check{\mathbf{\mathcal{T}}}^{*}(s)\|\leq
2|t-s|$.

###### Proof.

Fix a weakly convergent subsequence of
$\\{(\check{\mathbf{L}}^{n},\check{\Lambda}^{n},\gamma^{n},\beta^{n},\theta^{n}),\;n\in\mathbb{N}\\}$
and relabel it as $\\{n\\}$. We now prove the various statements in the lemma
for the limit
$(\check{\mathbf{L}}^{*},\check{\Lambda}^{*},\gamma^{*},\beta^{*},\theta^{*})$
of this sequence.

  1. (a)

This is immediate on noting that for each $n\in\mathbb{N}$ and $t\geq 0$,
$\sum_{x\in\Delta^{o}}\check{\Lambda}^{n}(e_{x}\times[0,t])=t.$

  2. (b)

By appealing to Skorohod’s representation theorem, we assume without loss of
generality that
$\\{(\check{\mathbf{L}}^{n},\check{\Lambda}^{n}),\;n\in\mathbb{N}\\}$
converges almost surely to $(\check{\mathbf{L}}^{*},\check{\Lambda}^{*})$. For
$t\in\mathbb{R}_{+}$ and $m(t)\leq n$, recall the evolution equation (3.24).
Also note that

$\int_{t_{n}-t}^{t_{n}}\check{\mathbf{L}}^{n}(t_{n}-a(s))ds=\Bigg{(}\int_{t_{n}-t}^{t_{n}}\check{\mathbf{L}}^{n}(t_{n}-a(s))ds-\int_{t_{n}-t}^{t_{n}}\check{\mathbf{L}}^{n}(t_{n}-s)ds\Bigg{)}+\int_{0}^{t}\check{\mathbf{L}}^{n}(s)ds,$
(4.12)

and, for each $t\in\mathbb{R}_{+}$,

$\left\|\int_{t_{n}-t}^{t_{n}}\check{\mathbf{L}}^{n}(t_{n}-a(s))ds-\int_{t_{n}-t}^{t_{n}}\check{\mathbf{L}}^{n}(t_{n}-s)ds\right\|\leq
t\sup_{s\in[t_{n}-t,t_{n}]}\|\bar{L}^{n}(a(s))-\bar{L}^{n}(s)\|.$ (4.13)

As in the proof of Lemma 4.3, for all $n\in\mathbb{N}$ satisfying $t_{n}\geq
t$ and $s\in[t_{n}-t,t_{n}]$,

$\|\bar{L}^{n}(a(s))-\bar{L}^{n}(s)\|\leq 2(m(t_{n}-t)+2)^{-1}.$ (4.14)

Combining (4.12), (4.13), and (4.14) with (3.24), and using the almost sure
convergence of
$\\{(\check{\mathbf{L}}^{n},\check{\Lambda}^{n}),\;n\in\mathbb{N}\\}$ to
$(\check{\mathbf{L}}^{*},\check{\Lambda}^{*})$ we see that, as $n\to\infty$,
for each $t\in\mathbb{R}_{+}$,

$\check{\mathbf{L}}^{n}(t)\to\check{\mathbf{L}}^{*}(0)-\int\limits_{0}^{t}\sum\limits_{v\in\mathcal{V}^{d}}v\check{\Lambda}^{*}(v\mid
s)ds+\int_{0}^{t}\check{\mathbf{L}}^{*}(s)ds,$

almost surely. The result follows.

  3. (c)

As in part (b), we assume that the convergence of
$\\{(\gamma^{n},\beta^{n},\theta^{n}),\;n\in\mathbb{N}\\}$ holds in the almost
sure sense. Observe that, for each $n\in\mathbb{N}$,
$\beta^{n}_{(1,3)}=\theta^{n}_{(1,3)}$, so the identity
$\beta^{*}_{(1,3)}=\theta^{*}_{(1,3)}$ follows. Now we show that
$\beta^{*}_{(1,3)}=\gamma^{*}$. Towards this end, fix $x\in\Delta^{o}$ and
$t\in\mathbb{R}_{+}$, and observe that, for each $n\geq m(t)$,

$\begin{split}\left|\beta^{n}_{(1,3)}(\\{e_{x}\\}\times[0,t])-\gamma^{n}(\\{e_{x}\\}\times[0,t])\right|&\leq
n^{-1}+n^{-1}\left|\sum\limits_{k=m(t_{n}-t)}^{n-1}\left(\delta_{\bar{\nu}^{n,k}}(e_{x})-\delta_{\bar{\nu}^{n,k+1}}(e_{x})\right)\right|\leq
2n^{-1}.\end{split}$

The desired identity follows on letting $n\to\infty$. Now we show that
$\beta^{*}_{(2,3)}=\gamma^{*}$. Once more, fix $t\in\mathbb{R}_{+}$ and
$x\in\Delta^{o}$, and observe that, for each $n\geq m(t)$,

$\begin{split}&\gamma^{n}(\\{e_{x}\\}\times[0,t])-\beta^{n}_{(2,3)}(\\{e_{x}\\}\times[0,t])\\\
&=n^{-1}\int_{0}^{t}\psi_{e}(t_{n}-s)\left(\bar{\Lambda}^{n}(e_{x}\mid
t_{n}-s)-\bar{\xi}^{n}_{(2)}(e_{x}\mid t_{n}-s)\right)ds\\\
&=n^{-1}\int_{t_{n}-t}^{t_{n}}\psi_{e}(s)\left(\bar{\Lambda}^{n}(e_{x}\mid
s)-\bar{\xi}^{n}_{(2)}(e_{x}\mid s)\right)ds.\end{split}$ (4.15)

Additionally, for $1\leq l\leq m\leq n$,

$\begin{split}n^{-1}\int_{t_{l}}^{t_{m+1}}\psi_{e}(s)\left(\bar{\Lambda}^{n}(e_{x}\mid
s)-\bar{\xi}^{n}_{(2)}(e_{x}\mid
s)\right)ds&=n^{-1}\sum\limits_{k=l}^{m}\left(\delta_{\bar{\nu}^{n,k+1}}(e_{x})-\bar{\mu}^{n,k+1}(e_{x})\right)\end{split}$
(4.16)

so, recalling (3.3) and using the martingale-difference property, we see that

$\mathbb{E}\left(n^{-1}\sum\limits_{k=l}^{m}\left(\delta_{\bar{\nu}^{n,k+1}}(e_{x})-\bar{\mu}^{n,k+1}(e_{x})\right)\right)^{2}\leq
n^{-2}(m-l+1).$ (4.17)

Combining (4.15), (4.16), and (4.17), we see that for some
$C_{1}\in(0,\infty)$, and all $n\geq m(t)$,

$\mathbb{E}\left(\left|\beta^{n}_{(2,3)}(\\{e_{x}\\}\times[0,t])-\gamma^{n}(\\{e_{x}\\}\times[0,t])\right|^{2}\right)\leq
C_{1}n^{-1}.$

The statement in (c) follows on letting $n\to\infty$.

  4. (d)

Once more we assume, without loss of generality, that the sequence
$\\{(\check{\mathbf{L}}^{n},\check{\Lambda}^{n},\gamma^{n},\beta^{n},\theta^{n}),\;n\in\mathbb{N}\\}$,
converges almost surely to
$(\check{\mathbf{L}}^{*},\check{\Lambda}^{*},\gamma^{*},\beta^{*},\theta^{*})$.
Fix $x\in\Delta^{o}$ and $t\in\mathbb{R}_{+}$, and observe that, for each
$n\geq m(t)$,

$\left|n^{-1}\int_{0}^{t}\psi_{e}(t_{n}-s)\check{\Lambda}^{n}(e_{x}\mid
s)ds-\int_{0}^{t}\exp(-s)\check{\Lambda}^{*}(e_{x}\mid s)ds\right|\\\
\leq\left|n^{-1}\int_{0}^{t}\psi_{e}(t_{n}-s)\check{\Lambda}^{n}(e_{x}\mid
s)ds-\int_{0}^{t}\exp(-s)\check{\Lambda}^{n}(e_{x}\mid s)ds\right|\\\
+\left|\int_{0}^{t}\exp(-s)\check{\Lambda}^{n}(e_{x}\mid
s)ds-\int_{0}^{t}\exp(-s)\check{\Lambda}^{*}(e_{x}\mid s)ds\right|.$ (4.18)

Next, note that

$\left|n^{-1}\int_{0}^{t}\psi_{e}(t_{n}-s)\check{\Lambda}^{n}(e_{x}\mid
s)ds-\int_{0}^{t}\exp(-s)\check{\Lambda}^{n}(e_{x}\mid s)ds\right|\\\
\leq\int_{0}^{t}\left|n^{-1}\psi_{e}(t_{n}-s)-\exp(-s)\right|\left|\check{\Lambda}^{n}(e_{x}\mid
s)\right|ds\leq
t\sup_{s\in[0,t]}\left|n^{-1}\psi_{e}(t_{n}-s)-\exp(-s)\right|,$ (4.19)

and, by convergence of $\check{\Lambda}^{n}$ to $\check{\Lambda}^{*}$, as
$n\to\infty$,

$\left|\int_{0}^{t}\exp(-s)\check{\Lambda}^{n}(\\{e_{x}\\}\times
ds)-\int_{0}^{t}\exp(-s)\check{\Lambda}^{*}(\\{e_{x}\\}\times ds)\right|\to
0.$ (4.20)

The displays in (4.18),(4.19),(4.20), together with Lemma 4.2 show that, as
$n\to\infty$,

$n^{-1}\int_{0}^{t}\psi_{e}(t_{n}-s)\check{\Lambda}^{n}(e_{x}\mid
s)ds\to\int_{0}^{t}\exp(-s)\check{\Lambda}^{*}(e_{x}\mid s)ds.$

On recalling the definition of $\gamma^{n}$ we now have the statement in (d).

  5. (e)

This result follows immediately from the observation in (3.19).

  6. (f)

Once again, we assume that the a.e. convergence as in (d) holds. Fix
$t\in\mathbb{R}_{+}$, $n\geq m(t)$, and $x,y\in\Delta^{o}$, and observe that,

$\begin{split}&\left|\theta^{n}(\\{e_{x}\\}\times\\{e_{y}\\}\times[0,t])-\int_{0}^{t}\exp(-s)\check{\Lambda}^{*}(e_{x}\mid
s)G^{\mathcal{V}}(\check{\mathbf{L}}^{*}(s))(e_{x},e_{y})ds\right|\\\
&=\Bigg{|}n^{-1}\int_{0}^{t}\psi_{e}(t_{n}-s)\bar{\zeta}^{n}\left((e_{x},e_{y})\mid
t_{n}-s,\bar{L}^{n}(a(t_{n}-s))\right)ds\\\
&\quad-\int_{0}^{t}\exp(-s)\check{\Lambda}^{*}(e_{x}\mid
s)G^{\mathcal{V}}(\check{\mathbf{L}}^{*}(s))(e_{x},e_{y})ds\Bigg{|}\\\
&\leq\left|\int_{0}^{t}\left(n^{-1}\psi_{e}(t_{n}-s)-\exp(-s)\right)\bar{\zeta}^{n}\left((e_{x},e_{y})\mid
t_{n}-s,\bar{L}^{n}(a(t_{n}-s))\right)ds\right|\\\
&\quad+\left|\int_{0}^{t}\exp(-s)\left(\bar{\zeta}^{n}\left((e_{x},e_{y})\mid
t_{n}-s,\bar{L}^{n}(a(t_{n}-s))\right)-\check{\Lambda}^{*}(e_{x}\mid
s)G^{\mathcal{V}}(\check{\mathbf{L}}^{*}(s))(e_{x},e_{y})\right)ds\right|.\end{split}$
(4.21)

From Lemma 4.2,

$\left|\int_{0}^{t}\left(n^{-1}\psi_{e}(t_{n}-s)-\exp(-s)\right)\bar{\zeta}^{n}\left((e_{x},e_{y})\mid
t_{n}-s,\bar{L}^{n}(a(t_{n}-s))\right)ds\right|\to 0,$ (4.22)

as $n\to\infty$. Additionally, for each $s\in[0,t]$,

$\begin{split}&\bar{\zeta}^{n}((e_{x},e_{y})\mid
t_{n}-s,\bar{L}^{n}(a(t_{n}-s)))-\check{\Lambda}^{*}(e_{x}\mid
s)G^{\mathcal{V}}(\check{\mathbf{L}}^{*}(s))(e_{x},e_{y})\\\
&\quad=\delta_{\bar{\nu}^{n,m(t_{n}-s)}}\otimes
G^{\mathcal{V}}(\bar{L}^{n}(a(t_{n}-s)))(e_{x},e_{y})-\check{\Lambda}^{*}(e_{x}\mid
s)G^{\mathcal{V}}(\check{\mathbf{L}}^{*}(s))(e_{x},e_{y})\\\
&\quad=\delta_{\bar{\nu}^{n,m(t_{n}-s)}}\otimes
G^{\mathcal{V}}(\bar{L}^{n}(a(t_{n}-s)))(e_{x},e_{y})-\delta_{\bar{\nu}^{n,m(t_{n}-s)}}\otimes
G^{\mathcal{V}}(\check{\mathbf{L}}^{*}(s))(e_{x},e_{y})\\\
&\qquad+\delta_{\bar{\nu}^{n,m(t_{n}-s)}}\otimes
G^{\mathcal{V}}(\check{\mathbf{L}}^{*}(s))(e_{x},e_{y})-\check{\Lambda}^{*}(e_{x}\mid
s)G^{\mathcal{V}}(\check{\mathbf{L}}^{*}(s))(e_{x},e_{y}),\end{split}$

and

$\begin{split}&\left|\delta_{\bar{\nu}^{n,m(t_{n}-s)}}\otimes
G^{\mathcal{V}}(\bar{L}^{n}(a(t_{n}-s)))(e_{x},e_{y})-\delta_{\bar{\nu}^{n,m(t_{n}-s)}}\otimes
G^{\mathcal{V}}(\check{\mathbf{L}}^{*}(s))(e_{x},e_{y})\right|\\\
&\quad\leq\left|G^{\mathcal{V}}(\bar{L}^{n}(a(t_{n}-s)))(e_{x},e_{y})-G^{\mathcal{V}}(\check{\mathbf{L}}^{*}(s))(e_{x},e_{y})\right|\\\
&\quad\leq\left|G^{\mathcal{V}}(\bar{L}^{n}(a(t_{n}-s)))(e_{x},e_{y})-G^{\mathcal{V}}(\bar{L}^{n}(t_{n}-s))(e_{x},e_{y})\right|\\\
&\qquad+\left|G^{\mathcal{V}}(\check{\mathbf{L}}^{n}(s)(e_{x},e_{y})-G^{\mathcal{V}}(\check{\mathbf{L}}^{*}(s))(e_{x},e_{y})\right|.\end{split}$
(4.23)

Since by Assumption 2.1 $G^{\mathcal{V}}$ is a Lipschitz map and recalling
from (4.14) that

$\|\bar{L}^{n}(a(t_{n}-s))-\bar{L}^{n}(t_{n}-s)\|\leq
2(m(t_{n}-t)+2)^{-1},\quad s\in[0,t],$ (4.24)

and that $\check{\mathbf{L}}^{n}\to\check{\mathbf{L}}^{*}$ almost surely as
$n\to\infty$, it follows from (4.23) that

$\left|\delta_{\bar{\nu}^{n,m(t_{n}-s)}}\otimes
G^{\mathcal{V}}(\bar{L}^{n}(a(t_{n}-s)))(e_{x},e_{y})-\delta_{\bar{\nu}^{n,m(t_{n}-s)}}\otimes
G^{\mathcal{V}}(\check{\mathbf{L}}^{*}(s))(e_{x},e_{y})\right|\to 0,$ (4.25)

as $n\to\infty$. Now, observe that, for each $s\in[0,t]$,

$\begin{split}&\delta_{\bar{\nu}^{n,m(t_{n}-s)+1}}\otimes
G^{\mathcal{V}}(\check{\mathbf{L}}^{*}(s))(e_{x},e_{y})-\check{\Lambda}^{*}(e_{x}\mid
s)G^{\mathcal{V}}(\check{\mathbf{L}}^{*}(s))(e_{x},e_{y})\\\
&\quad=\bar{\Lambda}^{n}(e_{x}\mid
t_{n}-s)G^{\mathcal{V}}(\check{\mathbf{L}}^{*}(s))(e_{x},e_{y})-\check{\Lambda}^{*}(e_{x}\mid
s)G^{\mathcal{V}}(\check{\mathbf{L}}^{*}(s))(e_{x},e_{y})\\\
&\quad=\check{\Lambda}^{n}(e_{x}\mid
s)G^{\mathcal{V}}(\check{\mathbf{L}}^{*}(s))(e_{x},e_{y})-\check{\Lambda}^{*}(e_{x}\mid
s)G^{\mathcal{V}}(\check{\mathbf{L}}^{*}(s))(e_{x},e_{y})\end{split}$ (4.26)

Letting

$h(s)\doteq\exp(-s)G^{\mathcal{V}}(\check{\mathbf{L}}^{*}(s))(e_{x},e_{y}),\;s\in\mathbb{R}_{+},$

we see that

$\displaystyle\int_{0}^{t}\exp(-s)\left(\delta_{\bar{\nu}^{n,m(t_{n}-s)+1}}\otimes
G^{\mathcal{V}}(\check{\mathbf{L}}^{*}(s))(e_{x},e_{y})-\check{\Lambda}^{*}(e_{x}\mid
s)G^{\mathcal{V}}(\check{\mathbf{L}}^{*}(s))(e_{x},e_{y})\right)ds$
$\displaystyle\quad=\int_{0}^{t}h(s)\check{\Lambda}^{n}(e_{x}\mid
s)ds-\int_{0}^{t}h(s)\check{\Lambda}^{*}(e_{x}\mid
s)ds=\int_{0}^{t}h(s)\check{\Lambda}^{n}(e_{x}\times
ds)-\int_{0}^{t}h(s)\check{\Lambda}^{*}(e_{x}\times ds)$

which converges to $0$ a.s. since $\check{\Lambda}^{n}\to\check{\Lambda}^{*}$
a.s. in $\mathcal{M}(\mathcal{V}^{d}\times\mathbb{R}_{+})$ and $h$ is a
continuous and bounded function. To complete the proof of (f) it now suffices
to show that for all $x\in\Delta^{o}$ and $t\in\mathbb{R}_{+}$,

$\left|\int_{0}^{t}h(s)\delta_{\bar{\nu}^{n,m(t_{n}-s)+1}}(e_{x})ds-\int_{0}^{t}h(s)\delta_{\bar{\nu}^{n,m(t_{n}-s)}}(e_{x})ds\right|\to
0,\;\mbox{ a.s. }$ (4.27)

Fix $t\in\mathbb{R}_{+}$ and $\varepsilon>0$, and let $\kappa>0$ be such that
$|h(s)-h(s^{\prime})|\leq\varepsilon$ whenever $|s-s^{\prime}|\leq\kappa$ and
$s,s^{\prime}\in[0,t]$. Let, for $k\in\mathbb{N}$,
$\sigma(k)\doteq\delta_{\bar{\nu}^{n,k}}(e_{x})$ and choose
$n_{0}\in\mathbb{N}$ such that $m(t_{n_{0}}-t)^{-1}<\kappa$. Then, for $n\geq
n_{0}$, the quantity on the left side of (4.27) can be written as

$\displaystyle\left|\int_{t_{n}-t}^{t_{n}}h(t_{n}-s)(\sigma(m(s)+1)-\sigma(m(s)))ds\right|$
$\displaystyle\leq\left|\sum_{k=m(t_{n}-t)}^{n-1}(\sigma(k+1)-\sigma(k))\int_{t_{k}}^{t_{k+1}}h(t_{n}-s)ds\right|+m(t_{n}-t)^{-1}\|h\|_{t,\infty}$
$\displaystyle\leq\left|\sum_{k=m(t_{n}-t)}^{n-1}\left(\frac{1}{k+2}\sigma(k+1)h(t_{n}-t_{k+1})-\frac{1}{k+2}\sigma(k)h(t_{n}-t_{k})\right)\right|+2\varepsilon
t+m(t_{n}-t)^{-1}\|h\|_{t,\infty},$

where $\|h\|_{t,\infty}\doteq\sup_{0\leq s\leq t}|h(s)|$. The last expression
can be bounded above by

$2\varepsilon
t+2m(t_{n}-t)^{-1}\|h\|_{t,\infty}+\|h\|_{t,\infty}\sum_{k=m(t_{n}-t)}^{n-1}\left(\frac{1}{k+1}-\frac{1}{k+2}\right)\leq
2\varepsilon t+3m(t_{n}-t)^{-1}\|h\|_{t,\infty}.$

Taking the limit as $n\to\infty$, we now have that

$\limsup_{n\to\infty}\left|\int_{0}^{t}h(s)\delta_{\bar{\nu}^{n,m(t_{n}-s)+1}}(e_{x})ds-\int_{0}^{t}h(s)\delta_{\bar{\nu}^{n,m(t_{n}-s)}}(e_{x})ds\right|\leq
2\varepsilon t.$

Since $\varepsilon>0$ is arbitrary, the statement in (4.27) follows.

  7. (g)

The first statement is immediate on noting that for $t\in\mathbb{R}_{+}$,
$\check{\mathbf{L}}^{n}(t)=(\check{\mathbf{\mathcal{T}}}^{n}(t))_{(1)}$, and
for $k\in\mathbb{N}$,

$\|\bar{\mathcal{T}}^{n,k+1}_{(2)}-\bar{\mathcal{T}}^{n,k+1}_{(1)}\|\leq
2(k+1)^{-1}.$

The second statement follows from the fact that whenever
$(x,y)\in(A_{+})^{c}$, $\bar{\mathcal{T}}^{n,k+1}(x,y)=0$ a.e. for all
$n\in\mathbb{N}$ and $k\in\mathbb{N}_{0}$. The final statement follows
immediately from (3.25) and the fact that $\check{\mathbf{\mathcal{T}}}^{n}$
converges a.s. to $\check{\mathbf{\mathcal{T}}}^{*}$ as $n\to\infty$.

∎

###  4.2 Proof of Laplace Upper Bound

###### Proof of Theorem 4.1.

Fix $F\in C_{b}(\mathcal{P}(\Delta^{o}))$ and $\varepsilon>0$. From the
variational representation in (3.11), for each $n\in\mathbb{N}$ we can find
$\\{\bar{\mu}^{n,i}\\}\in\Theta^{n}$ such that

$-n^{-1}\log E\exp[-nF(L^{n+1})]\\\ \geq
E\left[F(\bar{L}^{n}(t_{n}))+n^{-1}\sum\limits_{k=0}^{n-1}R\left(\delta_{\bar{\nu}^{n,k}}\otimes\bar{\mu}^{n,k+1}\|\delta_{\bar{\nu}^{n,k}}\otimes
G^{\mathcal{V}}(\bar{L}^{n,k+1})(\bar{\nu}^{n,k},\cdot)\right)\right]-\varepsilon,$
(4.28)

where the sequence $\\{\bar{L}^{n,k},\;k\in\mathbb{N}\\}$ is defined by (3.2).

For each $n\in\mathbb{N}$, define the $\mathcal{P}(\Delta^{o})$-valued
continuous process $\bar{L}^{n}$ and random measures $\bar{\Lambda}^{n}$ on
$\mathcal{V}^{d}\times[0,t_{n}]$ according to (3.6) and (3.8) respectively.
Also define, for each $n\in\mathbb{N}$, $\gamma^{n}$, $\beta^{n}$,
$\theta^{n}$, $\check{\mathbf{L}}^{n}$, $\check{\mathbf{\mathcal{T}}}^{n}$,
and $\check{\Lambda}^{n}$ as in (3.18), (3.22), and (3.23). Recalling the
identity in (3.20) we have that

$-n^{-1}\log E\exp[-nF(L^{n+1})]\geq
E\left[F(\check{\mathbf{L}}^{n}(0))+R(\beta^{n}\|\theta^{n})\right]-\varepsilon.$
(4.29)

From Lemma 4.3, the collection
$\\{(\check{\mathbf{L}}^{n},\check{\mathbf{\mathcal{T}}}^{n},\check{\Lambda}^{n},\gamma^{n},\beta^{n},\theta^{n}),\;n\in\mathbb{N}\\}$
is tight in $C(\mathbb{R}_{+}:\mathcal{P}(\Delta^{o}))\times
C(\mathbb{R}_{+}:\mathcal{P}(\Delta^{o}\times\Delta^{o}))\times\mathcal{M}(\mathcal{V}^{d}\times\mathbb{R}_{+})\times(\mathcal{P}(\mathcal{V}^{d}\times\mathbb{R}_{+}))\times(\mathcal{P}(\mathcal{V}^{d}\times\mathcal{V}^{d}\times\mathbb{R}_{+}))^{2}$.

Let
$(\check{\mathbf{L}}^{*},\check{\mathbf{\mathcal{T}}}^{*},\check{\Lambda}^{*},\gamma^{*},\beta^{*},\theta^{*})$
be a weak limit point of the above sequence and suppose without loss of
generality that the convergence holds along the full sequence and in the
almost sure sense.

From parts (c) and (d) of Lemma 4.4, the third marginal of $\beta^{*}$, namely
$\beta^{*}_{(3)}(ds)$, equals $e^{-s}ds$ a.s. Disintegrate $\beta^{*}$ as

$\beta^{*}(\\{e_{x}\\}\times\\{e_{y}\\}\times[0,t])=\int_{0}^{t}\exp(-s)\check{\eta}^{*}(\\{e_{x}\\}\times\\{e_{y}\\},s)ds,$
(4.30)

where $s\mapsto\check{\eta}^{*}(\cdot,s)$ is a measurable map from
$\mathbb{R}^{+}$ to $\mathcal{P}(\mathcal{V}^{d}\times\mathcal{V}^{d})$. Let,
for $s\in\mathbb{R}_{+}$,
$\eta^{*}(\cdot,s)\in\mathcal{P}(\Delta^{o}\times\Delta^{o})$ be defined as

$\eta^{*}(\\{x\\}\times\\{y\\},s)\doteq\check{\eta}^{*}(\\{e_{x}\\}\times\\{e_{y}\\},s),\;\;x,y\in\Delta^{o},$
(4.31)

and write $\eta^{*}(x,y\mid s)\doteq\eta^{*}(\\{x\\}\times\\{y\\},s)$, and,
for $i=1,2$, $\eta^{*}_{(i)}(\cdot\mid s)\doteq\eta^{*}_{(i)}(\cdot,s)$.

From Lemma 4.4(c), $\eta^{*}_{(1)}(s)=\eta^{*}_{(2)}(s)$ for a.e.
$s\in\mathbb{R}_{+}$. In particular $\eta^{*}$ satisfies Property (P2) in
Section (2.2) (with $\eta$ replaced by $\eta^{*}$). Thus, Property (b) in
(2.6) holds.

Moreover, if $(x,y)\in(A_{+})^{c}$, then by part (e) of Lemma 4.4, a.s.,

$\beta^{*}(\\{e_{x}\\}\times\\{e_{y}\\}\times[0,t])=0,\quad
t\in\mathbb{R}_{+},$

which shows that Property (P1) holds with $(\beta,\eta)$ replaced by
$(\beta^{*},\eta^{*})$. Consequently, Property (a) in (2.6) is satisfied.

Next, note that, from Lemma 4.4(c) and (d), for $x\in\Delta^{o}$ and
$t\in\mathbb{R}_{+}$,

$\displaystyle\int_{0}^{t}\exp(-s)\check{\Lambda}(e_{x}\mid
s)ds=\gamma^{*}(\\{e_{x}\\}\times[0,t])=\beta^{*}_{(1,3)}(\\{e_{x}\\}\times[0,t])=\int_{0}^{t}\exp(-s)\eta^{*}_{(1)}(x\mid
s)ds,$

where the last equality is from (4.30) and (4.31). This shows that for all
$x\in\Delta^{o}$ and a.e. $s\in\mathbb{R}_{+}$, $\eta^{*}_{(1)}(x\mid
s)=\check{\Lambda}(e_{x}\mid s)$ and so
$\sum_{v\in\mathcal{V}^{d}}v\check{\Lambda}(v\mid
s)(\cdot)=\eta^{*}_{(1)}(\cdot,s)$. In particular, from parts (a), (b), and
(g) of Lemma 4.4, it follows that Property (c) in (2.6) also holds (with
$\eta$ replaced by $\eta^{*}$, $M$ replaced by $\check{\mathbf{L}}^{*}$, and
$\mathbf{\mathcal{T}}$ replaced by $\check{\mathbf{\mathcal{T}}}^{*}$).

Since Properties (a), (b), and (c) of (2.6) hold a.s., it follows that
$\eta^{*}\in\mathcal{U}(\check{\mathbf{L}}^{*}(0))$ a.s. Furthermore,
$\check{\mathbf{L}}^{*}$ solves
$\mathcal{U}(\check{\mathbf{L}}^{*}(0),\eta^{*})$ a.s.

Note, from (4.30), and parts (d) and (f) of Lemma 4.4, that

$(\gamma^{*},\beta^{*},\theta^{*})=\left(\exp(-s)\check{\Lambda}^{*}(\cdot\mid
s)ds,\;\exp(-s)\check{\eta}^{*}(\cdot\mid
s)ds,\;\exp(-s)\check{\Lambda}^{*}(\cdot\mid s)\otimes
G^{\mathcal{V}}(\check{\mathbf{L}}^{*}(s))(\cdot,\cdot)ds\right).$ (4.32)

For $s\in\mathbb{R}_{+}$, disintegrate

$\eta^{*}(x,y\mid s)=\eta^{*}_{(1)}(x\mid s)\eta^{*}_{2|1}(y\mid
s,x),\;\;(x,y)\in\Delta^{o}\times\Delta^{o}.$ (4.33)

Then, using (4.29),

$\varepsilon+\liminf_{n\to\infty}-n^{-1}\log E\exp[-nF(L^{n+1})]\\\
\geq\liminf_{n\to\infty}E\left[F(\check{\mathbf{L}}^{n}(0))+R(\beta^{n}\|\theta^{n})\right]\geq\left[F(\check{\mathbf{L}}^{*}(0))+R(\beta^{*}\|\theta^{*})\right]\\\
=\left[F(\check{\mathbf{L}}^{*}(0))+R\left(\exp(-s)\check{\eta}^{*}(\cdot\mid
s)ds\big{\|}\exp(-s)\check{\Lambda}^{*}(\cdot\mid s)\otimes
G^{\mathcal{V}}(\check{\mathbf{L}}^{*}(s))(\cdot,\cdot)ds\right)\right]\\\
=\left[F(\check{\mathbf{L}}^{*}(0))+\int_{0}^{\infty}\exp(-s)R\left(\eta^{*}(\cdot\mid
s)\big{\|}\eta^{*}_{(1)}(x\mid s)\otimes
G(\check{\mathbf{L}}^{*}(s))(\cdot,\cdot)\right)ds\right]\\\
=\left[F(\check{\mathbf{L}}^{*}(0))+\int_{0}^{\infty}\exp(-s)\sum_{x\in\Delta^{o}}\eta^{*}_{(1)}(x\mid
s)R\left(\eta^{*}_{2|1}(\cdot\mid
s,x)\big{\|}G(\check{\mathbf{L}}^{*}(s))(x,\cdot)\right)ds\right]\\\
\geq\left[F(\check{\mathbf{L}}^{*}(0))+I(\check{\mathbf{L}}^{*}(0))\right]\geq\inf_{m\in\mathcal{P}(\Delta^{o})}\left[F(m)+I(m)\right],$

where the second inequality uses Fatou’s lemma and the lower semicontinuity of
relative entropy, the third line uses (4.32), the fourth line uses the chain
rule for relative entropies (see [14, Corollary 2.7]) (observe that the
relative entropies in lines three and four are on different spaces), the
relationship between $\eta^{*}$, $\check{\eta}^{*}$, and $\check{\Lambda}$,
and the relationship between $G$ and $G^{\mathcal{V}}$, the fifth line again
uses the chain rule for relative entropies and the disintegration in (4.33),
and the last line uses the fact that $\check{\mathbf{L}}^{*}$ solves
$\mathcal{U}(\check{\mathbf{L}}^{*}(0),\eta^{*})$, and the expression of the
rate function $I$ given in (2.7). The result follows on letting
$\varepsilon\to 0$. ∎

##  5 Laplace Lower Bound

We now proceed to the large deviation lower bound. The main result in this
direction is the following.

######  Theorem 5.1.

Suppose that Assumption 2.2 is satisfied. Then, for every $F\in
C_{b}(\mathcal{P}(\Delta^{o}))$,

$\limsup_{n\to\infty}-n^{-1}\log
E\exp[-nF(L^{n+1})]\leq\inf_{m\in\mathcal{P}(\Delta^{o})}[F(m)+I(m)],$

where $I$ is defined using the matrix $A$ in Assumption 2.2.

The proof of the above theorem is completed in this section and the next, and
in both of these sections Assumption 2.2 is assumed to hold throughout and the
matrix $A$ is as in this assumption.

We now proceed to construct a suitable near-optimal path. We begin in the
following subsection with the selection of a near-optimal control and
trajectory and then in successive sections, by a series of approximations, we
suitably modify these quantities, culminating in Section 5.4 in the final form
of the simple form controls and paths that will be used in the lower bound
proof.

###  5.1 Near-Optimal Control

Fix $F\in C_{b}(\mathcal{P}(\Delta^{o}))$ and $\varepsilon\in(0,1)$. In order
to prove Theorem 5.1 we can assume without loss of generality that $F$ is
Lipschitz (see [14, Corollary 1.10]), i.e., for some
$F_{\mbox{\tiny{lip}}}\in(0,\infty)$,

$|F(m)-F(\tilde{m})|\leq
F_{\mbox{\tiny{lip}}}\|m-\tilde{m}\|,\;m,\tilde{m}\in\mathcal{P}(\Delta^{o}).$

Choose $m^{0}\in\mathcal{P}(\Delta^{o})$ such that

$F(m^{0})+I(m^{0})\leq\inf_{m\in\mathcal{P}(\Delta^{o})}[F(m)+I(m)]+\varepsilon.$
(5.1)

Recall the definition of the rate function from (2.7) given in terms of
$\eta\in\mathcal{U}$. In proofs it will sometimes be convenient to work with
analogues of $\eta$ that are probability measures on
$\mathcal{P}(\mathcal{V}^{d}\times\mathcal{V}^{d})$. In particular, for
$\eta\in\mathcal{U}$, we define
$\eta^{\mathcal{V}}:\mathbb{R}_{+}\to\mathcal{P}(\mathcal{V}^{d}\times\mathcal{V}^{d})$
as

$\eta^{\mathcal{V}}(s)(e_{x},e_{y})\doteq\eta(x,y\mid s),\;x,y\in\Delta^{o}.$
(5.2)

Observe that the map defined in (2.7) can be rewritten as

$I(m)=\inf\limits_{\eta\in\mathcal{U}(m)}\int_{0}^{\infty}\exp(-s)\sum\limits_{x\in\Delta^{o}}\eta^{\mathcal{V}}_{(1)}(e_{x}\mid
s)R\left(\eta^{\mathcal{V}}_{2|1}(\cdot\mid
s,e_{x})\|G^{\mathcal{V}}(M(s))(e_{x},\cdot)\right)ds,$ (5.3)

where $\eta^{\mathcal{V}}(s)(e_{x},e_{y})=\eta^{\mathcal{V}}_{(1)}(e_{x}\mid
s)\eta^{\mathcal{V}}_{2|1}(\cdot\mid s,e_{x})$. Also note that the relative
entropy in (2.7) is computed for probability measures on $\Delta^{o}$ while
the relative entropy in (5.3) is computed for probability measures on
$\mathcal{V}^{d}$.

We choose $\eta^{0}\in\mathcal{U}(m^{0})$ such that, with
$\eta^{0,\mathcal{V}}$ defined by the right side of (5.2) (with $\eta$
replaced with $\eta^{0}$),

$\int_{0}^{\infty}\exp(-s)\sum_{x\in\Delta^{o}}\eta^{0,\mathcal{V}}_{(1)}(e_{x}\mid
s)R\left(\eta^{0,\mathcal{V}}_{2|1}(\cdot\mid
s,e_{x})\|G^{\mathcal{V}}(M^{0}(s))(e_{x},\cdot)\right)\leq
I(m^{0})+\varepsilon,$ (5.4)

where $M^{0}$ solves $\mathcal{U}(m^{0},\eta^{0})$. From the definition of
$\mathcal{U}(m_{0})$, there is a $\mathcal{T}^{0}\in
C([0,\infty):\mathcal{P}(\Delta^{o}\times\Delta^{o}))$ such that, for each
$t\in\mathbb{R}_{+}$,
$(\mathcal{T}^{0}(t))_{(1)}=(\mathcal{T}^{0}(t))_{(2)}=M^{0}(t)$ and
$\mathcal{T}^{0}(t)(x,y)=0$ whenever $(x,y)\in(A_{+})^{c}$.

We now modify $M^{0}$ and $\eta^{0}$ to construct a more tractable near-
optimal trajectory.

###  5.2 Step 1: Ensuring Nondegeneracy.

Our first approximation step ensures that the probability measure that appears
in the second argument of the relative entropy terms of the form in (5.4) are
suitably nondegenerate. Let, for each $z\in\Delta^{o}$,
$\Delta_{+}(z)\doteq\\{y\in\Delta^{o}:A_{z,y}>0\\}$, and recall the constant
$\delta_{0}^{A}\in(0,\infty)$ from Assumption 2.2(2b). Note that from
Assumption 2.2(3), there is a $\pi^{*}\in\mathcal{P}_{+}(\Delta^{o})$
satisfying

$\sum_{x\in\Delta^{o}}\pi^{*}_{x}G(\pi^{*})_{x,y}=\pi^{*}_{y},\;y\in\Delta^{o}.$
(5.5)

It will be helpful to consider the measure
$\pi^{\mathcal{V},*}\in\mathcal{P}(\mathcal{V}^{d})$ defined by
$\pi^{\mathcal{V},*}_{e_{x}}\doteq\pi^{*}_{x}$, $x\in\Delta^{o}$, so that

$\sum\limits_{v\in\mathcal{V}^{d}}\pi^{\mathcal{V},*}_{v}G^{\mathcal{V}}(\pi^{*})_{v,u}=\pi^{\mathcal{V},*}_{u},\;u\in\mathcal{V}^{d}.$

Let

$\delta_{0}^{\pi^{*}}\doteq\inf\limits_{x\in\Delta^{o}}\pi^{*}_{x},\;\;\delta_{0}^{G,\pi^{*}}\doteq\inf\limits_{(x,y)\in
A_{+}}\pi^{*}_{x}G(\pi^{*})_{x,y},$ (5.6)

and note that

$\delta_{0}^{G,\pi^{*}}\geq\delta_{0}^{A}(\delta_{0}^{\pi^{*}})^{2}>0.$ (5.7)

Let, for $x,y\in\Delta^{o}$ and $s\in\mathbb{R}_{+}$,

$M^{*}(s)\doteq\pi^{*},\quad\eta^{*}(x,y\mid
s)\doteq\pi^{*}_{x}G(\pi^{*})_{x,y},$

and observe that $\eta^{*}\in\mathcal{U}(\pi^{*})$ and $M^{*}$ solves
$\mathcal{U}(\pi^{*},\eta^{*})$. Define, for $\kappa\in(0,1)$ and
$t\in\mathbb{R}_{+}$,

$\displaystyle M^{\kappa}(t)\doteq(1-\kappa)M^{0}(t)+\kappa
M^{*}(t),\;\eta^{\kappa}(\cdot\mid t)$
$\displaystyle\doteq(1-\kappa)\eta^{0}(\cdot\mid t)+\kappa\eta^{*}(\cdot\mid
t),\;m^{\kappa}\doteq(1-\kappa)m^{0}+\kappa\pi^{*},$ (5.8)

and observe that with

$\mathcal{T}^{*}(t)\doteq\pi^{*}G(\pi^{*}),\;\mathcal{T}^{\kappa}(t)\doteq(1-\kappa)\mathcal{T}^{0}(t)+\kappa\mathcal{T}^{*}(t),\;\;t\in\mathbb{R}_{+},$

we have that
$(\mathcal{T}^{\kappa}(t))_{(1)}=(\mathcal{T}^{\kappa}(t))_{(2)}=M^{\kappa}(t)$.
Also note that, since $M^{0}(t)\in\mathcal{P}^{*}(\Delta^{o})$ and
$M^{*}(t)\in\mathcal{P}^{*}(\Delta^{o})$, we have that
$M^{\kappa}(t)\in\mathcal{P}^{*}(\Delta^{o})$ for every $t\in\mathbb{R}_{+}$,
in fact we have that $\text{supp}(\mathcal{T}^{\kappa}(t))=A_{+}$ for each
$t\in\mathbb{R}_{+}.$ From these observations we see that
$\eta^{\kappa}\in\mathcal{U}(m^{\kappa})$ and $M^{\kappa}$ solves
$\mathcal{U}(m^{\kappa},\eta^{\kappa})$.

For each $t\in\mathbb{R}_{+}$ and $x,y\in\Delta^{o}$, define

$\tau^{\kappa}(x,y\mid t)=\frac{\kappa(1-\kappa)\eta^{0}(x,y\mid
t)+\kappa\pi^{*}_{x}G(\pi^{*})_{x,y}}{2\kappa(1-\kappa)+\kappa^{2}},$ (5.9)

and note that for each $x,y\in\Delta^{o}$ and $t\in\mathbb{R}_{+}$,

$\displaystyle\eta^{\kappa}(x,y\mid t)$
$\displaystyle=(1-\kappa)\eta^{0}(x,y\mid
t)+\kappa\pi^{*}_{x}G(\pi^{*})_{x,y}$ (5.10)
$\displaystyle=(1-\kappa)^{2}\eta^{0}(x,y\mid
t)+(2\kappa(1-\kappa)+\kappa^{2})\tau^{\kappa}(x,y\mid t).$

Also, observe that

$\eta^{\kappa}_{(1)}(x\mid s)=(1-\kappa)\eta^{0}_{(1)}(x\mid
s)+\kappa\pi^{*}_{x},$ (5.11)

and, by Assumption 2.2(1),

$\displaystyle
G(M^{\kappa}(s))_{x,y}=G((1-\kappa)M^{0}(s)+\kappa\pi^{*})_{x,y}=(1-\kappa)G(M^{0}(s))_{x,y}+\kappa
G(\pi^{*})_{x,y}.$ (5.12)

Thus, from the previous two displays,

$\displaystyle\eta^{\kappa}_{(1)}(x\mid s)G(M^{\kappa}(s))_{x,y}$
$\displaystyle=(1-\kappa)^{2}\eta^{0}_{(1)}(x\mid
s)G(M^{0}(s))_{x,y}+\kappa(1-\kappa)\eta^{0}_{(1)}(x\mid s)G(\pi^{*})_{x,y}$
(5.13)
$\displaystyle\quad+\kappa(1-\kappa)\pi^{*}_{x}G(M^{0}(s))_{x,y}+\kappa^{2}\pi^{*}_{x}G(\pi^{*})_{x,y}$
$\displaystyle=(1-\kappa)^{2}\eta^{0}_{(1)}(x\mid
s)G(M^{0}(s))_{x,y}+\left(2\kappa(1-\kappa)+\kappa^{2}\right)\sigma^{\kappa}(x,y\mid
s),$

where for $x,y\in\Delta^{o}$ and $t\in\mathbb{R}_{+}$,

$\displaystyle\sigma^{\kappa}(x,y\mid t)$
$\displaystyle\doteq\frac{\kappa(1-\kappa)\eta^{0}_{(1)}(x\mid
s)G(\pi^{*})_{x,y}+\kappa(1-\kappa)\pi^{*}_{x}G(M^{0}(s))_{x,y}+\kappa^{2}\pi^{*}_{x}G(\pi^{*})_{x,y}}{2\kappa(1-\kappa)+\kappa^{2}}.$
(5.14)

Using the convexity of relative entropy and combining (5.10) and (5.13)

$\displaystyle\int_{0}^{\infty}\exp(-s)\sum_{x\in\Delta^{o}}\eta^{\kappa}_{(1)}(x\mid
s)R\left(\eta^{\kappa}_{2|1}(\cdot\mid
s,x)\|G(M^{\kappa}(s))(x,\cdot)\right)ds$ (5.15)
$\displaystyle\quad=\int_{0}^{\infty}\exp(-s)R\left(\eta^{\kappa}(\cdot\mid
s)\|\eta^{\kappa}_{(1)}(\cdot\mid s)\otimes
G(M^{\kappa}(s))(\cdot,\cdot)\right)ds$
$\displaystyle\quad\leq(1-\kappa)^{2}\int_{0}^{\infty}\exp(-s)R\left(\eta^{0}(\cdot\mid
s)\|\eta^{0}_{(1)}(\cdot\mid s)\otimes G(M^{0}(s))(\cdot,\cdot)\right)ds$
$\displaystyle\qquad+\left(2\kappa(1-\kappa)+\kappa^{2}\right)\int_{0}^{\infty}\exp(-s)R\left(\tau^{\kappa}(\cdot\mid
s)\|\sigma^{\kappa}(\cdot\mid s)\right)ds.$

Observe from Assumption 2.2(2a) that, for each $s\in\mathbb{R}_{+}$,
$\text{supp}(\sigma^{\kappa}(\cdot\mid s))=A_{+}$, and for all
$t\in\mathbb{R}_{+}$ and $(x,y)\in A_{+}$,

$|\log\sigma^{\kappa}(x,y\mid
t)|\leq\left|\log\left(\frac{\kappa^{2}}{2\kappa(1-\kappa)+\kappa^{2}}\pi^{*}_{x}G(\pi^{*})_{x,y}\right)\right|.$

Combining the observation in the previous display with (5.9), and (5.14), it
follows that, for $s\in\mathbb{R}_{+}$ and $\kappa\in(0,1/2)$

$\displaystyle R\left(\tau^{\kappa}(\cdot\mid s)\|\sigma^{\kappa}(\cdot\mid
s)\right)$ $\displaystyle\leq\sum_{(x,y)\in A_{+}}\tau^{\kappa}(x,y\mid
s)|\log\sigma^{\kappa}(x,y\mid s)|$ $\displaystyle\leq
d\left|\log\left(\frac{\kappa^{2}}{2\kappa(1-\kappa)+\kappa^{2}}\right)\right|+\sum_{(x,y)\in
A_{+}}\tau^{\kappa}(x,y\mid s)|\log(\pi^{*}_{x}G(\pi^{*})_{x,y})|$
$\displaystyle\leq
d\left(\left|\log\left(\frac{\kappa}{2}\right)\right|+\left|\log\delta_{0}^{G,\pi^{*}}\right|\right).$

Thus,

$\displaystyle\left(2\kappa(1-\kappa)+\kappa^{2}\right)\int_{0}^{\infty}\exp(-s)R\left(\tau^{\kappa}(\cdot\mid
s)\|\sigma^{\kappa}(\cdot\mid
s)\right)ds\leq\left(2\kappa(1-\kappa)+\kappa^{2}\right)d\left(\left|\log\left(\frac{\kappa}{2}\right)\right|+\left|\log\delta_{0}^{G,\pi^{*}}\right|\right).$
(5.16)

Choose $\kappa_{1}\in(0,1/2)$ such that

$\|m^{0}-m^{\kappa_{1}}\|\leq\frac{\min\\{(F_{\mbox{\tiny{lip}}})^{-1},1\\}\varepsilon}{2},\;\;\left(2\kappa_{1}(1-\kappa_{1})+(\kappa_{1})^{2}\right)d\left(\left|\log\left(\frac{\kappa_{1}}{2}\right)\right|+\left|\log\delta_{0}^{G,\pi^{*}}\right|\right)\leq\varepsilon/2.$
(5.17)

For convenience, write
$(m^{1},\eta^{1},M^{1},\mathcal{T}^{1})\doteq(m^{\kappa_{1}},\eta^{\kappa_{1}},M^{\kappa_{1}},\mathcal{T}^{\kappa_{1}})$.
Then,

$F(m^{1})+\int_{0}^{\infty}\exp(-s)\sum_{x\in\mathcal{V}^{d}}\eta^{1}_{(1)}(x\mid
s)R\left(\eta^{1}_{2|1}(\cdot\mid s,x)\|G(M^{1}(s))(x,\cdot)\right)ds\\\ \leq
F(m^{0})+\int_{0}^{\infty}\exp(-s)\sum_{x\in\mathcal{V}^{d}}\eta^{0}_{(1)}(x\mid
s)R\left(\eta^{0}_{2|1}(\cdot\mid
s,x)\|G(M^{0}(s))(x,\cdot)\right)ds+\varepsilon\\\
\leq\inf_{m\in\mathcal{P}(\Delta^{o})}[F(m)+I(m)]+3\varepsilon,$ (5.18)

where we have used the Lipschitz property of $F$, (5.15), (5.16), and (5.17)
for the first inequality, and the displays in (5.1) and (5.4) for the second
inequality.

Note that, for each $s\in\mathbb{R}_{+}$,
$\text{supp}(\eta^{1}_{(1)}(\cdot\mid s)\otimes
G(M^{1}(s))(\cdot,\cdot))=A_{+},$ and that, from (5.7), (5.11), and (5.12),
with $\delta_{0}^{M_{1}}\doteq\kappa^{2}_{1}\delta_{0}^{G,\pi^{*}}$,

$\begin{split}\inf_{s\in\mathbb{R}_{+}}\inf_{(x,y)\in
A_{+}}G(M^{1}(s))(x,y)\geq\inf_{s\in\mathbb{R}_{+}}\inf_{(x,y)\in
A_{+}}\eta^{1}_{(1)}(x\mid
s)G(M^{1}(s))(x,y)\geq\delta_{0}^{M_{1}}>0,\end{split}$ (5.19)

which implies that for each $s\in\mathbb{R}_{+}$,

$R\left(\eta^{1}(\cdot\mid s)\|\eta^{1}_{(1)}(\cdot\mid s)\otimes
G(M^{1}(s))(\cdot,\cdot)\right)\leq\left|\log\delta_{0}^{M_{1}}\right|.$
(5.20)

Also, from (5.7) it follows that
$\kappa_{1}\delta_{0}^{G,\pi^{*}}\leq\kappa_{1}\delta^{\pi^{*}}_{0}$ and so,
for each $s\in\mathbb{R}_{+}$, with
$\delta\doteq\kappa_{1}\delta_{0}^{G,\pi^{*}}$,

$\inf\limits_{x\in\Delta^{o}}M^{1}(s)(x)\geq\delta,\quad\inf\limits_{(x,y)\in
A_{+}}\eta^{1}(x,y\mid s)\geq\delta,\;\mbox{ and
}\text{supp}(\eta^{1}(\cdot\mid s))=A_{+}.$ (5.21)

Recall from the proof of the upper bound that the trajectories in the
variational problem in the Laplace upper bound are related to the limit
controlled trajectories by time reversal (see e.g., (3.22) and last display in
Section 4.2). Thus, we now introduce a time reversal of $M^{1}$, which, after
further approximations, will be used to construct suitable controlled
processes in the proof of the lower bound. Fix $T\in(0,\infty)$ large enough
so that

$\exp(-T+1)\max\left\\{\left|\log\left(\frac{\delta\delta_{0}^{A}}{8}\right)\right|,\left|\log\delta_{0}^{M_{1}}\right|\right\\}\leq\varepsilon$
(5.22)

Throughout this section and the next, this $T$ is fixed. Define, for
$t\in[0,T]$,

$\hat{M}^{1}(t)\doteq M^{1}(T-t),\;\hat{\eta}^{1}(t)=\hat{\eta}^{1}(\cdot\mid
t)\doteq\eta^{1}(\cdot\mid T-t),$

and note that, since $M^{1}$ solves $\mathcal{U}(m^{1},\eta^{1})$,

$\begin{split}\hat{M}^{1}(t)=M^{1}(T)+\int_{0}^{t}\hat{\eta}_{(1)}^{1}(s)ds-\int_{0}^{t}\hat{M}^{1}(s)ds,\;t\in[0,T],\end{split}$
(5.23)

where $\hat{\eta}_{(1)}^{1}(s)=\eta_{(1)}^{1}(T-s)$. Recalling the non-
negativity of relative entropy, note that,

$\int_{0}^{\infty}\exp(-s)\sum_{x\in\Delta^{o}}\eta^{1}_{(1)}(x\mid
s)R\left(\eta^{1}_{2|1}(\cdot\mid s,x)\|G(M^{1}(s))(x,\cdot)\right)ds\\\
\geq\exp(-T)\int_{0}^{T}\exp(s)\sum_{x\in\Delta^{o}}\hat{\eta}^{1}_{(1)}(x\mid
s)R\left(\hat{\eta}^{1}_{2|1}(\cdot\mid
s,x)\big{\|}G(\hat{M}^{1}(s))(x,\cdot)\right)ds,$ (5.24)

where $\hat{\eta}^{1}_{2|1}(\cdot\mid s,x)=\eta^{1}_{2|1}(\cdot\mid T-s,x)$.

Finally, disintegrating $\mathcal{T}^{1}(T)$ as
$\mathcal{T}^{1}(T)(x,y)=M^{1}(T)(x)Q(x,y)$, $x,y\in\Delta^{o}$, we have that
$M^{1}(T)$ is a stationary distribution of the Markov chain with transition
probability kernel $Q$. Also, on recalling that
$\text{supp}(M^{1}(T))=\Delta^{o}$ and
$\text{supp}(\mathcal{T}^{1}(T))=A_{+}$, we see that $Q(x,y)=0$ if and only if
$(x,y)\in(A_{+})^{c}$, from which it follows that the kernel $Q$ is
irreducible and has unique stationary distribution $M^{1}(T)$.

###  5.3 Step 2: Continuity of Control

Our next step mollifies the control $\hat{\eta}^{1}$ in a suitable manner so
that it can be discretized at a later step. For $\kappa>0$, define

$\hat{\eta}^{1,\kappa}(s)\doteq\kappa^{-1}\int_{s}^{\kappa+s}\hat{\eta}^{1}(u)du,\;s\in[0,T],$
(5.25)

where $\hat{\eta}^{1}(u)\doteq\hat{\eta}^{1}(T)$ for $u\geq T$. Also, define
for $t\in[0,T]$,

$\hat{M}^{1,\kappa}(t)\doteq
M_{1}(T)+\int_{0}^{t}\hat{\eta}_{(1)}^{1,\kappa}(s)ds-\int_{0}^{t}\hat{M}^{1,\kappa}(s)ds.$
(5.26)

Note that there is a unique $\hat{M}^{1,\kappa}\in C([0,T]:\mathbb{R}^{d})$
that solves (5.26), and that this $\hat{M}^{1,\kappa}$ satisfies, for each
$s\in[0,T]$, $\sum\limits_{x\in\Delta^{o}}\hat{M}^{1,\kappa}(s)(x)=1$. We now
show that for $\kappa$ sufficiently small we have
$\inf_{s\in[0,T]}\inf_{x\in\Delta^{o}}\hat{M}^{1,\kappa}(s)(x)>0$, namely that
the solution to (5.26) in fact belongs to
$C([0,T]:\mathcal{P}_{+}(\Delta^{o}))$. We can write, for $t\in[0,T]$,

$\hat{M}^{1,\kappa}(t)=M_{1}(T)+\int_{0}^{t}\hat{\eta}^{1}_{(1)}(s)ds-\int_{0}^{t}\hat{M}^{1,\kappa}(s)ds+\mathcal{R}_{1}^{\kappa}(t),$
(5.27)

where

$\mathcal{R}_{1}^{\kappa}(t)\doteq\int_{0}^{t+\kappa}\hat{\eta}_{(1)}^{1}(u)\kappa^{-1}\int_{(u-\kappa)^{+}}^{u\wedge
t}dsdu-\int_{0}^{t}\hat{\eta}^{1}_{(1)}(u)du.$

Observe that, for each $t\in[0,T]$, $\|\mathcal{R}^{\kappa}_{1}(t)\|\leq
3\kappa$. Combining this estimate with (5.23) and (5.27), we have, for
$t\in[0,T]$,

$\|\hat{M}^{1,\kappa}(t)-\hat{M}^{1}(t)\|\leq
3\kappa+\int_{0}^{t}\|\hat{M}^{1,\kappa}(s)-\hat{M}^{1}(s)\|ds,$

from which we see, by an application of Grönwall’s lemma, that

$\sup_{t\in[0,T]}\|\hat{M}^{1,\kappa}(t)-\hat{M}^{1}(t)\|\leq 3\kappa\exp(T).$
(5.28)

Recall the definition of $\delta$ from above (5.21), and let

$c_{1}\doteq 2\left(\delta^{2}\delta_{0}^{A}\right)^{-1}.$ (5.29)

Assume that $\kappa$ is small enough so that

$3\kappa\exp(T)\leq\min\left\\{\frac{\varepsilon}{2}\min\\{1,F_{\text{lip}}^{-1}\\},\frac{\varepsilon}{2c_{1}},\frac{\delta}{2}\right\\},$
(5.30)

and

$2c_{1}L_{G}\kappa+\kappa(e^{1-T}+1)\left|\log\delta^{M_{1}}_{0}\right|<\frac{\varepsilon}{2}.$
(5.31)

This, in particular, in view of (5.21) and (5.28), ensures that
$\hat{M}^{1,\kappa}\in C([0,T]:\mathcal{P}_{+}(\Delta^{o}))$, and in fact

$\inf_{s\in[0,T]}\inf_{x\in\Delta^{o}}\hat{M}^{1,\kappa}(s)(x)\geq\delta/2.$
(5.32)

Next, we write

$\displaystyle\int_{0}^{T}\exp(s)R\left(\hat{\eta}^{1,\kappa}(\cdot\mid
s)\big{\|}\hat{\eta}_{(1)}^{1,\kappa}(\cdot\mid s)\otimes
G(\hat{M}^{1,\kappa}(s))(\cdot,\cdot)\right)ds$
$\displaystyle=\int_{0}^{T}\exp(s)R\left(\kappa^{-1}\int_{s}^{\kappa+s}\hat{\eta}^{1}(\cdot\mid
u)du\big{\|}\kappa^{-1}\int_{s}^{\kappa+s}\hat{\eta}_{(1)}^{1}(\cdot\mid
u)\otimes G(\hat{M}^{1}(u))(\cdot,\cdot)du\right)ds+\mathcal{R}_{1},$ (5.33)

where

$\displaystyle\mathcal{R}_{1}$
$\displaystyle=\int_{0}^{T}\exp(s)R\left(\kappa^{-1}\int_{s}^{\kappa+s}\hat{\eta}^{1}(\cdot\mid
u)du\big{\|}\kappa^{-1}\int_{s}^{\kappa+s}\hat{\eta}_{(1)}^{1}(\cdot\mid
u)\otimes G(\hat{M}^{1,\kappa}(s))(\cdot,\cdot)du\right)ds$
$\displaystyle\quad-\int_{0}^{T}\exp(s)R\left(\kappa^{-1}\int_{s}^{\kappa+s}\hat{\eta}^{1}(\cdot\mid
u)du\big{\|}\kappa^{-1}\int_{s}^{\kappa+s}\hat{\eta}_{(1)}^{1}(\cdot\mid
u)\otimes G(\hat{M}^{1}(u))(\cdot,\cdot)du\right)ds.$ (5.34)

Observe from (5.21), (5.29) and (5.32) that, for $s\in[0,T]$ and $(x,y)\in
A_{+}$,

$\displaystyle\left|\log\left(\kappa^{-1}\int_{s}^{\kappa+s}\hat{\eta}_{(1)}^{1}(x\mid
u)G(\hat{M}^{1,\kappa}(s))(x,y)du\right)-\log\left(\kappa^{-1}\int_{s}^{\kappa+s}\hat{\eta}_{(1)}^{1}(x\mid
u)G(\hat{M}^{1}(u))(x,y)du\right)\right|$ $\displaystyle\leq
c_{1}\kappa^{-1}\left|\int_{s}^{\kappa+s}\hat{\eta}_{(1)}^{1}(x\mid
u)G(\hat{M}^{1,\kappa}(s))(x,y)du-\int_{s}^{\kappa+s}\hat{\eta}_{(1)}^{1}(x\mid
u)G(\hat{M}^{1}(u))(x,y)du\right|.$ (5.35)

Also, for each $s\in[0,T]$,

$\displaystyle\kappa^{-1}\sum\limits_{(x,y)\in
A_{+}}\left|\int_{s}^{\kappa+s}\hat{\eta}_{(1)}^{1}(x\mid
u)G(\hat{M}^{1,\kappa}(s))(x,y)du-\int_{s}^{\kappa+s}\hat{\eta}_{(1)}^{1}(x\mid
u)G(\hat{M}^{1}(u))(x,y)du\right|$ $\displaystyle\quad\leq
L_{G}\left(\|\hat{M}^{1,\kappa}(s)-\hat{M}^{1}(s)\|+\kappa^{-1}\int_{s}^{\kappa+s}\|\hat{M}^{1}(s)-\hat{M}^{1}(u)\|du\right)\;\leq
L_{G}\left(\frac{\varepsilon}{2c_{1}}+2\kappa\right),$ (5.36)

where the first inequality follows from Assumption 2.1 and the last inequality
follows from (5.23), (5.28), and (5.30). Combining (5.3), (5.3), and (5.3) we
see that

$\displaystyle e^{-T}\mathcal{R}_{1}\leq
e^{-T}\int_{0}^{T}L_{G}\exp(s)\left(\frac{\varepsilon}{2}+2\kappa
c_{1}\right)ds\leq L_{G}\left(\frac{\varepsilon}{2}+2c_{1}\kappa\right).$
(5.37)

For $u\in\mathbb{R}_{+}$, let

$\mathcal{R}_{2}(u)\doteq R\left(\hat{\eta}^{1}(\cdot\mid
u)\big{\|}\hat{\eta}_{(1)}^{1}(\cdot\mid u)\otimes
G(\hat{M}^{1}(u))(\cdot,\cdot)\right).$ (5.38)

Using (5.20), we see that, for each $u\in\mathbb{R}_{+}$,
$\mathcal{R}_{2}(u)\leq\left|\log\delta_{0}^{M_{1}}\right|.$ Using the
convexity of relative entropy and (5.38), we now have that

$\displaystyle\int_{0}^{T}\exp(s)R\left(\kappa^{-1}\int_{s}^{\kappa+s}\hat{\eta}^{1}(\cdot\mid
u)du\big{\|}\kappa^{-1}\int_{s}^{\kappa+s}\hat{\eta}_{(1)}^{1}(\cdot\mid
u)\otimes G(\hat{M}^{1}(u))(\cdot,\cdot)du\right)ds$
$\displaystyle\quad\leq\int_{0}^{T}\exp(s)\kappa^{-1}\int_{s}^{\kappa+s}R\left(\hat{\eta}^{1}(\cdot\mid
u)\big{\|}\hat{\eta}_{(1)}^{1}(\cdot\mid u)\otimes
G(\hat{M}^{1}(u))(\cdot,\cdot)\right)du\,ds$
$\displaystyle\quad=\int_{0}^{T}\exp(s)\kappa^{-1}\int_{s}^{\kappa+s}\mathcal{R}_{2}(u)du\,ds,$
(5.39)

Next, on recalling that $\kappa^{-1}(1-e^{-\kappa})\leq 1$, it is easily
checked that

$\int_{0}^{T}\exp(s)\kappa^{-1}\int_{s}^{\kappa+s}\mathcal{R}_{2}(u)du\,ds=\kappa^{-1}\int_{0}^{T+\kappa}\mathcal{R}_{2}(u)\int_{(u-\kappa)^{+}}^{u\wedge
T}\exp(s)ds\,du\\\
\leq\kappa^{-1}\int_{0}^{\kappa}(\exp(u)-1)\mathcal{R}_{2}(u)\,du+\kappa^{-1}e^{T}(1-e^{-\kappa})\int_{T}^{T+\kappa}\mathcal{R}_{2}(u)du+\kappa^{-1}(1-e^{-\kappa})\int_{\kappa}^{T}\exp(u)\mathcal{R}_{2}(u)du\\\
\leq\kappa(e+e^{T})\left|\log\delta^{M_{1}}_{0}\right|+\int_{0}^{T}\exp(u)R\left(\hat{\eta}^{1}(\cdot\mid
u)\big{\|}\hat{\eta}_{(1)}^{1}(\cdot\mid u)\otimes
G(\hat{M}^{1}(u))(\cdot,\cdot)\right)du.$ (5.40)

Combining the estimates in (5.3), (5.37), (5.3), and (5.40), we have

$\begin{split}&e^{-T}\int_{0}^{T}\exp(s)R\left(\hat{\eta}^{1,\kappa}(\cdot\mid
s)\big{\|}\hat{\eta}_{(1)}^{1,\kappa}(\cdot\mid s)\otimes
G(\hat{M}^{1,\kappa}(s))(\cdot,\cdot)\right)\\\ &\quad\leq
L_{G}\left(\frac{\varepsilon}{2}+2c_{1}\kappa\right)+\kappa(e^{1-T}+1)\left|\log\delta^{M_{1}}_{0}\right|\\\
&\qquad+e^{-T}\int_{0}^{T}\exp(u)R\left(\hat{\eta}^{1}(\cdot\mid
u)\big{\|}\hat{\eta}_{(1)}^{1}(\cdot\mid u)\otimes
G(\hat{M}^{1}(u))(\cdot,\cdot)\right)du.\end{split}$

Now denote by $\kappa_{2}$ the constant $\kappa$ that satisfies (5.30) and
(5.31). Let

$(\hat{\eta}^{2},\hat{M}^{2},m^{2})\doteq(\hat{\eta}^{1,\kappa_{2}},\hat{M}^{1,\kappa_{2}},\hat{M}^{1,\kappa_{2}}(T)).$

Note from (5.28) and (5.30) that

$|F(m^{2})-F(m^{1})|=|F(\hat{M}^{1,\kappa_{2}}(T))-F(\hat{M}^{1}(T))|\leq\varepsilon/2.$

Thus,

$F(m^{2})+e^{-T}\int_{0}^{T}\exp(s)\sum_{x\in\Delta^{o}}\hat{\eta}^{2}_{(1)}(x\mid
s)R\left(\hat{\eta}^{2}_{(2)}(\cdot\mid
s,x)\big{\|}G(\hat{M}^{2}(s))(x,\cdot)\right)ds\\\ \leq
L_{G}\varepsilon/2+\varepsilon/2+F(m^{1})+e^{-T}\int_{0}^{T}\exp(u)R\left(\hat{\eta}^{1}(\cdot\mid
u)\big{\|}\hat{\eta}_{(1)}^{1}(\cdot\mid u)\otimes
G(\hat{M}^{1}(u))(\cdot,\cdot)\right)du\\\
\leq\inf_{m\in\mathcal{P}(\Delta^{o})}[F(m)+I(m)]+(4+L_{G})\varepsilon,$
(5.41)

where for the last inequality we have used (5.18) and (5.24). Furthermore,
from (5.26),

$\hat{M}^{2}(t)=M_{1}(T)+\int_{0}^{t}\hat{\eta}_{(1)}^{2}(s)ds-\int_{0}^{t}\hat{M}^{2}(s)ds,\;t\in[0,T],\;\;\hat{M}^{2}(T)=m_{2}.$
(5.42)

By construction,
$\hat{\eta}^{2}\in\mathcal{C}(\mathbb{R}_{+}:\mathcal{P}(\Delta^{o}\times\Delta^{o}))$,
and we can find $C_{1}\doteq C_{1}(\kappa_{2})\in(0,\infty)$ such that

$\|\hat{\eta}^{2}(s)-\hat{\eta}^{2}(t)\|\leq C_{1}|s-t|,\;\;s,t\in[0,T],$
(5.43)

and, on recalling (5.21) and (5.32), observe that

$\inf\limits_{s\in[0,T]}\inf\limits_{(x,y)\in A_{+}}\hat{\eta}^{2}(x,y\mid
s)\geq\delta,\;\;\inf_{s\in[0,T],x\in\Delta^{o}}\hat{M}^{2}(s)(x)\geq\delta/2.$
(5.44)

###  5.4 Step 3: Piecewise Constant Approximation

Now we carry out the last step in the approximation, which is to replace
continuous controls by piecewise constant controls. For $\kappa>0$, define
$\hat{\eta}^{2,\kappa}$ as

$\hat{\eta}^{2,\kappa}(\cdot\mid s)\doteq\sum\limits_{j=0}^{\lfloor
T\kappa^{-1}\rfloor-1}\hat{\eta}^{2}(\cdot\mid
j\kappa)\bm{1}_{[j\kappa,(j+1)\kappa)}(s)+\hat{\eta}^{2}(\cdot\mid\lfloor
T\kappa^{-1}\rfloor\kappa)\bm{1}_{[\lfloor
T\kappa^{-1}\rfloor\kappa,T]}(s),\;\;s\in[0,T].$ (5.45)

Let $\hat{M}^{2,\kappa}$ solve the equation

$\hat{M}^{2,\kappa}(t)=M^{1}(T)+\int_{0}^{t}\hat{\eta}_{(1)}^{2,\kappa}(s)ds-\int_{0}^{t}\hat{M}^{2,\kappa}(s)ds,\;t\geq
0.$ (5.46)

Then, with
$\mathcal{R}^{\kappa}_{2}(t)\doteq\int_{0}^{t}\hat{\eta}_{(1)}^{2,\kappa}(s)ds-\int_{0}^{t}\hat{\eta}_{(1)}^{2}(s)ds$,
we have that, for $t\in[0,T]$,

$\hat{M}^{2,\kappa}(t)=M_{1}(T)+\int_{0}^{t}\hat{\eta}_{(1)}^{2}(s)ds-\int_{0}^{t}\hat{M}^{2,\kappa}(s)+\mathcal{R}_{2}^{\kappa}(t).$
(5.47)

From (5.43) and the definition of $\hat{\eta}^{2,\kappa}$,

$\sup_{t\in[0,T]}\|\mathcal{R}_{2}^{\kappa}(t)\|\leq
T\left(\sup_{s,t\in[0,T],|s-t|\leq\kappa}\|\hat{\eta}^{2}(s)-\hat{\eta}^{2}(t)\|\right)\leq
C_{1}\kappa T,$

Combining the last estimate, (5.42), and (5.47), we have from Grönwall’s lemma
that

$\sup_{t\in[0,T]}\|\hat{M}^{2,\kappa}(t)-\hat{M}^{2}(t)\|\leq C_{1}\kappa
T\exp({T}).$ (5.48)

Assume that $\kappa$ is sufficiently small so that

$C_{1}\kappa
T\exp({T})\leq\min\left\\{\frac{\varepsilon}{2}\min\\{1,F_{\text{lip}}^{-1}\\},\frac{\varepsilon}{4c_{1}},\frac{\delta}{4}\right\\},$
(5.49)

and

$2\kappa(2L_{G}+C_{1})(2|\log c_{1}|+c_{1})+4\kappa
c_{1}L_{G}\leq\varepsilon,$ (5.50)

where $c_{1}$ is defined in (5.29). Then, it follows from (5.48) and (5.44)
that for this choice of $\kappa$,

$\inf_{s\in[0,T]}\inf_{x\in\Delta^{o}}\hat{M}^{2,\kappa}(s)(x)\geq\frac{\delta}{4},\;\;\inf\limits_{s\in[0,T]}\inf\limits_{(x,y)\in
A_{+}}\hat{\eta}^{2,\kappa}(x,y\mid s)\geq\delta.$ (5.51)

This shows that $\hat{M}^{2,\kappa}$ belongs to
$C([0,T]:\mathcal{P}_{+}(\Delta^{o}))$. For $t\in[0,T]$, let
$\alpha_{\kappa}(t)\doteq\lfloor t\kappa^{-1}\rfloor\kappa$ and write

$\displaystyle\int_{0}^{T}\exp(s)R\left(\hat{\eta}^{2,\kappa}(\cdot\mid
s)\big{\|}\hat{\eta}_{(1)}^{2,\kappa}(\cdot\mid s)\otimes
G(\hat{M}^{2,\kappa}(s))(\cdot,\cdot)\right)ds$
$\displaystyle\quad=\int_{0}^{T}\exp(s)R\left(\hat{\eta}^{2,\kappa}(\cdot\mid
s)\big{\|}\hat{\eta}_{(1)}^{2,\kappa}(\cdot\mid s)\otimes
G(\hat{M}^{2}(\alpha_{\kappa}(s)))(\cdot,\cdot)\right)ds+\mathcal{R}_{3},$
(5.52)

where

$\displaystyle\mathcal{R}_{3}$
$\displaystyle\doteq\int_{0}^{T}\exp(s)R\left(\hat{\eta}^{2,\kappa}(\cdot\mid
s)\big{\|}\hat{\eta}_{(1)}^{2,\kappa}(\cdot\mid s)\otimes
G(\hat{M}^{2,\kappa}(s))(\cdot,\cdot)\right)ds$
$\displaystyle\quad-\int_{0}^{T}\exp(s)R\left(\hat{\eta}^{2,\kappa}(\cdot\mid
s)\big{\|}\hat{\eta}_{(1)}^{2,\kappa}(\cdot\mid s)\otimes
G(\hat{M}^{2}(\alpha_{\kappa}(s)))(\cdot,\cdot)\right)ds.$ (5.53)

Recalling the definition of $c_{1}$ from (5.29), we have, from Assumption 2.1
and (5.51), for $(x,y)\in A_{+}$ and $s\in[0,T]$,

$\displaystyle\sum\limits_{(x,y)\in
A_{+}}\left|\log\left(\hat{\eta}_{(1)}^{2,\kappa}(x\mid
s)G(\hat{M}^{2,\kappa}(s))(x,y)\right)-\log\left(\hat{\eta}_{(1)}^{2,\kappa}(x\mid
s)G(\hat{M}^{2}(\alpha_{\kappa}(s)))(x,y)\right)\right|$
$\displaystyle\quad\leq 2c_{1}\sum\limits_{(x,y)\in
A_{+}}\left|\hat{\eta}_{(1)}^{2,\kappa}(x\mid
s)G(\hat{M}^{2,\kappa}(s))(x,y)-\hat{\eta}_{(1)}^{2,\kappa}(x\mid
s)G(\hat{M}^{2}(\alpha_{\kappa}(s)))(x,y)\right|$ $\displaystyle\quad\leq
2L_{G}c_{1}\left(\|\hat{M}^{2,\kappa}(s)-\hat{M}^{2}(s)\|+\|\hat{M}^{2}(s)-\hat{M}^{2}(\alpha_{\kappa}(s))\|\right)\leq
2L_{G}c_{1}\left(\frac{\varepsilon}{4c_{1}}+2\kappa\right)=L_{G}\left(\frac{\varepsilon}{2}+4\kappa
c_{1}\right),$ (5.54)

where the last inequality is due to (5.42), (5.48), and (5.49). Combining
(5.4), and (5.4), we have that

$e^{-T}\mathcal{R}_{3}\leq
e^{-T}\int_{0}^{T}L_{G}\exp(s)\left(\frac{\varepsilon}{2}+4\kappa
c_{1}\right)ds\leq L_{G}\left(\frac{\varepsilon}{2}+4\kappa c_{1}\right).$
(5.55)

Next, using Assumption 2.1, (5.42), and (5.43), note that, for $s,u\in[0,T]$
such that $|s-u|\leq\kappa$,

$\displaystyle\sum\limits_{(x,y)\in A_{+}}|\hat{\eta}_{(1)}^{2}(x\mid
s)G(\hat{M}^{2}(s))(x,y)-\hat{\eta}_{(1)}^{2}(x\mid u)G(\hat{M}^{2}(u))(x,y)|$
$\displaystyle\quad\leq
L_{G}\|\hat{M}^{2}(s)-\hat{M}^{2}(u)\|+\|\hat{\eta}_{(1)}^{2}(\cdot\mid
s)-\hat{\eta}_{(1)}^{2}(\cdot\mid u)\|\leq\kappa(2L_{G}+C_{1}),$ (5.56)

and, using (5.51), observe that

$\inf_{s\in[0,T]}\inf\limits_{(x,y)\in A_{+}}\hat{\eta}_{(1)}^{2}(x\mid
s)G(\hat{M}^{2}(s))(x,y)\geq\frac{\delta^{2}\delta_{0}^{A}}{4}=\frac{c_{1}^{-1}}{2}.$
(5.57)

Moreover, note that if, for some $\gamma\in(0,1)$,
$a,\tilde{a},b,\tilde{b}\in(\gamma,1]$, then

$\left|a\log(a/b)-\tilde{a}\log(\tilde{a}/\tilde{b})\right|\leq\left(2|\log\gamma|+\gamma^{-1}\right)\left(|a-\tilde{a}|+|b-\tilde{b}|\right).$
(5.58)

Using (5.4), (5.57), and (5.58), we have

$\int_{0}^{T}\exp(s)R\left(\hat{\eta}^{2,\kappa}(\cdot\mid
s)\big{\|}\hat{\eta}_{(1)}^{2,\kappa}(\cdot\mid s)\otimes
G(\hat{M}^{2}(\alpha_{\kappa}(s)))(\cdot,\cdot)\right)ds\\\
\leq\int_{0}^{T}\exp(s)R\left(\hat{\eta}^{2}(\cdot\mid
s)\big{\|}\hat{\eta}_{(1)}^{2}(\cdot\mid s)\otimes
G(\hat{M}^{2}(s))(\cdot,\cdot)\right)ds\\\
+2\kappa\left(2L_{G}+C_{1}\right)\left(2|\log
c_{1}|+c_{1}\right)\int_{0}^{T}\exp(s)ds.$

Combining the estimate in the last display with (5.4) and (5.55), we have

$e^{-T}\int_{0}^{T}\exp(s)R\left(\hat{\eta}^{2,\kappa}(\cdot\mid
s)\big{\|}\hat{\eta}_{(1)}^{2,\kappa}(\cdot\mid s)\otimes
G(\hat{M}^{2,\kappa}(s))(\cdot,\cdot)\right)ds\\\ \leq
e^{-T}\int_{0}^{T}\exp(s)R\left(\hat{\eta}^{2}(\cdot\mid
s)\big{\|}\hat{\eta}_{(1)}^{2}(\cdot\mid s)\otimes
G(\hat{M}^{2}(s))(\cdot,\cdot)\right)ds\\\ +2\kappa(2L_{G}+C_{1})(2|\log
c_{1}|+c_{1})+L_{G}\left(\varepsilon/2+4\kappa c_{1}\right).$ (5.59)

Now, denote by $\kappa_{3}$ the constant $\kappa$ that satisfies (5.49) and
(5.50) and let

$(\hat{\eta}^{3},\hat{M}^{3},m^{3})\doteq(\hat{\eta}^{2,\kappa_{3}},\hat{M}^{2,\kappa_{3}},\hat{M}^{2,\kappa_{3}}(T)).$

From (5.48) and (5.49) it follows that

$\left|F(m^{3})-F(m^{2})\right|=\left|F(\hat{M}^{2,\kappa_{3}}(T))-F(\hat{M}^{2}(T))\right|\leq\varepsilon/2.$

Combining the last display with the estimate in (5.59) and recalling our
choice of $\kappa_{3}$, we have

$F(m^{3})+e^{-T}\int_{0}^{T}\exp(s)\sum_{x\in\Delta^{o}}\hat{\eta}^{3}_{(1)}(x\mid
s)R\left(\hat{\eta}^{3}_{(2)}(\cdot\mid
s,x)\big{\|}G(\hat{M}^{3}(s))(x,\cdot)\right)ds\\\ \leq
L_{G}\varepsilon/2+\varepsilon/2+\varepsilon+F(m^{2})+e^{-T}\int_{0}^{T}e^{s}R\left(\hat{\eta}^{2}(\cdot\mid
u)\big{\|}\hat{\eta}_{(1)}^{2}(\cdot\mid u)\otimes
G(\hat{M}^{2}(u)(\cdot,\cdot)\right)du\\\
\leq\inf_{m\in\mathcal{P}(\Delta^{o})}[F(m)+I(m)]+(6+2L_{G})\varepsilon,$
(5.60)

where for the last inequality we have used (5.41). Furthermore, from (5.46),

$\hat{M}^{3}(t)=M^{1}(T)+\int_{0}^{t}\hat{\eta}_{(1)}^{3}(s)ds-\int_{0}^{t}\hat{M}^{3}(s)ds,\;t\in[0,T],\;\;\hat{M}^{3}(T)=m_{3}.$
(5.61)

By construction, for each $j\in\\{0,1,\ldots,\lfloor
T\kappa_{3}^{-1}\rfloor-1\\}$, the map $t\mapsto\hat{\eta}^{3}(\cdot\mid t)$
is constant over the interval $[j\kappa_{3},(j+1)\kappa_{3})$, as well as over
the interval $[\lfloor T\kappa_{3}^{-1}\rfloor\kappa_{3},T]$, and, from
(5.51),

$\inf\limits_{s\in[0,T]}\inf\limits_{(x,y)\in A_{+}}\hat{\eta}^{3}((x,y)\mid
s)\geq\delta,\;\;\inf_{s\in[0,T]}\inf_{x\in\Delta^{o}}\hat{M}^{3}(s)(x)\geq\delta/4.$
(5.62)

##  6 Proof of Laplace Lower Bound

In this section we will prove Theorem 5.1 by constructing a suitable sequence
of controlled processes based on the quantities $\hat{\eta}^{3},\hat{M}^{3}$
from Section 5.4.

###  6.1 Construction of Suitable Controls

To simplify notation, write

$\hat{\eta}\doteq\hat{\eta}^{3},\;\;\hat{M}\doteq\hat{M}^{3},\;\;c\doteq\kappa_{3},\;\;q\doteq
M^{1}(T),$

where ${M}^{1}$ is as in Section 5.2 and $\hat{\eta}^{3},\hat{M}^{3},$ and
$\kappa_{3}$ are as in Section 5.4.

The precise construction of the controlled processes will be given in a
recursive fashion in Construction 6.1. An informal outline of this
construction is as follows:

  * •

Use the original uncontrolled dynamics until the empirical measure charges
each point in $\Delta^{o}$. This is needed to ensure that the relative entropy
costs are well controlled and it can be done due to Assumption 2.2(4). Note
that this incurs zero cost since no control is exercised.

  * •

Once the empirical measure of the original uncontrolled dynamics has charged
each point in $\Delta^{o}$, proceed as follows. Recall the irreducible
transition probability kernel $Q$ as given at the end of Section 5.2 and note
that $q$ is the unique stationary distribution for $Q$. Until time step
$m(t_{n}-T)-1$, the controlled chain will use the kernel $Q$. Note that this
approximately corresponds to evolving according to $Q$ until the interpolated
continuous time instant $t_{n}-T$. By the ergodic theorem, at this time
instant the empirical measure will, with high probability, be very close to
$q$.

  * •

Now, over the last $T$ units of interpolated time (i.e., until time $t_{n}$),
we construct the chain successively in a manner that closely shadows the
piecewise linear trajectory $\hat{M}$. Specifically, over each time segment
$[lc,(l+1)c]$ over which $\hat{M}$ is linear and $\hat{\eta}(\cdot\mid s)$ is
constant (in $s$) we will construct the chain, for time instants that
correspond to – in the continuous time interpolation (as described in Section
3) – the interval $[lc,(l+1)c]$, using the transition probability kernel
$\hat{\eta}(\cdot\mid lc)$. Using the ergodic theorem again, the empirical
measures that are formed using this construction will be close to the
trajectory $\hat{M}$ with high probability.

  * •

Over the small probability events where deviations from the ergodic limits
occur we modify controls so that we do not expend too much control cost.

The reader may want to keep the above rough outline in mind in what follows.

Recall the constants $\delta_{0}^{A}$ and $\delta$ defined in Part 2 of
Assumption 2.2 and above (5.21), respectively. Let $l_{0}\doteq\lfloor
Tc^{-1}\rfloor$ and define

$\displaystyle b_{1}\doteq 4+c,\;\;d_{1}\doteq
e^{c}(12+c),\;\;d_{2}=6,\;\;d_{3}\doteq d_{1}+l_{0}b_{1}e^{c},\;\;d_{4}\doteq
2^{l_{0}}(3+d_{2}),\;\;\delta_{1}\doteq\delta\delta^{A}_{0}/8,$ (6.1)
$\displaystyle
A_{1}\doteq|\log\delta_{1}|+(2+d_{3})\delta_{1}^{-1},\;\;B_{1}\doteq
2d_{4}\delta_{1}^{-1},\;\;C_{1}\doteq|\log\delta_{1}|(l_{0}+3)^{2}.$

Fix $\varepsilon_{0},\varepsilon_{1}>0$ sufficiently small so that

$\varepsilon_{0}<\min\\{c,\delta/16\\},\;F_{\mbox{\tiny{lip}}}(d_{3}\varepsilon_{0}+2d_{4}\varepsilon_{1})\leq\varepsilon,\;C_{1}\varepsilon_{1}+(l_{0}+1)(A_{1}\varepsilon_{0}+B_{1}\varepsilon_{1})\leq\varepsilon.$
(6.2)

We now proceed to the first item in the above outline. Let
$\\{Z_{i},\;i\in\mathbb{N}_{0}\\}$ be a sequence of $\Delta^{o}$-valued random
variables defined recursively as follows. Recall $x_{0}\in\Delta^{o}$ as fixed
in Section 2.1 and let $Z_{0}\doteq x_{0}$. Having defined
$Z_{0},\ldots,Z_{n}$ for some $n\in\mathbb{N}_{0}$, define the conditional law
of $Z_{n+1}$ given $Z_{0},\dots,Z_{n}$ by

$P\left(Z_{n+1}=x\mid\sigma\\{Z_{0},\ldots Z_{n}\\}\right)\doteq
G(L^{n+1,Z})(Z_{n},x),\;x\in\Delta^{o},$

where $\\{L^{n,Z},\;n\in\mathbb{N}\\}$ is defined by
$L^{n,Z}\doteq\frac{1}{n}\sum_{i=0}^{n-1}\delta_{Z_{i}}$, $n\in\mathbb{N}$.
From Assumption 2.2(4) and Lemma A.1 in the Appendix, it follows that there is
an $a^{*}>0$ and $r_{1}\in\mathbb{N}$, such that with

$N_{1}(\omega)\doteq\inf\\{k\in\mathbb{N}:L^{k,Z}(\omega)(x)>a^{*}\mbox{ for
all }x\in\Delta^{o}\\},$ (6.3)

we have

$P(N_{1}>r_{1})\leq\varepsilon_{1}.$ (6.4)

We will use this sequence later in the construction to build the piece in the
first item above.

Next, we proceed to the second item in the outline given at the start of the
section. Recall $q=M^{1}(T)$ and the irreducible transition probability kernel
$Q$ as given at the end of Section 5.2 which has $q$ as the unique stationary
distribution. Also recall that

$\left(A_{+}\right)^{c}=\\{(x,y)\in\Delta^{o}\times\Delta^{o}:Q(x,y)=0\\}.$
(6.5)

Let $Q^{\mathcal{V}}\in\mathcal{K}(\mathcal{V}^{d})$ be defined as

$Q^{\mathcal{V}}(e_{x},e_{y})\doteq Q(x,y),\;\;x,y\in\Delta^{o}.$

Now, let $\\{Y_{i}(x),\;x\in\Delta^{o},i\in\mathbb{N}_{0}\\}$ be iid
$\Delta^{o}$-valued random vectors, independent of the sequence
$\\{Z_{i},\;i\in\mathbb{N}_{0}\\}$, such that

$P(Y_{i}(x)=y)=Q(x,y),\;x,y\in\Delta^{o},\;i\in\mathbb{N}_{0}.$

For each $j\in\mathbb{N}_{0}$, let

$\mathcal{G}_{j}\doteq\sigma\left\\{Z_{l},\;l\in\mathbb{N}_{0}\right\\}\vee\sigma\left\\{Y_{i}(x),\;x\in\Delta^{o},0\leq
i\leq j\right\\},$

and, for each $y\in\Delta^{o}$, define the sequence
$\\{\bar{Y}_{i}^{y},\;i\in\mathbb{N}_{0}\\}$ of $\Delta^{o}$-valued random
variables as $\bar{Y}^{y}_{0}\doteq y$, and

$P\left(\bar{Y}_{i+1}^{y}=z\mid\mathcal{G}_{i+1}\vee\sigma\\{\bar{Y}^{y}_{j},0\leq
j\leq i\\}\right)\doteq
Q(\bar{Y}^{y}_{i},z),\;\;z\in\Delta^{o},i\in\mathbb{N}_{0}.$

By using the ergodic theorem for the transition probability matrix $Q$, we can
find $k_{0}\in\mathbb{N}$ such that, with

$A_{\varepsilon_{0}}\doteq\left\\{\omega:\max_{y\in\Delta^{o}}\sup_{m\geq
k_{0}}\left\|\frac{1}{m}\sum_{i=0}^{m-1}\delta_{\bar{Y}_{i}^{y}(\omega)}-q\right\|\geq\varepsilon_{0}\right\\},$

we have

$P(A_{\varepsilon_{0}})\leq\varepsilon_{1},\mbox{ and
}k_{0}>4\epsilon_{0}^{-1}.$ (6.6)

We now go on to the third item in the outline given at the start of the
section. For that we introduce some notation that is useful in describing the
construction. For each $n\in\mathbb{N}$ let

$m^{n}_{j}\doteq m(t_{n}-T+jc),\;\;j=0,1,\dots,l_{0},$

where $l_{0}$ is defined above (6.1). For each $n\in\mathbb{N}$ and
$j=0,\dots,l_{0}$, let

$\begin{split}\mathcal{I}^{n,j}&\doteq\left\\{i\in\mathbb{N}_{0}:t_{i}\in[t_{m^{n}_{j}+1},t_{m^{n}_{j+1}})\right\\}=\\{m^{n}_{j}+1,m^{n}_{j}+2,\dots,m^{n}_{j}+l^{n,j}\\},\end{split}$
(6.7)

where $l^{n,j}\doteq|\mathcal{I}^{n,j}|$ denotes the cardinality of each of
these sets. Note that, for all $n\in\mathbb{N}$,

$m^{n}_{j}\doteq m^{n}_{j-1}+l^{n,j-1}+1,\;\;j=1,\dots,l_{0}.$

For $j=0,1,\dots,l_{0}$, we define $\beta^{j}\in\mathcal{K}(\Delta^{o})$ as

$\beta^{j}(x,y)\doteq\hat{\eta}(x,y\mid cj),\;x,y\in\Delta^{o}.$ (6.8)

Such a $\beta^{j}$ can be disintegrated as

$\beta^{j}(x,y)=\beta^{j}_{(1)}(x)\beta^{j}_{2|1}(y\mid
x),\;x,y\in\Delta^{o}.$ (6.9)

Recall from (5.62) (and the fact that $A$ is irreducible from Part 2 of
Assumption 2.2) that

$\inf_{j=0,\dots,l_{0}}\inf_{x\in\Delta^{o}}\beta^{j}_{(1)}(x)\geq\delta,\;\;\inf_{j=0,\dots,l_{0}}\inf_{(x,y)\in
A_{+}}\beta^{j}_{2|1}(y\mid x)\geq\delta.$ (6.10)

Also, by our construction of $\hat{\eta}$, for each $j=0,1,\dots,l_{0}$,

$\sum_{x\in\Delta^{o}}\beta^{j}_{(1)}(x)\beta^{j}_{2|1}(y\mid
x)=\beta^{j}_{(1)}(y),\;\;y\in\Delta^{o}.$

This is a consequence of the fact that $\eta^{0}$ introduced in Section 5.1
belongs to $\mathcal{U}(m^{0})$ (see Property (P2) in Section 2.2). The above
identity, together with (6.10), says that $\beta^{j}_{(1)}$ is the unique
stationary distribution of the Markov chain with an irreducible transition
probability function $\beta^{j}_{2|1}(\cdot\mid\cdot)$.

Let, for $j=0,1,\dots,l_{0}$, $\\{U^{j}_{i},\;i\in\mathbb{N}_{0}\\}$ be
sequences of $\Delta^{o}$-valued random variables that are mutually
independent of one another for different $j$, independent of
$\\{Z_{j},\bar{Y}^{y}_{j},\;j\in\mathbb{N}_{0},y\in\Delta^{o}\\}$, and are
distributed according to $U^{j}_{0}\sim\beta^{j}_{(1)}$, and

$P(U^{j}_{i}=y\mid\sigma\\{U^{j}_{m},\;0\leq m\leq
i-1\\})=\beta^{j}_{2|1}(y\mid U^{j}_{i-1}),\;\;i\in\mathbb{N}.$

Then, using the ergodic theorem, we can find $k^{*}\in\mathbb{N}$ such that

$P\left(\max_{j=0,\ldots,l_{0}}\,\sup_{m\geq
k^{*}}\left\|\frac{1}{m+1}\sum_{i=0}^{m}\delta_{U^{j}_{i}}-\beta^{j}_{(1)}\right\|\geq\varepsilon_{0}\right)\leq\varepsilon_{1}$
(6.11)

and

$\max_{j=0,\ldots,l_{0}}\max_{x\in\Delta^{o}}E\left(\left.\left\|\frac{1}{k^{*}+1}\sum_{i=0}^{k^{*}}\delta_{U^{j}_{i}}-\beta^{j}_{(1)}\right\|\;\;\right|U^{j}_{0}=x\right)\leq\varepsilon_{0}.$
(6.12)

Now, fix $n_{0}\in\mathbb{N}$ large enough so that, for all $n\geq n_{0}$,

$m^{n}_{0}>k_{0}+r_{1}+\lfloor
4(r_{1}+1)/\varepsilon_{0}\rfloor+1,\;\;2(m^{n}_{0}+2)^{-1}\leq\varepsilon_{0},\;m^{n}_{0}c>k^{*}.$
(6.13)

Now, we piece the above main ingredients together to construct the controlled
collection
$\\{\bar{\nu}^{n,k},\bar{L}^{n,k},\bar{\mu}^{n,k},\;n\in\mathbb{N}\\}$ as
follows.

######  Construction 6.1.

Fix $n\geq n_{0}$.

  1. (i)

Let $x_{0}\in\Delta^{o}$ be as fixed in Section 2.1. Let
$\bar{X}^{n}_{0}\doteq x_{0}$, $\bar{\nu}^{n,0}\doteq e_{x_{0}}$,
$\bar{L}^{n,1}\doteq\delta_{x_{0}}$. Define, for
$k\in\\{1,\dots,N_{1}(\omega)\wedge r_{1}\\}$,

$\bar{X}^{n}_{k}(\omega)\doteq Z_{k}(\omega),\;\bar{\nu}^{n,k}(\omega)\doteq
e_{\bar{X}^{n}_{k}(\omega)},\;\bar{L}^{n,k+1}(\omega)\doteq
L^{k+1,Z}(\omega).$

Also, set

$\bar{\mu}^{n,k}(\omega)(e_{y})\doteq
G^{\mathcal{V}}(\bar{L}^{n,k}(\omega))(e_{\bar{X}^{n}_{k-1}(\omega)},e_{y}),\;y\in\Delta^{o}.$

On the ‘low probability’ set $\\{r_{1}<N_{1}(\omega)\\}$, we once more define
$\bar{X}^{n}_{k},\bar{\nu}^{n,k},\bar{L}^{n,k+1},\bar{\mu}^{n,k}$ by the above
formulas for all $k>r_{1}$.

  2. (ii)

On the ‘high probability’ set $\\{N_{1}(\omega)\leq r_{1}\\}$ the construction
proceeds as follows. Let $k_{0}$ be as introduced above (6.6) and let
$k_{1}\doteq k_{0}+\lfloor 4(r_{1}+1)/\varepsilon_{0}\rfloor+1$. For
$k\in\\{N_{1}(\omega)+1,\ldots,N_{1}(\omega)+k_{1}\\}$, define
$\bar{X}^{n}_{k}(\omega)\doteq\bar{Y}^{\bar{X}^{n}_{N_{1}(\omega)}(\omega)}_{k-N_{1}(\omega)}(\omega)$,
and let

$\bar{\nu}^{n,k}(\omega)\doteq
e_{\bar{X}^{n}_{k}(\omega)},\;\bar{L}^{n,k+1}(\omega)\doteq\frac{1}{k+1}\sum_{j=0}^{k}\delta_{\bar{X}^{n}_{j}(\omega)},$
(6.14)

and set

$\bar{\mu}^{n,k}(\omega)(e_{y})\doteq
Q(\bar{X}^{n}_{k-1}(\omega),y),\;y\in\Delta^{o}.$ (6.15)

  3. (iii)

Again, on the set $\\{N_{1}(\omega)\leq r_{1}\\}$, let $k_{2}(\omega)\doteq
N_{1}(\omega)+k_{1}$, and define

$\tau^{n}(\omega)\doteq\inf\\{k\geq
k_{2}(\omega):\|\bar{L}^{n,k+1}(\omega)-q\|>2\varepsilon_{0}\\},\;\;k_{3}(\omega)\doteq\tau^{n}(\omega)\wedge(m^{n}_{0}-1).$

For $k\in\\{k_{2}(\omega)+1,\ldots,k_{3}(\omega)\\}$, let
$\bar{X}^{n}_{k}(\omega)\doteq\bar{Y}^{\bar{X}^{n}_{k_{2}(\omega)}(\omega)}_{k-k_{2}(\omega)}(\omega)$,
and define $\bar{\nu}^{n,k},\bar{L}^{n,k+1},\bar{\mu}^{n,k}$ by (6.14) and
(6.15). Let $\mathcal{J}_{0}^{n}(\omega)\doteq\bm{1}_{\\{\tau^{n}(\omega)\leq
m^{n}_{0}-1\\}}$. Define

$\mathcal{D}^{n}_{0}\doteq\\{N_{1}(\omega)\leq
r_{1}\\}\cap\\{\mathcal{J}_{0}^{n}(\omega)=1\\},$ (6.16)

which, in view of (6.6), is again a ‘low probability set’. On
$\mathcal{D}^{n}_{0}$, for $k\geq k_{3}(\omega)$ let $\bar{\mu}^{n,k}$ and
$\bar{X}^{n}_{k}$ be defined so that

$\bar{\mu}^{n,k}(\omega)(e_{y})\doteq
G^{\mathcal{V}}(\bar{L}^{n,k}(\omega))(e_{\bar{X}^{n}_{k-1}(\omega)},e_{y}),\;\;y\in\Delta^{o},$

and

$P(\bar{X}^{n}_{k}=y\mid\bar{\mathcal{F}}^{n,k})=\bar{\mu}^{n,k}(e_{y}),\;\;y\in\Delta^{o},$

where, as in Section 3,
$\bar{\mathcal{F}}^{n,k}=\sigma\\{\bar{L}^{n,i},\;1\leq i\leq k\\}$, and
$\bar{\nu}^{n,k},\bar{L}^{n,k+1}$ are defined by (6.14). This ensures that no
cost is incurred on this low probability event.

  4. (iv)

Now we give the construction on the ‘high probability’ set
$\mathcal{E}_{0}^{n}\doteq\\{N_{1}(\omega)\leq
r_{1}\\}\cap\\{\mathcal{J}_{0}^{n}(\omega)=0\\}$.

     * •

For $k=m_{0}^{n}$, let

$\bar{\mu}^{n,k}(\omega)(e_{y})\doteq\beta^{0}_{(1)}(y),\;\;y\in\Delta^{o},$

define $\bar{X}^{n}_{k}\doteq U^{0}_{0}$, and note that, a.e. on
$\mathcal{E}_{0}$,

$P(\bar{X}^{n}_{k}=y\mid\bar{\mathcal{F}}^{n,k})=\beta^{0}_{(1)}(y),\;\;y\in\Delta^{o},$

where $\bar{\mathcal{F}}^{n,k}=\sigma\\{\bar{L}^{n,j},1\leq j\leq k\\}$, and
$\bar{\nu}^{n,k},\bar{L}^{n,k+1}$ are defined by (6.14).

     * •

Recall the set $\mathcal{I}^{n,0}$ introduced in (6.7). Also, recall that we
have chosen $k^{*}$ so that (6.11) and (6.12) hold, and let

$\tau^{n,0}(\omega)\doteq\inf\left\\{m\geq
k^{*}:\left\|\frac{1}{m+1}\sum_{i=0}^{m}\delta_{U^{0}_{i}(\omega)}-\beta^{0}_{(1)}\right\|>\varepsilon_{0}\right\\}.$
(6.17)

For $k\in\\{m^{n}_{0}+1,\dots,m^{n}_{0}+(l^{n,0}\wedge\tau^{n,0}(\omega))\\}$,
let $\bar{X}^{n}_{k}\doteq U^{0}_{k-m^{n}_{0}}$, and note that, a.e. on
$\mathcal{E}_{0}^{n}$,

$P(\bar{X}^{n}_{k}=y\mid\bar{\mathcal{F}}^{n,k})=\beta^{0}_{2|1}(y\mid\bar{X}^{n}_{k-1}),\;\;y\in\Delta^{o},$

where $\bar{\mathcal{F}}^{n,k}$ is defined as above. Also, for
$k\in\\{m^{n}_{0}+1,\dots,m^{n}_{0}+(l^{n,0}\wedge\tau^{n,0}(\omega))\\}$,
define $\bar{\nu}^{n,k},\bar{L}^{n,k+1}$ by (6.14), and

$\bar{\mu}^{n,k}(\omega)(e_{y})\doteq\beta^{0}_{2|1}(y\mid\bar{X}^{n}_{k-1}(\omega)),\;\;y\in\Delta^{o}.$

If $\\{\tau^{n,0}(\omega)\leq l^{n,0}\\}$ occurs, then let, for $k\geq
m^{n}_{0}+\tau^{n,0}(\omega)+1$, $\bar{\mu}^{n,k}(\omega)$ and
$\bar{X}^{n}_{k}(\omega)$ be defined so that

$\bar{\mu}^{n,k}(\omega)(e_{y})\doteq
G^{\mathcal{V}}(\bar{L}^{n,k}(\omega))(e_{\bar{X}^{n}_{k-1}(\omega)},e_{y}),\;\;y\in\Delta^{o},$

and

$P(\bar{X}^{n}_{k}=y\mid\bar{\mathcal{F}}^{n,k})=\bar{\mu}^{n,k}(e_{y}),\;\;y\in\Delta^{o},$

define $\bar{\nu}^{n,k},\bar{L}^{n,k+1}$ by (6.14), and let
$\mathcal{J}_{1}^{n}(\omega)=\bm{1}_{\\{\tau^{n,0}(\omega)\leq l^{n,0}\\}}$.
Note that, by (6.11), $\\{\tau^{n,0}(\omega)\leq l^{n,0}\\}$ is a ‘low
probability’ event for large $n$ and so once more we are using uncontrolled
(zero cost) dynamics on this event.

  5. (v)

We now recursively extend the construction. Towards this end, suppose that,
for some $l\in\\{0,\dots,l_{0}-1\\}$, we have defined the quantities

$\left\\{\bar{X}^{n}_{k}(\omega),\bar{\nu}^{n,k}(\omega),\bar{L}^{n,k}(\omega),\bar{\mu}^{n,k}(\omega),\;k\in\cup_{i=0}^{l}\left(\\{m^{n}_{i}\\}\cup\mathcal{I}^{n,i}\right)\right\\}$

and $\\{\mathcal{J}_{i}^{n},\;0\leq i\leq l+1\\}$. Let

$\mathcal{E}_{l+1}^{n}\doteq\mathcal{E}_{l}^{n}\cap\\{\mathcal{J}^{n}_{l+1}(\omega)=0\\}=\\{N_{1}(\omega)\leq
r_{1}\\}\cap\left(\cap_{i=0}^{l+1}\\{\mathcal{J}_{i}^{n}(\omega)=0\\}\right).$
(6.18)

Then on the ‘high probability’ set $\mathcal{E}_{l+1}^{n}$ we proceed as
follows.

     * •

For $k=m^{n}_{l+1}$, let

$\bar{\mu}^{n,k}(\omega)(e_{y})\doteq\beta^{l+1}_{(1)}(y),\;\;y\in\Delta^{o},$

define $\bar{X}^{n}_{k}\doteq U^{l+1}_{0}$, and note that, a.e. on
$\mathcal{E}_{l+1}^{n}$,

$P(\bar{X}^{n}_{k}=y\mid\bar{\mathcal{F}}^{n,k})=\beta^{l+1}_{(1)}(y),\;\;y\in\Delta^{o}.$

Also, define $\bar{\nu}^{n,k},\bar{L}^{n,k+1}$ by (6.14).

     * •

We now consider $k\in\mathcal{I}^{n,l+1}$. Let

$\tau^{n,l+1}(\omega)\doteq\inf\left\\{m\geq
k^{*}:\left\|\frac{1}{m+1}\sum_{i=0}^{m}\delta_{U^{l+1}_{i}(\omega)}-\beta^{l+1}_{(1)}\right\|>\varepsilon_{0}\right\\}.$

For
$k\in\\{m^{n}_{l+1}+1,\dots,m^{n}_{l+1}+(l^{n,l+1}\wedge\tau^{n,l+1}(\omega))\\}$,
let $\bar{X}^{n}_{k}=U^{l+1}_{k-m^{n}_{l+1}}$, and note that, a.e. on
$\mathcal{E}_{l+1}^{n}$,

$P(\bar{X}^{n}_{k}=y\mid\bar{\mathcal{F}}^{n,k})=\beta^{l+1}_{2|1}(y\mid\bar{X}^{n}_{k-1}),\;\;y\in\Delta^{o},$

where $\bar{\mathcal{F}}^{n,k}$ is defined as above. Also, for
$k\in\\{m^{n}_{l+1}+1,\dots,m^{n}_{l+1}+(l^{n,l+1}\wedge\tau^{n,l+1}(\omega))\\}$,
define $\bar{\nu}^{n,k},\bar{L}^{n,k+1}$ by (6.14), and

$\bar{\mu}^{n,k}(\omega)(e_{y})\doteq\beta^{l+1}_{2|1}(y\mid\bar{X}^{n}_{k-1}(\omega)),\;\;y\in\Delta^{o}.$

If $\\{\tau^{n,l+1}(\omega)\leq l^{n,l+1}\\}$ occurs, then let, for $k\geq
m^{n}_{l+1}+\tau^{n,l+1}(\omega)+1$, $\bar{\mu}^{n,k}(\omega)$ and
$\bar{X}^{n}_{k}(\omega)$ be defined so that

$\bar{\mu}^{n,k}(\omega)(e_{y})\doteq
G^{\mathcal{V}}(\bar{L}^{n,k}(\omega))(e_{\bar{X}^{n}_{k-1}(\omega)},e_{y}),\;\;y\in\Delta^{o},$

and

$P(\bar{X}^{n}_{k}=y\mid\bar{\mathcal{F}}^{n,k})=\bar{\mu}^{n,k}(e_{y}),\;\;y\in\Delta^{o},$

define $\bar{\nu}^{n,k},\bar{L}^{n,k+1}$ by (6.14), and let
$\mathcal{J}_{l+2}^{n}(\omega)\doteq\bm{1}_{\\{\tau^{n,l+1}(\omega)\leq
l^{n,l+1}\\}}$.

  6. (vi)

On the event $\\{l^{n,l_{0}}<\tau^{n,l_{0}}(\omega)\\}$ and for $k\geq
m^{n}_{l_{0}}+\tau^{n,l_{0}}(\omega)+1$, define $\bar{\mu}^{n,k}(\omega)$ and
$\bar{X}^{n}_{k}(\omega)$ by

$\bar{\mu}^{n,k}(\omega)(e_{y})\doteq
G^{\mathcal{V}}(\bar{L}^{n,k}(\omega))(e_{\bar{X}^{n}_{k-1}(\omega)},e_{y}),\;\;y\in\Delta^{o},$

and

$P(\bar{X}^{n}_{k}=y\mid\bar{\mathcal{F}}^{n,k})=\bar{\mu}^{n,k}(e_{y}),\;\;y\in\Delta^{o},$

and define $\bar{\nu}^{n,k},\bar{L}^{n,k+1}$ by (6.14)

pt$\bar{\mu}^{n,k}\sim G^{\mathcal{V}}(\bar{L}^{n,k})$ $k=1,\dots,r_{1}\wedge
N_{1}(\omega)$pt$\bar{\mu}^{n,k}\sim G^{\mathcal{V}}(\bar{L}^{n,k})$ $k\geq
r_{1}+1$$r_{1}<N_{1}(\omega)$pt$\bar{\mu}^{n,k}\sim Q^{\mathcal{V}}$
$k=N_{1}(\omega)+1,\dots,k_{3}(\omega)$pt$\bar{\mu}^{n,k}\sim
G^{\mathcal{V}}(\bar{L}^{n,k})$ $k\geq
k_{3}(\omega)+1$$\mathcal{J}_{0}^{n}=1$pt$\bar{\mu}^{n,k}\sim\beta^{0}$
$k=m^{n}_{0},\dots,m^{n}_{0}+l^{n,0}\wedge\tau^{n,0}$pt$\bar{\mu}^{n,k}\sim
G^{\mathcal{V}}(\bar{L}^{n,k})$ $k\geq
m^{n}_{0}+\tau^{n,0}(\omega)+1$$\mathcal{J}_{1}^{n}=1$…pt$\bar{\mu}^{n,k}\sim
G^{\mathcal{V}}(\bar{L}^{n,k})$ $k\geq
m^{n}_{l_{0}-1}+\tau^{n,l_{0}-1}(\omega)+1$$\mathcal{J}_{l_{0}}^{n}=1$pt$\bar{\mu}^{n,k}\sim\beta^{l+1}$
$k=m^{n}_{l_{0}},\dots,m^{n}_{l_{0}}+l^{n,l_{0}}\wedge\tau^{n,l_{0}}$pt$\bar{\mu}^{n,k}\sim
G^{\mathcal{V}}(\bar{L}^{n,k})$ $k\geq
m^{n}_{l_{0}}+\tau^{n,l_{0}}+1$$\mathcal{J}^{n}_{l_{0}+1}=1$pt$\bar{\mu}^{n,k}\sim
G^{\mathcal{V}}(\bar{L}^{n,k})$ $k\geq
m^{n}_{l_{0}}+l^{n,l_{0}}+1$$\mathcal{J}^{n}_{l_{0}+1}=0$$\mathcal{J}_{l_{0}}^{n}=0$$\mathcal{J}_{1}^{n}=0$$\mathcal{J}_{0}^{n}=0$$r_{1}\geq
N_{1}(\omega)$ Figure 6.1: An algorithmic representation of Construction 6.1
of the controls. From the root of the tree to the bottom: red edges (resp.
blue, green) correspond to ‘low probability’ (resp. ‘high probability’) events
and lead to uncontrolled dynamics based on $G$ (resp. the controls based on
the kernel $Q$, the kernel $\beta_{2|1}$).

###  6.2 Convergence of Controlled Processes

Let, for $n\in\mathbb{N}$,
$\\{\bar{L}^{n,k+1},\bar{\mu}^{n,k+1},\bar{\nu}^{n,k},\;k\in\mathbb{N}_{0}\\}$
be defined as in Construction 6.1. Using these, for $n\in\mathbb{N}$ and
$t\in[0,T]$, define $\bar{L}^{n}(t)$ as in (3.6),
$\\{\bar{\Lambda}^{n},\bar{\xi}^{n},\bar{\zeta}^{n}\\}$ as in (3.8) – (3.10),
(3.13), and $\\{\gamma^{n},\beta^{n},\theta^{n}\\}$ as in (3.18). Also, define
$\check{\mathbf{L}}^{n}$ and $\check{\Lambda}^{n}$ as in (3.22) and (3.23),
and for $t\in[0,T]$, define $\sigma_{n,t}\doteq t_{n}-T+t$,

$\hat{M}^{n}(t)\doteq\bar{L}^{n}(\sigma_{n,t})=\bar{L}^{n}(t_{n}-T+t).$ (6.19)

For notational convenience, write
$\mathcal{E}^{n}\doteq\mathcal{E}^{n}_{l_{0}+1}$, where
$\mathcal{E}^{n}_{l_{0}+1}$ is defined as in (6.18). Also, note that, for each
$n\in\mathbb{N}$,

$B^{n}\doteq\cup_{l=1}^{l_{0}+1}\\{\mathcal{J}_{l}^{n}=1\\}\subseteq\left\\{\max_{j=0,\ldots,l_{0}}\,\sup_{m\geq
k^{*}}\left\|\frac{1}{m+1}\sum_{i=0}^{m}\delta_{U^{j}_{i}}-\beta^{j}_{(1)}\right\|>\varepsilon_{0}\right\\},$
(6.20)

and thus, from (6.11), for all $n\in\mathbb{N}$,

$P(B^{n})\leq\varepsilon_{1}.$ (6.21)

The following lemma gives an estimate on the distance between $\hat{M}^{n}(0)$
and $q$.

######  Lemma 6.2.

For all $n\geq n_{0}$,

$P(\|\hat{M}^{n}(0)-q\|\geq 3\varepsilon_{0})\leq 3\varepsilon_{1}.$

###### Proof.

Fix $n\geq n_{0}$ and note that

$\hat{M}^{n}(0)=\bar{L}^{n}(t_{n}-T)=\bar{L}^{n}(a(t_{n}-T))+\mathcal{R}^{n},$

where, from (4.24) and our choice of $n_{0}$ above (6.13),

$\|\mathcal{R}^{n}\|=\|\bar{L}^{n}(t_{n}-T)-\bar{L}^{n}(a(t_{n}-T))\|\leq
2(m(t_{n}-T)+2)^{-1}=2(m^{n}_{0}+2)^{-1}\leq\varepsilon_{0}.$

Thus, on recalling the definition of $\\{a(s),\;s\in\mathbb{R}_{+}\\}$ from
(3.12), we have

$P(\|\hat{M}^{n}(0)-q\|>3\varepsilon_{0})\leq
P(\|\bar{L}^{n}(a(t_{n}-T))-q\|>2\varepsilon_{0})=P(\|\bar{L}^{n,m^{n}_{0}}-q\|>2\varepsilon_{0}).$
(6.22)

Also,

$\displaystyle P(\|\bar{L}^{n,m^{n}_{0}}-q\|>2\varepsilon_{0})$
$\displaystyle\leq
P\left((\mathcal{E}^{n})^{c}\right)+P(\mathcal{E}^{n},\|\bar{L}^{n,m^{n}_{0}}-q\|>2\varepsilon_{0}),$
(6.23)

and

$\\{\omega:\mathcal{J}_{0}^{n}(\omega)=1\\}\subseteq\left\\{\omega:\sup\limits_{k_{2}(\omega)\leq
k\leq m_{n}^{0}-1}\|\bar{L}^{n,k+1}(\omega)-q\|>2\varepsilon_{0}\right\\}$
(6.24)

Also, for all $k\geq k_{2}(\omega)$, we have

$\bar{L}^{n,{k}+1}(\omega)=\frac{N_{1}(\omega)+1}{{k}+1}\bar{L}^{n,N_{1}(\omega)+1}(\omega)+\frac{{k}-N_{1}(\omega)}{{k}+1}\frac{1}{{k}-N_{1}(\omega)}\sum_{j=N_{1}(\omega)+1}^{{k}}\delta_{\bar{X}^{n}_{j}(\omega)}.$

From this, using the fact that, on $\\{N_{1}\leq r_{1}\\}$, from the
definitions of $k_{1}$ and $k_{2}(\omega)$,

$\frac{2(N_{1}(\omega)+1)}{k+1}\leq\frac{2(r_{1}+1)}{N_{1}+k_{0}+\lfloor
4(r_{1}+1)/\varepsilon_{0}\rfloor+1}\leq\frac{\varepsilon_{0}}{2},\mbox{ for
all }k\geq k_{2}(\omega),$

we have, on $\mathcal{D}^{n}_{0}$ (recall the definition of
$\mathcal{D}^{n}_{0}$ from (6.16)) that, for all
$k\in\\{k_{2}(\omega),k_{2}(\omega)+1,\ldots,k_{3}(\omega)\\}$,

$\begin{split}\|\bar{L}^{n,k+1}(\omega)-q\|&\leq\frac{\varepsilon_{0}}{2}+\frac{k-N_{1}(\omega)}{k+1}\left\|\frac{1}{k-N_{1}(\omega)}\sum_{j=N_{1}(\omega)+1}^{k}\delta_{\bar{X}^{n}_{j}(\omega)}-q\right\|\\\
&\leq\frac{\varepsilon_{0}}{2}+\max\limits_{y\in\Delta^{o}}\left\|\frac{1}{k-N_{1}(\omega)}\sum_{j=N_{1}(\omega)+1}^{k}\delta_{\bar{Y}^{y}_{j-N_{1}(\omega)}(\omega)}-q\right\|\\\
&\leq\frac{\varepsilon_{0}}{2}+\max\limits_{y\in\Delta^{o}}\left\|\frac{1}{k-N_{1}(\omega)+1}\sum\limits_{j=0}^{k-N_{1}(\omega)}\delta_{\bar{Y}^{y}_{j}(\omega)}-q\right\|+\frac{2}{k-N_{1}(\omega)+1}\\\
&\leq\varepsilon_{0}+\max\limits_{y\in\Delta^{o}}\left\|\frac{1}{k-N_{1}(\omega)+1}\sum\limits_{j=0}^{k-N_{1}(\omega)}\delta_{\bar{Y}^{y}_{j}(\omega)}-q\right\|,\end{split}$
(6.25)

where the last inequality follows on recalling (6.6) and noting that
$k_{2}(\omega)-N_{1}(\omega)>k_{0}$ on $\\{N_{1}\leq r_{1}\\}$. Once more
using the fact that $k_{2}(\omega)-N_{1}(\omega)>k_{0}$ on $\\{N_{1}\leq
r_{1}\\}$, we have, due to (6.6), (6.24), and (6.25), that

$\displaystyle\mathbb{P}(\mathcal{D}^{n}_{0})$ $\displaystyle\leq
P\left(\left\\{\omega:N_{1}(\omega)\leq r_{1},\sup\limits_{k_{2}(\omega)\leq
k\leq
m_{n}^{0}-1}\|\bar{L}^{n,k+1}(\omega)-q\|>2\varepsilon_{0}\right\\}\right)$
(6.26) $\displaystyle\leq P\left(\left\\{\omega:N_{1}(\omega)\leq
r_{1},\,\max_{y\in\Delta^{o}}\sup_{k\geq
k_{2}(\omega)}\left\|\frac{1}{k-N_{1}(\omega)+1}\sum\limits_{j=0}^{k-N_{1}(\omega)}\delta_{\bar{Y}^{y}_{j}(\omega)}-q\right\|>\varepsilon_{0}\right\\}\right)$
$\displaystyle\leq P(A_{\varepsilon_{0}})\leq\varepsilon_{1},$ (6.27)

where the next to last inequality uses
$k_{2}(\omega)-N_{1}(\omega)=k_{1}>k_{0}$. This, together with (6.4) and
(6.21), shows that

$P\left((\mathcal{E}^{n})^{c}\right)\leq
P(N_{1}>r_{1})+P(\mathcal{D}^{n}_{0})+P\left(\cup_{i=1}^{l_{0}+1}\\{\mathcal{J}_{i}^{n}=1\\}\right)\leq\varepsilon_{1}+\varepsilon_{1}+\varepsilon_{1}=3\varepsilon_{1}.$

Also, on $\mathcal{E}^{n}$, we have $\tau^{n}\geq m^{n}_{0}-1$, and therefore

$\displaystyle
P(\mathcal{E}^{n},\,\|\bar{L}^{n,m^{n}_{0}}-q\|>2\varepsilon_{0})$
$\displaystyle=0.$

The result follows on using the above estimate together with (6.22), (6.23),
and (6.26). ∎

For $n\in\mathbb{N}$ and $t\in[0,c]$, let

$p_{0}^{n}\doteq m(t_{n}-T+\varepsilon_{0})-m^{n}_{0},\;\;p_{0}^{n}(t)\doteq
m(t_{n}-T+t)-m^{n}_{0},$ (6.28)

and note that $p^{n}_{0}(\varepsilon_{0})=p^{n}_{0}$. Recall the definitions
of $k^{*}$ and $n_{0}$ from above (6.11) and (6.13), respectively, and let
$n_{1}\geq n_{0}$ be such that, for each $n\geq n_{1}$ and all
$i=0,\dots,l_{0}$,

$p_{0}^{n}>k^{*},\;\;\frac{2\max\\{k^{*},2c,1\\}}{m^{n}_{0}}\leq\frac{\varepsilon_{0}}{2},\;\;\left\|\frac{m(t_{n}-T+(i+1)c)+1}{m(t_{n}-T+ic+\varepsilon_{0})}-e^{c-\varepsilon_{0}}\right\|<\varepsilon_{0}.$
(6.29)

Note that the last estimate in the previous display is possible due to Lemma
4.2 and that it implies that

$\frac{m(t_{n}-T+(i+1)c)+1}{m(t_{n}-T+ic+\varepsilon_{0})}\leq
e^{c-\varepsilon_{0}}+\varepsilon_{0}\leq 2+c,\;\;i=0,\dots,l_{0},$ (6.30)

since $c-\varepsilon_{0}\in(0,1)$. Also, note that the first inequality in
(6.29) implies that

$p_{i}^{n}=m(t_{n}-T+ic+\varepsilon_{0})-m_{i}^{n}\geq
k^{*},\;\;i=0,\dots,l_{0},$

which is used in Lemma 6.4. Further, recall from (6.1) that $d_{1}\doteq
e^{c}(12+c)$ and $d_{2}=6$.

The following lemma shows that the controlled state process has the correct
asymptotic behavior over the time interval $[0,c]$.

######  Lemma 6.3.

For $n\geq n_{1}$,

$P\left(\sup_{t\in[0,c]}\|\hat{M}^{n}(t)-\hat{M}(t)\|\geq
d_{1}\varepsilon_{0}\right)\leq d_{2}\varepsilon_{1}.$

###### Proof.

Fix $n\geq n_{1}$. Using (3.14) and (6.19), note that for each $t\in[0,c]$,

$\displaystyle\hat{M}^{n}(t)$
$\displaystyle=\hat{M}^{n}(0)+\int_{t_{n}-T}^{t_{n}-T+t}\sum\limits_{v\in\mathcal{V}^{d}}(v-\bar{L}^{n}(a(s)))\bar{\Lambda}^{n}(v\mid
s)ds$
$\displaystyle=q+t\beta^{0}_{(1)}-\int_{0}^{t}\hat{M}^{n}(s)ds+\bar{\mathcal{R}}^{n}_{1}(t)+\bar{\mathcal{R}}^{n}_{2}(t)+\bar{\mathcal{R}}_{3}^{n},$
(6.31)

where

$\bar{\mathcal{R}}^{n}_{1}\doteq\hat{M}^{n}(0)-q,\;\;\bar{\mathcal{R}}^{n}_{2}(t)\doteq-\int_{t_{n}-T}^{t_{n}-T+t}\left(\bar{L}^{n}(a(s))-\bar{L}^{n}(s)\right)ds,$

and

$\bar{\mathcal{R}}^{n}_{3}(t)\doteq\int_{t_{n}-T}^{t_{n}-T+t}\left(\sum\limits_{v\in\mathcal{V}^{d}}v\bar{\Lambda}(v\mid
s)-\beta^{0}_{(1)}\right)ds.$

We begin by considering $\bar{\mathcal{R}}^{n}_{1}$ and
$\bar{\mathcal{R}}^{n}_{2}$. From Lemma 6.2 we see that