Large Deviations for a Random Walk Model with

State-dependent Noise

Michelle Boué ITAM Daniel Hernández-Hernández CIMAT Richard S. Ellis UMass, Amherst

November 27, 2000

Abstract In this paper we prove the Laplace principle for a class of random walks with state-dependent noise. The Laplace principle implies a large deviations principle with the same rate function. This type of model has important applications in queueing and communication theory, and in the area of stochastic approximation.

1 Introduction

This paper is concerned with proving a large deviations principle for a certain class of random walks, where the evolution of the noise process depends on the state of the random walk. This type of model has important applications in queueing and communication theory, and in the area of stochastic approximation. In fact, our main motivation for the study of these models is their application to the state-dependent stochastic approximation algorithms presented in [9].

Let S be a compact Polish space and let p(dζ|x, ξ) be a stochastic kernel on S given IR^{d} × S. For each n ∈ IN, we consider a sequence of random variables {(X_{j}^{n}, Z_{j}^{n}), j = 0, …, n} defined on a probability space (Ω, F, P) and taking values in IR^{d} × S. For x ∈ IR^{d}, ξ ∈ S and b a function mapping IR^{d} × S into IR^{d}, this sequence is defined through

X_{0}^{n} ≐ x
Z_{0}^{n} ≐ ξ
X_{j+1}^{n} ≐ X_{j}^{n} + \frac{1}{n}b(X_{j}^{n}, Z_{j+1}^{n}),

where for j ∈ {0, 1, …, n − 1} the conditional distribution of Z_{j+1}^{n} given the past is given by

P_{x,ξ} {Z_{j+1}^{n} ∈ dζ|(X_{i}^{n}, Z_{i}^{n}), i = 0, …, j} = p(dζ|X_{j}^{n}, Z_{j}^{n}).  (1.1)

Here P_{x,ξ} denotes probability conditioned on X_{0}^{n} = x, Z_{0}^{n} = ξ. We assume that the stochastic kernel p and the function b satisfy the following hypothesis. Hypothesis H.1.

a) b(x, ξ) is bounded, continuous in ξ and Lipschitz continuous with constant K in x, uniformly in ξ.

b) p(dζ|x, ξ) is weakly continuous in (x, ξ).

c) Given any compact set Δ ⊂ IR^{d}, there exist a probability measure ϑ on S, a function p̃^{x}(ξ, ζ) on S × S, and constants 0 < a ≤ A < ∞ such that

p(dζ|x, ξ) = p̃^{x}(ξ, ζ)ϑ(dζ) and a ≤ p̃^{x}(ξ, ζ) ≤ A

for all x ∈ Δ. Moreover, p̃^{x}(ξ, ζ) is continuous in x uniformly in ξ and ζ, for x ∈ Δ.

Under this hypothesis, the following statements are proved in [10]. Consider the eigenvalue problem:

e^{Λ(α)+Ψ(ξ)} = ∫_{S} e^{⟨α,b(x,ζ)⟩+Ψ(ζ)}p(dζ|x, ξ).  (1.2)

Under Hypothesis H.1 the solution to this problem exists. Moreover, the solution is bounded with Λ smooth. In fact, we can identify Λ(α) in a very explicit manner. Given x ∈ IR^{d} and ξ ∈ S, set ξ_{0}^{x} = ξ and let {ξ_{j}^{x}, j ≥ 0} be a Markov process with transition kernel p(·|x, ξ_{j}^{x}). Then the function Λ(x, α) satisfies

Λ(x, α) = lim_{N→∞} \frac{1}{N} log E_{ξ} \{exp⟨α, ∑_{j=1}^{N} b(x, ξ_{j}^{x})⟩\} ,  (1.3)

where E_{ξ} denotes expectation conditioned on ξ_{0}^{x} = ξ. We refer to the process {ξ_{j}^{x}, j ≥ 0} as the ”fixed x” process. As can be seen, it is the Markov chain that results if the parameter X_{j}^{n} in (1.1) is held constant at value x. This process is intimately connected with the process {X_{j}^{n}}: if n is large, then X_{j}^{n} varies slowly and thus the ”local” evolution of b(X_{j}^{n}, Z_{j+1}^{n}) is very similar to the evolution of the same quantity but taking X_{j}^{n} as constant (see [9]).

Let X^{n} = {X^{n}(t), 0 ≤ t ≤ 1} be the piecewise linear interpolation on [0, 1] of {X_{j}^{n}, j = 0, …, n}. More precisely, for t ∈ [j/n, (j + 1)/n] and j = 0, …, n − 1

X^{n}(t) ≐ X_{j}^{n} + (t − \frac{j}{n}) b(X_{j}^{n}, Z_{j+1}^{n}).  (1.4)

The main result of the paper, Theorem 2.2, states the Laplace principle for the process {X^{n}, n ∈ IN}. The term Laplace principle refers to the asymptotic analysis of normalized logarithms of expectations involving continuous functions (a precise definition is given in the next section). Because a Laplace principle is equivalent to a large deviations principle with the same rate function, the large deviation principle that we are interested in is an immediate consequence of Theorem 2.2.

We note that the large deviations principle implied by Theorem 2.2 is covered by the results in [3]. The proof there relies on technical assumptions for the function Λ, which is assumed to exist. Under Hypothesis H.1, the function Λ exists indeed, and satisfies the technical assumptions required there, thereby implying the large deviations principle. Instead, an advantage of the proof presented here is that it depends on assumptions made on the evolution of the process itself (the transition kernels and the function b). The advantage is in several senses. First, for the purposes of using the results in applications, assumptions must be made on the processes, since these are the type of assumptions that can be used there. Moreover, knowledge about the process provides a lot of intuition concerning the averaging procedure required for the proof. This intuition has been heavily exploited by some of the proofs of convergence of state-dependent stochastic algorithms (see [9, 8]), and we have incorporated some of their underlying ideas into the proof. Finally, seeing where each one of the properties of the process is needed in the proof has enabled us to understand the ergodicity properties required to extend our results to more general state-dependent processes. Extensions will be dealt with elsewhere.

2 The main theorem

Before stating our main theorem, we need to introduce the concept of a Laplace principle. By definition, a rate function on a Polish space maps the Polish space into [0, ∞] and has compact level sets.

Definition 2.1 Let {X^{n}, n ∈ IN} be a sequence of random variables taking values in a Polish space X and let I be a rate funcion on X. We say that {X^{n}, n ∈ IN} satisfies a Laplace principle with rate function I if for every bounded continuous function h mapping X into IR

lim_{n→∞} \frac{1}{n} log E \{exp[−nh(X^{n})]\} = − inf_{x∈X} \{h(x) + I(x)\} .

A Laplace principle is equivalent to a large deviations principle with the same rate function (see Theorems 2.2.1 and 2.2.3 in [4] for a proof). For our model of interest, we will prove the former in the theorem that follows, obtaining the latter as a direct consequence of it.

Theorem 2.2 For n ∈ IN, let X^{n} be the piecewise linear interpolation of {X_{j}^{n}, j = 0, 1, …, n} as defined in (1.4). Under Hypothesis H.1 the sequence {X^{n}, n ∈ IN} satisfies the Laplace principle with rate function I_{x,ξ}(·), where

I_{x,ξ}(ϕ) ≐ \{ \begin{matrix}∫_{0}^{1} L(ϕ, ϕ̇)dt & if ϕ is absolutely continuous and ϕ(0) = x, \\ ∞ & otherwise, \end{matrix}

and L(x, ·) is the Legendre-Fenchel transform of the function Λ(x, ·) given in (1.3) with respect to the second variable. That is, for x and β in IR^{d}

L(x, β) ≐ sup_{α∈IR^{d}}{⟨α, β⟩ − Λ(x, α)}.  (2.5)

Let W^{n}(x, ξ) ≐ −1/n log E_{x,ξ} {exp[−nh(X^{n})]}. The proof of Theorem 2.2 is done in two parts. We start by proving the Laplace principle upper bound, equivalent to

lim inf_{n→∞} W^{n}(x, ξ) ≥ inf_{ϕ∈C([0,1]:IR^{d})} {I_{x,ξ}(ϕ) + h(ϕ)} .  (2.6)

This is the content of Section 3. The lower bound

lim sup_{n→∞} W^{n}(x, ξ) ≤ inf_{ϕ∈C([0,1]:IR^{d})} {I_{x,ξ}(ϕ) + h(ϕ)} .  (2.7)

is then proved in Section 4. In both cases, a key step in the proof involves the study (via weak convergence methods) of the limit properties of a sequence of associated stochastic control problems. For ease of presentation, the representation formulas required to associate W^{n}(x, ξ) with an appropriate stochastic control problem are presented in the Appendix (Theorem .1 is used for the upper bound and Theorem .2 for the lower bound).

3 Proof of the Laplace principle upper bound

This section is devoted to the proof of (2.6). As was mentioned earlier, we shall use the representation formula found in Theorem .1 in the Appendix, so that for every n ∈ IN

W^{n}(x, ξ) = inf_{\{ν_{j}^{n}\}} Ē_{x,ξ} \{\frac{1}{n} ∑_{j=0}^{n−1} R(ν_{j}^{n}(·)∥p(·|X̄_{j}^{n}, Z̄_{j}^{n})) + h(X̄^{n})\} .

The infimum is taken over all admissible control sequences {ν_{j}^{n}, j = 0, …, n − 1}, with ν_{j}^{n}(·) = ν_{j}^{n}(·|X̄_{0}^{n}, …, X̄_{j}^{n}, Z̄_{j}^{n}). The reader is referred to the Appendix for the definition of all the quantities involved in the representation.

Given ε > 0, for each n ∈ IN let {ν_{j}^{n}, j = 0, …, n − 1} be a sequence of early optimal admissible controls, so that

W^{n}(x, ξ) ≥ Ē_{x,ξ} \{\frac{1}{n} ∑_{j=0}^{n−1} R(ν_{j}^{n}(·)∥p(·|X̄_{j}^{n}, Z̄_{j}^{n})) + h(X̄^{n})\} − ε.  (3.8)

Here {X̄_{j}^{n}, j = 0, …, n} is the controlled process associated with this sequence of controls, and {X̄^{n}, n ∈ IN} is the sequence of piecewise linear interpolations of {X̄_{j}^{n}, j = 0, …, n}. The proof of (2.6) requires that we analyze the asymptotic behavior of {X̄^{n}, n ∈ IN} and of a sequence of control measures {ν^{n}, n ∈ IN} which we now construct using the sequences {ν_{j}^{n}, j = 0, …, n, n ∈ IN}.

Let {m_{n}, n ∈ IN} be a sequence of real numbers satisfying m_{n} → ∞ as n → ∞, and such that if k_{n} ≐ m_{n}/n then lim_{n→∞} k_{n} = 0. Also, suppose that 1 is an integral multiple of k_{n}. The basic idea will be to collect terms of the sum appearing in (3.8) in groups of size m_{n} for the purposes of averaging. The control measures that we now define will be the result of this grouping.

For ξ ∈ S, let δ_{ξ} denote the unit point measure at ξ. For l = 0, …, 1/k_{n} − 1, and Borel subsets B_{1} and B_{2} of S, let

ν_{l}^{n}(B_{1} × B_{2}) ≐ \frac{1}{m_{n}} ∑_{j=lm_{n}}^{(l+1)m_{n}−1} δZ̄_{j}^{n}(B_{1}) × ν_{j}^{n}(B_{2}|X̄_{j}^{n}, Z̄_{j}^{n}).

The quantity ν_{l}^{n} is a stochastic kernel^{1} on S × S with marginals

(ν_{l}^{n})_{1}(B_{1}) = \frac{1}{m_{n}} ∑_{j=lm_{n}}^{(l+1)m_{n}−1} δZ̄_{j}^{n}(B_{1}) and (ν_{l}^{n})_{2}(B_{2}) = \frac{1}{m_{n}} ∑_{j=lm_{n}}^{(l+1)m_{n}−1} ν_{j}^{n}(B_{2}|X̄_{j}^{n}, Z̄_{j}^{n}).

1For ease of presentation, the dependence on the underlying probability space of all stochastic kernels appearing in this paper is not made explicit in the notation

For each n ∈ IN and t ∈ [0, 1] define

ν^{n}(B_{1} × B_{2}|t) ≐ \{ \begin{matrix}ν_{l}^{n}(B_{1} × B_{2}) & if t ∈ [lk_{n}, (l + 1)k_{n}) for l = 0, …, 1/k_{n} − 2, \\ ν_{(1− \frac{1}{kn})}^{n}(B_{1} × B_{2}) & if t ∈ [1 − 1/k_{n}, 1]. \end{matrix}

Finally we define the admissible control measure ν^{n} to be the random probability measure defined for Borel subsets B_{1}, B_{2} of S and C of [0, 1] through

ν^{n}(B_{1} × B_{2} × C) ≐ ∫_{C} ν^{n}(B_{1} × B_{2}|t)dt.

Theorem A.5.6 in [4] provides us with a convenient decomposition for the measures ν^{n}(dζ × dy × dt) in terms of the first marginal of ν^{n}(dζ × dy|t). More precisely, if for B_{1} ∈ B(S) we define the first marginal ν̂_{1}^{n}(dζ|t) of ν^{n}(dζ × dy|t) through

ν̂_{1}^{n}(B_{1}|t) ≐ ν^{n}(B_{1} × S|t),

then for Borel subsets B_{1}, B_{2} of S and C of [0, 1] we can write

ν^{n}(B_{1} × B_{2} × C) = ∫_{C} ν^{n}(B_{1} × B_{2}|t)dt
= ∫_{C} ∫_{B_{1}×B_{2}} ν̂_{1}(dζ|t)ν̂_{2}^{n}(dy|ζ, t)dt
= ∫_{C} ∫_{B_{1}} ν̂_{2}^{n}(B_{2}|ζ, t)ν̂_{1}^{n}(dζ|t)dt,  (3.9)

where ν̂_{2}^{n}(dy|ζ, t) is a stochastic kernel on S given S × [0, 1]. Following the notation in [4], we summarize this decomposition as ν^{n}(dζ × dy × dt) = ν̂_{1}^{n}(dζ|t) ⊗ ν̂_{2}^{n}(dy|ζ, t) ⊗ dt. The marginals of ν^{n}(dζ × dy × dt) can also be represented in terms of the kernels ν̂_{1}^{n}(dζ|t) and ν̂_{2}^{n}(dy|ζ, t) and of Lebesgue measure λ on IR. Namely, for Borel sets B_{1} and B_{2} of S and C of [0, 1] the marginal over (ζ, t) can be written as

ν^{n}(B_{1} × S × C) = ∫_{C} ν̂_{1}^{n}(B_{1}|t)dt
≐ (ν̂_{1}^{n} ⊗ λ)(B_{1} × C)

and the marginal over (y, t) as

ν^{n}(S × B_{2} × C) = ∫_{C} ∫_{S} ν̂_{2}^{n}(B_{2}|ζ, t)ν̂_{1}^{n}(dζ|t)dt
≐ (ν̂_{2}^{n} ⊗ λ)(B_{2} × C).

We note that the marginal over t is simply Lebesgue measure λ.

The next step is to manipulate the sum appearing in (3.8) in order to rewrite the right hand side of this inequality in terms of the measures ν^{n}. We first use the fact that R(β∥γ) = R(α × β∥α × γ) for any probability measures α, β and γ on S. This formula applied term by term enables us to write

Ē_{x,ξ} \{\frac{1}{n} ∑_{j=0}^{n−1} R(ν_{j}^{n}(·)∥p(·|X̄_{j}^{n}, Z̄_{j}^{n}))\}

= Ē_{x,ξ} \{ ∑_{l=0}^{\frac{1}{kn} −1} k_{n} \frac{1}{m_{n}} ∑_{j=lm_{n}}^{(l+1)m_{n}−1} R (ν_{j}^{n}(·) ∥ p(·|X̄_{j}^{n}, Z̄_{j}^{n}))\}

= Ē_{x,ξ} \{ ∑_{l=0}^{\frac{1}{kn} −1} k_{n} \frac{1}{m_{n}} ∑_{j=lm_{n}}^{(l+1)m_{n}−1} R (δZ̄_{j}^{n}(·) × ν_{j}^{n}(·) ∥ δZ̄_{j}^{n}(dζ) ⊗ p(·|X̄_{j}^{n}, ζ))\} ,

where we have used the notation δZ̄_{j}^{n}(·) × p(·|X̄_{j}^{n}, Z̄_{j}^{n}) = δZ̄_{j}^{n}(dζ) ⊗ p(·|X̄_{j}^{n}, ζ). Applying Jensen’s inequality to the convex function R(·∥·), the above is no less than

Ē_{x,ξ} \{ ∑_{l=0}^{\frac{1}{kn} −1} k_{n}R(\frac{1}{m_{n}} ∑_{j=lm_{n}}^{(l+1)m_{n}−1}δZ̄_{j}^{n}(dζ) × ν_{j}^{n}(·|X̄_{j}^{n}, ζ)∥\frac{1}{m_{n}} ∑_{j=lm_{n}}^{(l+1)m_{n}−1}δZ̄_{j}^{n}(dζ) ⊗ p(·|X̄_{j}^{n}, ζ))\} ,

which is clearly equivalent to

Ē_{x,ξ} {∫_{0}^{1} R(ν^{n}(·|t)∥γ^{n}(·|t))dt} ,  (3.10)

where, for each n ∈ IN and t ∈ [0, 1], we define

γ^{n}(B_{1} × B_{2}|t) ≐ \frac{1}{m_{n}} ∑_{j=lm_{n}}^{(l+1)m_{n}−1}δZ̄_{j}^{n}(B_{1}) ⊗ p(B_{2}|X̄_{j}^{n}, ζ) if t ∈ [lk_{n}, (l + 1)k_{n}),

for l = 0, …, 1/k_{n} − 1. Define analogously the measure γ^{n} on S × S × [0, 1] as:

γ^{n}(B_{1} × B_{2} × C) ≐ ∫_{C} γ^{n}(B_{1} × B_{2}|t)dt.

Finally we apply the equality

∫_{X} R(α(·|x)∥β(·|x))γ(dx) = R(α ⊗ γ∥β ⊗ γ),  (3.11)

valid for all stochastic kernels α and β on S given X and probability measures γ on X (see [4, Lemma 1.4.3 (f)]). In the present context, this equality implies that (3.10) can be rewritten as

Ē_{x,ξ} {R(ν^{n}∥γ^{n})} .

Combining this series of inequalities with (3.8) we get

W^{n}(x, ξ) + ε ≥ Ē_{x,ξ} {R(ν^{n}∥γ^{n}) + h(X̄^{n})} .

We now wish take the limit inferior as n → ∞ of both terms in the last inequality. The asymptotic properties of the sequence {(ν^{n}, γ^{n}, X̄^{n}), n ∈ IN} required to do this are proved in Theorem .7 in the Appendix. Accordingly, there exists a probability space where a subsequence of {(ν^{n}, γ^{n}, X̄^{n}), n ∈ IN} converges in distribution to some limit (ν, γ, X̄). The stochastic kernels ν and γ and the random variable X̄ (taking values in the continuous functions on [0,1]) satisfy all the conclusions stated in Lemma .7. Thanks to the Skorohod Representation Theorem [4, Theorem A.3.9], we can assume without loss of generality that convergence takes place with probability one. Along the convergent subsequence, lower semicontinuity of R(·∥·) and Fatou’s Lemma, plus continuity of h yield

lim inf_{n→∞} W^{n}(x, ξ) + ε ≥ Ē_{x,ξ} {R(ν∥γ) + h(X̄)} .

The limit characterizations of ν, γ and X̄ enable us to continue

lim inf_{n→∞} W^{n}(x, ξ) + ε

≥ Ē_{x,ξ} {R(ν∥γ) + h(X̄)}

= Ē_{x,ξ} {R(ν̂_{1}(dζ|t) ⊗ ν̂_{2}(dy|ζ, t) ⊗ dt∥ν̂_{1}(dζ|t) ⊗ p(dy|X̄(t), ζ) ⊗ dt) + h(X̄)}
= Ē_{x,ξ} {∫_{0}^{1} R(ν̂_{1}(dζ|t) ⊗ ν̂_{2}(dy|ζ, t)∥ν̂_{1}(dζ|t) ⊗ p(dy|X̄(t), ζ)dt + h(X̄)}
= Ē_{x,ξ} {∫_{0}^{1} ∫_{S} R(ν̂_{2}(dy|ζ, t)∥p(dy|X̄(t), ζ))ν̂_{1}(dζ|t)dt + h(X̄)}
≥ Ē_{x,ξ} {∫_{0}^{1} L(X̄(t), ∫_{S} b(X̄(t), ζ)ν̂_{1}(dζ|t))dt + h(X̄)}

= Ē_{x,ξ} {∫_{0}^{1} L(X̄(t), ˙ X̄(t))dt + h(X̄)} = Ē_{x,ξ} {I_{x,ξ}(X̄) + h(X̄)}

≥ inf_{ϕ∈C([0,1]:IR^{d})} {I_{x,ξ}(ϕ) + h(ϕ)} .

The third line uses part b) of Lemma .7; the fourth and fifth lines both use (3.11); the sixth line uses part h) of Theorem .4 and line seven follows from part e) of Lemma .7. Since the above inequality is valid for all ε > 0, (2.6) follows, concluding the proof of the upper bound.

4 Proof of the Laplace principle lower bound

This section is devoted to showing that (2.7) holds for all h : C([0, 1] : IR^{d}) ↦ IR^{d}. ¿From part (b) of Corollary 1.2.5 in [4], it suffices to show that (2.7) holds for functions h in C([0, 1]; IR^{d}) that are Lipschitz continuous. Therefore, throughout this section we work under the assumption that h is Lipschitz continuous.

Following the proof of Proposition 6.6.1 in [4], the proof of (2.7) is done by introducing a perturbation to the original random walk by means of a random walk with Gaussian noise. This allows one to obtain necessary smoothness properties for the function L_{σ}, which is the analogue of the function L defined in (2.5) but for the perturbed process. Weak convergence arguments make use of these continuity properties, entailing the Laplace principle lower bound when taking the perturbation to be sufficiently small.

Given σ > 0, let {G_{j,σ}, j ∈ IN_{0}} be a sequence of i.i.d. random variables on IR^{d} with common Gaussian distribution ρ_{σ}, with mean zero and variance σI. We assume them to be independent of {ξ_{j}^{x}, x ∈ IR^{d}, j ∈ IN_{0}}, where ξ_{j}^{x} is the ”fixed x” Markov process with transition kernel p(·|x, ξ_{j}^{x}). Given n ∈ IN and j ∈ {0, 1, …, n − 1}, let X_{j}^{n} and Z_{j}^{n} be as before, and define

U_{0,σ}^{n} ≐ 0

U_{j+1,σ}^{n} ≐ U_{j,σ}^{n} + \frac{1}{n}G_{j,σ}.

Denote by X^{n}(t) and U_{σ}^{n}(t) the piecewise linear interpolations of {X_{j}^{n}, j = 1, …, n} and {U_{j,σ}^{n}, j = 0, …, n} on [0, 1], respectively (see 1.4). Also, define

Y_{σ}^{n}(t) ≐ X^{n}(t) + U_{σ}^{n}(t),  (4.12)

which is the piecewise linear interpolation of {X_{j}^{n} + U_{j,σ}^{n}}.

As was mentioned earlier, the point of introducing a perturbation is to replace the function L by a continuous function L_{σ}. This latter function is defined as the Legendre-Fenchel transform of some convex function Λ_{σ}. Once again, the function Λ_{σ} is identified via an eigenvalue problem, which we now describe.

For fixed x ∈ S, we can identify an additive component of the process (see [10, p. 376]), namely, b(x, ξ_{j}^{x}) + G_{j,σ}. Here ξ_{j}^{x} is the ”fixed x” Markov process described earlier. Let Q_{σ}^{x} be the stochastic kernel on S × IR^{d} given ξ ∈ S defined by

Q_{σ}^{x}(B_{1} × B_{2}|ξ) = ∫_{B_{1}} ∫_{IR_{d}} 1_{B_{2}}(b(x, ζ) + y)ρ_{σ}(dy)p(dζ|x, ξ),

where B_{1} ∈ B(S) and B_{2} ∈ B(IR^{d}). Then, letting υ_{σ}(B_{1} × B_{2}|x) ≐ ∫_{B_{1}} ∫_{IR}_{d} 1_{B_{2}}(b(x, ζ) + y)ρ_{σ}(dy)ϑ(dζ), with ϑ as in Hypothesis H.1, B_{1} ∈ B(S) and B_{2} ∈ B(IR^{d}), we have

aυ_{σ}(B_{1} × B_{2}|x) ≤ Q_{σ}^{x}(B_{1} × B_{2}|ξ) ≤ Aυ_{σ}(B_{1} × B_{2}|x).

These bounds on Q_{σ}^{x}(·, ·|ξ) and the fact that the convex hull of the support of υ_{σ}(S×·|x) = IR^{d} guarantee [10, Lemma 3.1] the existence of a solution to the eigenvalue problem for each x, α ∈ IR^{d}. That is, for ach x, α ∈ IR^{d} there exist a unique Λ_{σ}(x, α) ∈ IR and a bounded function Ψ_{σ}(x; α, ·) : S ↦ IR such that

e^{Λ_{σ}(x,α)+Ψ_{σ}(x;α,ξ)} = ∫_{S} ∫_{IR_{d}} e^{⟨α,b(x,ζ)+y⟩+Ψ_{σ}(x;α,ζ)}ρ_{σ}(dy)p(dζ|x, ξ).

Furthermore, Λ_{σ}(x, α) = Λ(x, α) + \frac{σ^{2}}{2} ||α||^{2}, and Ψ_{σ}(x; α, ξ) = Ψ(x; α, ξ), where Ψ(x; α, ξ) is the eigenfunction associated with Λ (see (1.2)). Finally, we define

L_{σ}(x, β) = Λ_{σ}^{∗}(x, α) ≐ sup_{α∈IR^{d}}{⟨α, β⟩ − Λ_{σ}(x, α)}.  (4.13)

Having introduced the necessary definitions, we proceed with the proof of (2.7). The properties of L_{σ} that will be used are proved in Lemma .5 in the Appendix.

Let K_{1} be the Lipschitz constant of h and define B ≐ 2||h||_{∞}. Then

h(Y_{σ}^{n}) = h(X^{n} + U_{σ}^{n}) ≥ h(X^{n}) − (K_{1}||U_{σ}^{n}||_{∞} ∧ B)

and, because of independence,

\frac{1}{n} log E_{x,ξ}\{exp[−nh(Y_{σ}^{n})]\} ≤ \frac{1}{n} log E_{x,ξ}\{exp[−nh(X^{n})] · exp[n(K_{1}||U_{σ}^{n}||_{∞} ∧ B)]\}
= −W^{n}(x, ξ) + \frac{1}{n} log E_{x,ξ}\{exp[n(K_{1}||U_{σ}^{n}||_{∞} ∧ B)]\}.

Hence

lim sup_{n→∞} W^{n}(x, ξ) ≤ lim sup_{n→∞}(−\frac{1}{n} log E_{x,ξ}\{exp[−nh(Y_{σ}^{n})]\}) +

lim sup_{n→∞}(\frac{1}{n} log E_{x,ξ}\{exp[n(K_{1}||U_{σ}^{n}|_{∞} ∧ B)]\})

≤ lim sup_{n→∞}(−\frac{1}{n} log E_{x,ξ}\{exp[−nh(Y_{σ}^{n})]\}) + \frac{K_{1}^{2}σ^{2}}{2} , (4.14)

where the second inequality follows from [4, p.189]. This implies that (2.7) holds as long as we can show that

lim sup W_{σ}^{n}(x, ξ) ≤ inf_{φ∈C([0,1]:IR^{d})}{I_{x,ξ}(φ) + h(φ)} + θ(σ),  (4.15)

with W_{σ}^{n} ≐ −\frac{1}{n} log E_{x,ξ} exp[−nh(Y_{σ}^{n})], and θ(σ) → 0 when σ → 0.

Now, given ε > 0, there exists ψ ∈ C([0, 1] : IR^{d}) such that

I_{x,ξ}(ψ) + h(ψ) ≤ inf_{φ∈C([0,1]:IR^{d})}{I_{x,ξ}(φ) + h(φ)} + ε < ∞.  (4.16)

Then (4.15) will follow once we prove that

lim sup_{n→∞} W_{σ}^{n}(x, ξ) ≤ I_{x,ξ}(ψ) + h(ψ) + θ(σ).  (4.17)

The rest of this section is devoted to proving (4.17).

As was the case in the proof of the upper bound, a key step in the proof of the lower bound is the use of a variational representation. In this case we use a representation for the quantity W_{σ}^{n}(x, ξ) for every n ∈ IN, so that

W_{σ}^{n}(x, ξ) = inf_{\{ν_{j}^{n}\}} \overline{E}_{x,ξ} \{\frac{1}{n} ∑_{j=0}^{n−1} R(ν_{j}^{n}(·)||(p × ρ_{σ})(·|\overline{X}_{j}^{n}, \overline{Z}_{j}^{n})) + h(\overline{Y}^{n})\} .

The admissible controls {ν_{j}^{n}}, and the controlled processes X̄_{j}^{n}, Z̄_{j}^{n} and Ū_{j}^{n} involved in the representation are described in detail in Theorem .2 in the Appendix. In particular, control sequences of the form

ν_{j,prod}^{n}(dζ × dy)|\overline{X}_{0}^{n}, …, \overline{X}_{j}^{n}, \overline{U}_{0}^{n}, …, \overline{U}_{j}^{n}, \overline{Z}_{j}^{n})
= ν_{j}^{1,n}(dζ|\overline{X}_{0}^{n}, …, \overline{X}_{j}^{n}, \overline{U}_{0}^{n}, …, \overline{U}_{j}^{n}, \overline{Z}_{j}^{n}) × ν_{j}^{2,n}(dy|\overline{X}_{0}^{n}, …, \overline{X}_{j}^{n}, \overline{U}_{0}^{n}, …, \overline{U}_{j}^{n}, \overline{Z}_{j}^{n})

are admissible. Since for any probability measures γ and θ on S, and λ and μ on IR^{d} we have [4, Corollary C.3.3]

R(γ × λ∥θ × μ) = R(γ∥θ) + R(λ∥μ),  (4.18)

we can write

\overline{E}_{x,ξ} \{\frac{1}{n} ∑_{j=0}^{n−1} R(ν_{j,prod}^{n}(·)||(p × ρ_{σ})(·|\overline{X}_{j}^{n}, \overline{Z}_{j}^{n}))\}
= \overline{E}_{x,ξ} \{\frac{1}{n} ∑_{j=0}^{n−1}[R(ν_{j}^{1,n}(·)||p(·|\overline{X}_{j}^{n}, \overline{Z}_{j}^{n})) + R(ν_{j}^{2,n}(·)||ρ_{σ}(·))]\} .

Then the representation formula implies that

W_{σ}^{n}(x, ξ) ≤ inf_{\{ν_{j,prod}^{n}\}} \overline{E}_{x,ξ} \{\frac{1}{n} ∑_{j=0}^{n−1}[R(ν_{j}^{1,n}(·)||p(·|\overline{X}_{j}^{n}, \overline{Z}_{j}^{n})) + R(ν_{j}^{2,n}(·)||ρ_{σ} (·))] + h(\overline{Y}^{n})\} .

(4.19)

We will show that this inequality implies that

lim sup_{n→∞} W_{σ}^{n}(x, ξ) ≤ ∫_{0}^{1} L_{σ}(ψ(t), ψ̇(t))dt + h(ψ) + θ(σ),  (4.20)

for ψ as in (4.16). We observe that, since L_{σ}(x, β) ≤ L(x, β) for all x and β ∈ IR^{d} (Lemma .5 part a) in the Appendix), (4.17) will follow after that.

The proof of (4.20) proceeds as follows. Let ψ^{∗} be as in part e) of Lemma .5 in the Appendix. We will design an admissible control sequence based on ψ^{∗} with the following properties: the running costs are nearly optimal and, with probability converging to 1, the process \overline{Y}^{n} ≐ \overline{X}^{n} + \overline{U}^{n} enters a small neighborhood of ψ^{∗} as n → ∞. The estimates that we obtain for the running costs will lead directly to (4.20).

Define the compact set

Δ ≡ ∪_{t∈[0,1]}{y ∈ IR^{d} : ||y − ψ^{∗}(t)|| ≤ 1}.

Let η = η(Δ, σ) ∈ (0, 1) satisfy the conclusions of part (d) of Lemma .5 when taking ε = σ. Also, let {x_{j}, j = 1 …, n} be a sequence in Δ satisfying ∥ψ^{∗}(j/n) − x_{j}∥ < η. For every n ∈ IN, j = 1, …, n and with x = ψ^{∗}(j/n), y = x_{j} and β = ψ̇^{∗}(j/n), part (d) of that lemma implies that there exists \overline{β}_{j}^{n} ∈ IR^{d} such that

L_{σ}(x_{j}, \overline{β}_{j}^{n}) − L_{σ}(ψ^{∗}(j/n), ψ̇^{∗}(j/n)) ≤ σ  (4.21)

and

||\overline{β}_{j}^{n} − ψ̇^{∗}(j/n)|| ≤ K∥ψ^{∗}(j/n) − x_{j}∥.

Further, \overline{β}_{j}^{n} = \overline{β}_{j}^{1,n} + \overline{β}_{j}^{2,n}, with

\overline{β}_{j}^{1,n} = ∫_{S} b(x_{j}, ξ)μ_{j,n}^{∗}(dξ), and \overline{β}_{j}^{2,n} = ∫_{IR^{d}} yν_{j,n}^{∗}(dy).

Here μ_{j,n}^{∗} is the invariant measure corresponding to the kernel γ_{j,n}^{∗} defined for B_{1} ∈ B(S) as

γ_{j,n}^{∗}(B_{1}|ψ^{∗}(j/n), ξ) = ∫_{B_{1}} exp{⟨α, b(ψ^{∗}(j/n), ζ)⟩ − Λ(ψ^{∗}(j/n), α)
+Ψ_{σ}(ψ^{∗}(j/n); α, ζ) − Ψ_{σ}(ψ^{∗}(j/n); α, ξ)}p(dζ|ψ^{∗}(j/n), ξ),

and for B_{2} ∈ B(IR^{d})

ν_{j,n}^{∗}(B_{2}) = ∫_{B_{2}} exp \{⟨α, y⟩ − \frac{σ^{2}||α||^{2}}{2} \} ρ_{σ}(dy).

Here α = α(ψ^{∗}(j/n), ψ̇^{∗}(j/n)) and ψ̇^{∗}(j/n) = ∫_{S} b(ψ^{∗}(j/n), ξ)μ_{j,n}^{∗}(dξ) + ∫_{IR^{d}} yν_{j,n}^{∗}(dy). We observe that, from part (h) of Lemma .4 in the Appendix,

L(x_{j}, \overline{β}_{j}^{1,n}) ≤ ∫_{S} R(γ_{j,n}^{∗}(·|ψ^{∗}(j/n), ξ)∥p(·|x_{j}, ξ))μ_{j,n}^{∗}(dξ)
= ⟨α(ψ^{∗}(j/n), ψ̇^{∗}(j/n)), \overline{β}_{j}^{n} − \overline{β}_{j}^{2,n}⟩ − Λ(ψ^{∗}(j/n), α(ψ^{∗}(j/n), ψ̇^{∗}(j/n)))
≤ L(ψ^{∗}(j/n), \overline{β}_{j}^{n} − \overline{β}_{j}^{2,n}).

Now, from part (c) of Lemma .5 and for \overline{β}_{j}^{n} as in (4.21), there exist a stochastic kernel γ_{j}^{1,n}(·|x_{j}, ξ) on S given S × IR^{d}, with invariant measure μ_{j}^{n}, and a measure γ_{j}^{2,n} on IR^{d} which achieve the infimum in the representation for L_{σ}. That is,

L_{σ}(x_{j}, \overline{β}_{j}^{n}) = ∫_{S} R(γ_{j}^{1,n}(·|x_{j}, ξ)||p(·|x_{j}, ξ))μ_{j}^{n}(dξ) + R(γ_{j}^{2,n}||ρ_{σ}),  (4.22)

and

\overline{β}_{j}^{n} = ∫_{S} b(x_{j}, ξ)μ_{j}^{n}(dξ) + ∫_{IR^{d}} yγ_{j}^{2,n}(dy) = \overline{β}_{j}^{1,n} + \overline{β}_{j}^{2,n},

where we have used formula (4.18). The kernel γ_{j}^{1,n} and the measure γ_{j}^{2,n} are defined, respectively, as

γ_{j}^{1,n}(B_{1}|x_{j}, ξ) = ∫_{B_{1}} e^{⟨α,b(x_{j},ζ)⟩+Ψ_{σ}(x_{j};α,ζ)−Ψ_{σ}(x_{j};α,ξ)+Λ(x_{j},α)}p(dζ|x_{j}, ξ)  (4.23)

and

γ_{j}^{2,n}(B_{2}) = ∫_{B_{2}} e^{⟨α,y⟩− \frac{σ^{2}}{2} ∥α∥^{2}}ρ_{σ}(dy),

with α = α(x_{j}, \overline{β}_{j}^{n}) = α(x_{j}, ψ^{∗}(j/n), ψ̇^{∗}(j/n)) in both γ_{j}^{1,n} and γ_{j}^{2,n}. Note that γ_{j}^{2,n} depends implicitly of x_{j} (through α), but we do not write this dependence explicitly for ease of notation.

We now use the kernels γ_{j}^{1,n} and γ_{j}^{2,n} to build a sequence of admissible controls that will enable us to prove (4.17). The construction is similar to the one used in Section 3. Let {m_{n}, n ∈ IN} be a sequence as the one used there, so that m_{n} → ∞ as n → ∞. Let k_{n} = m_{n}/n and l ∈ \{0, …, \frac{1}{k_{n}} − 1\}. Then for lm_{n} ≤ j < (l + 1)m_{n} − 1 we define

ν_{j}^{1,n}(dζ|x_{0}, …, x_{j}, u_{0}, …, u_{j}, ξ_{j}) ≐ \{ \begin{matrix}γ_{lm_{n}}^{1,n}(dζ|x_{lm_{n}}, ξ_{j}) & if max_{0≤i≤j} ∥x_{i} − ψ^{∗}(i/n)∥ ≤ η \\ p(dζ|x_{j}, ξ_{j}) & if max_{0≤i≤j} ∥x_{i} − ψ^{∗}(i/n)∥ > η \end{matrix}

and

ν_{j}^{2,n}(dy|x_{0}, …, x_{j}, u_{0}, …, u_{j}, ξ_{j}) ≐ \{ \begin{matrix}γ_{lm_{n}}^{2,n}(dy) & if & max_{0≤i≤j} ∥x_{i} − ψ^{∗}(i/n)∥ ≤ η \\ ρ_{σ}(dy) & if & max_{0≤i≤j} |x_{i} − ψ^{∗}(i/n)| > η. \end{matrix}

To simplify notation we have not made explicit the dependence on σ of ν_{j}^{1,n} and ν_{j}^{2,n}. Let \overline{X}_{0}^{n} = x ∈ IR^{d}, \overline{U}_{0}^{n} = 0, \overline{Z}_{0}^{n} = ξ ∈ S, and define

\overline{X}_{j+1}^{n} = \overline{X}_{j}^{n} + \frac{1}{n}b(\overline{X}_{j}^{n}, \overline{Z}_{j+1}^{n}), j = 0, …, n − 1

and

\overline{U}_{j+1}^{n} = \overline{U}_{j}^{n} + \frac{1}{n}\overline{G}_{j}^{n}, j = 0, …, n − 1,

where \overline{G}_{j}^{n}, \overline{Z}_{j}^{n}, lm_{n} ≤ j < (l + 1)m_{n} − 1 are random variables with joint distribution

\overline{P}_{x,ξ}\{(\overline{Z}_{j+1}^{n}, \overline{G}_{j}^{n}) ∈ (dξ × dy)|\overline{X}_{0}^{n}, …, \overline{X}_{j}^{n}, \overline{U}_{0}, … \overline{U}_{j}^{n}, \overline{Z}_{j}^{n}\} = ν_{j}^{1,n}(dζ) × ν_{j}^{2,n}(dy).

Now, for B_{1}, B_{2} ∈ B(S), B ∈ B(IR^{d}), define

ν_{l}^{1,n}(B_{1} × B_{2}) ≐ \frac{1}{m_{n}} ∑_{j=l_{n}}^{(l+1)m_{n}−1} δ\overline{Z}_{j}^{n}(B_{1}) × ν_{j}^{1,n}(B_{2}|\overline{X}_{0}^{n}, … \overline{X}_{j}^{n}, \overline{Z}_{j}^{n}),
ν_{l}^{2,n}(B) ≐ \frac{1}{m_{n}} ∑_{j=lm_{n}}^{(l+1)m_{n}−1} ν_{j}^{2,n}B|\overline{X}_{0}^{n}, …, \overline{X}_{j}^{n}),
ν^{1,n}(·|t) ≐ \{ \begin{matrix}ν_{l}^{1,n}(·) & if & t ∈ [lk_{n}, (l + 1)k_{n}) for l = 0, …, 1/k_{n} − 2 \\ ν_{( \frac{1}{kn} −1)}^{1,n}(·) & if & t ∈ [1 − k_{n}, 1] \end{matrix}

and

ν^{2,n}(·|t) ≐ \{ \begin{matrix}ν_{l}^{2,n}(·) & if & t ∈ [lk_{n}, (l + 1)k_{n}) for l = 0, …, 1/k_{n} − 2 \\ ν_{( \frac{1}{kn} −1)}^{2,n}(·) & if & t ∈ [1 − k_{n}, 1]. \end{matrix}

Define the random measures ν^{1,n} and ν^{2,n} on S × S × [0, 1] and IR^{d} × [0, 1], respectively, by:

ν^{1,n}(B_{1} × B_{2} × C) ≐ ∫_{C} ν^{1,n}(B_{1} × B_{2}|t)dt

and

ν^{2,n}(B × C) ≐ ∫_{C} ν^{2,n}(B|t)dt.

Further, let ν_{prod}^{n} be the random measure on S × S × IR^{d} × [0, 1] defined as

ν_{prod}^{n}(B_{1} × B_{2} × B × C) = ∫_{C} ν^{1,n}(B_{1} × B_{2}|t)ν^{2,n}(B|t)dt.

Finally, let τ^{n} = \frac{1}{n}(min\{i ∈ \{0, 1, …, n\} : ∥\overline{X}_{i}^{n} − ψ^{∗}(i/n)∥ > η\} ∧ n).

With these definitions we have that for j ≤ nτ^{n} − 1, and lm_{n} ≤ j ≤ (l + 1)m_{n} − 1 for some l ∈ \{0, …, \frac{1}{k_{n}} − 1\},

R(ν_{j}^{1,n}(·)∥p(·|\overline{X}_{j}^{n}, \overline{Z}_{j}^{n})) = R(γ_{lm_{n}}^{1,n}(·|\overline{X}_{lm_{n}}^{n}, \overline{Z}_{j}^{n})∥p(·|\overline{X}_{j}^{n}, \overline{Z}_{j}^{n}))

and

R(ν_{j}^{2,n}(·)∥ρ_{σ}(·)) = R(γ_{lm_{n}}^{2,n}(·)||ρ_{σ}(·)).

Moreover, the running cost has the form

\overline{E}_{x,ξ}\{\frac{1}{n} ∑_{j=0}^{n−1} R (ν_{j}^{1,n}(·) × ν_{j}^{2,n}(·)∥p(·|\overline{X}_{j}^{n}, \overline{Z}_{j}^{n}) × ρ_{σ}(·))\}

= \overline{E}_{x,ξ}\{\frac{1}{n} ∑_{j=0}^{nτ^{n}−1}[R(ν_{j}^{1,n}(·)∥p(·|\overline{X}_{j}^{n}, \overline{Z}_{j}^{n})) + R(ν_{j}^{2,n}(·)∥ρ_{σ}(·))]\}
= \overline{E}_{x,ξ}\{ ∑_{l=0}^{q_{n}−1} k_{n} [\frac{1}{m_{n}} ∑_{j=lm_{n}}^{(l+1)m_{n}−1}R(γ_{lm_{n}}^{1,n}(·|\overline{X}_{lm_{n}}^{n}, \overline{Z}_{j}^{n})∥p(·|\overline{X}_{j}^{n}, \overline{Z}_{j}^{n})) + R(γ_{lm_{n}}^{2,n}(·)∥ρ_{σ}(·))]
+\frac{1}{n} ∑_{j=q_{n}m_{n}}^{nτ^{n}−1}[R(γ_{q_{n}m_{n}}^{1,n}(·|\overline{X}_{q_{n}m_{n}}^{n}, \overline{Z}_{j}^{n})∥p(·|\overline{X}_{j}^{n}, \overline{Z}_{j}^{n}) + R(γ_{q_{n}m_{n}}^{2,n}(·)||ρ_{σ}(·))]\},  (4.24)

where q_{n} is such that nτ^{n} = q_{n}m_{n} + r_{n}, with 0 ≤ r_{n} < m_{n}, and q_{n}, r_{n} ∈ IN_{0}.

We now prove the following claim: for each j ≤ nτ^{n} − 1, lm_{n} ≤ j ≤ (l + 1)m_{n} − 1 for some l ∈ {0, …, q_{n}}, and n large enough,

R(γ_{lm_{n}}^{1,n}(·|\overline{X}_{lm_{n}}^{n}, \overline{Z}_{j}^{n})∥p(·|\overline{X}_{j}^{n}, \overline{Z}_{j}^{n})) ≤ R(γ_{lm_{n}}^{1,n}(·|\overline{X}_{lm_{n}}^{n}, \overline{Z}_{j}^{n})∥p(·|\overline{X}_{lm_{n}}^{n}, \overline{Z}_{j}^{n})) + σ. (4.25)

We first note that part c) of Hypothesis H.1 implies that for any x, y ∈ Δ, there exists δ > 0 such that for ∥x − y∥ < δ

\frac{p̃^{y}(ξ, ζ)}{p̃^{x}(ξ, ζ)} = 1 + \frac{p̃^{y}(ξ, ζ) − p̃^{x}(ξ, ζ)}{p̃^{x}(ξ, ζ)} ≤ 1 + \frac{p̃^{y}(ξ, ζ) − p̃^{x}(ξ, ζ)}{a} ≤ e^{σ}.  (4.26)

Then taking n large enough so that m_{n}∥b∥/n < δ, we have ∥\overline{X}_{lm_{n}+i}^{n} −\overline{X}_{lm_{n}}^{n}∥ ≤ \frac{i}{n}∥b∥_{∞} < δ for 0 ≤ i < m_{n} and hence

γ_{lm_{n}}^{1,n}(B_{1}|\overline{X}_{lm_{n}}^{n}, \overline{Z}_{j}^{n})

= ∫_{B_{1}} e^{⟨α,b(\overline{X}_{lmn}^{n},ζ)⟩+Ψ_{σ}(\overline{X}_{lmn}^{n};α,ζ)−Ψ_{σ}(\overline{X}_{lmn}^{n};α,ξ)−Λ(\overline{X}_{lmn}^{n},α)}p(dζ|\overline{X}_{lm_{n}}^{n}, \overline{Z}_{j}^{n})
= ∫_{B_{1}} e^{⟨α,b(\overline{X}_{lmn}^{n},ζ)⟩+Ψ_{σ}(\overline{X}_{lmn}^{n};α,ζ)−Ψ_{σ}(\overline{X}_{lmn}^{n};α,ξ)−Λ(\overline{X}_{lmn}^{n},α)}p̃^{\overline{X}{n \atop lmn}}(\overline{Z}_{j}^{n}, ζ)\frac{p̃^{\overline{X}{n \atop j}}(\overline{Z}_{j}^{n}, ζ)}{p̃^{\overline{X}{n \atop j}}(\overline{Z}_{j}^{n}, ζ)}ϑ(dζ)
≤ e^{σ} ∫_{B_{1}} e^{⟨α,b(\overline{X}_{lmn}^{n},ζ)⟩+Ψ_{σ}(\overline{X}_{lmn}^{n};α,ζ)−Ψ_{σ}(\overline{X}_{lmn}^{n};α,ξ)−Λ(\overline{X}_{lmn}^{n},α)}p̃^{\overline{X}{n \atop j}}(\overline{Z}_{j}^{n}, ζ)ϑ(dζ)  (4.27)

for any B_{1} ∈ B(S). ¿From the above we get that γ_{lm_{n}}^{1,n}(·|\overline{X}_{lm_{n}}^{n}, \overline{Z}_{j}^{n}) << p(·|\overline{X}_{j}^{n}, \overline{Z}_{j}^{n}) and that

\frac{dγ_{lm_{n}}^{1,n}(·|\overline{X}_{lm_{n}}^{n}, \overline{Z}_{j}^{n})}{dp(·|\overline{X}_{j}^{n}, \overline{Z}_{j}^{n})} = \frac{dγ_{lm_{n}}^{1,n}(·|\overline{X}_{lm_{n}}^{n}, \overline{Z}_{j}^{n})}{dp̃(·|\overline{X}_{lm_{n}}^{n}, \overline{Z}_{j}^{n})} · \frac{dp̃(·|\overline{X}_{lm_{n}}^{n}, \overline{Z}_{j}^{n})}{dp̃(·|\overline{X}_{j}^{n}, \overline{Z}_{j}^{n})}
≤ e^{σ} · \frac{dγ_{lm_{n}}^{1,n}(·|\overline{X}_{lm_{n}}^{n}, \overline{Z}_{j}^{n})}{dp̃(·|\overline{X}_{lm_{n}}^{n}, \overline{Z}_{j}^{n})},

which implies (4.25).

Fix \overline{ξ} ∈ S and normalize Ψ_{σ} in such a way that Ψ_{σ}(x; α, \overline{ξ}) = 0. Then, observing that

\frac{a}{A}e^{Ψ_{σ}(x;α,ξ_{1})} ≤ e^{Ψ_{σ}(x;α,ξ_{2})} ≤ \frac{A}{a}e^{Ψ_{σ}(x;α,ξ_{1})}

for all ξ_{1}, ξ_{2} ∈ S, and taking ξ_{1} = \overline{ξ}, we get that

\frac{a}{A} ≤ e^{Ψ_{σ}(x;,α,ξ)} ≤ \frac{A}{a}, ∀ξ ∈ S, x, α ∈ IR^{d}.  (4.28)

Then, from (4.23),

γ_{lm_{n}}^{1,n}(dζ|x, ξ) = e^{⟨α,b(x,ζ)⟩+Ψ_{σ}(x;α,ζ)−Ψ_{σ}(x;α,ξ)−Λ(x,α)}p̃^{x}(ξ, ζ)ϑ(dζ),

with α = α(x, \overline{β}_{lm_{n}}^{n}), x ∈ Δ, and \overline{β}_{lm_{n}}^{n} to satisfy (4.21), and hence

γ_{lm_{n}}^{1,n}(dζ|x, ξ) ≥ \frac{a^{3}}{A^{2}} e^{⟨α,b(x,ζ)⟩−Λ(x,α)}ϑ(dζ)
≥ \frac{a^{3}}{A^{2}} e^{−2||b||_{∞} max_{x} ||α||}ϑ(dζ).

Using the fact that (x, β) ↦ α(x, β) is continuous, we get that for x ∈ Δ, \overline{β}_{ℓm_{n}}^{n} belongs to the set Θ ≐ ⋃_{t∈[0,1]}\{β ∈ IR^{d} : ||β − ψ̇^{∗}(t)|| ≤ K\} and, moreover, that max\left\{{x∈Δ \atop β∈Θ}\right\} ||α|| is bounded.

We complete the estimate on the running cost for our admissible control sequence in the inequalities that follow. Here γ_{lm_{n}}^{1,n,j} shall denote the jth iteration of the kernel γ_{lm_{n}}^{1,n}. We observe that, from 16.0.2 in [11]:

∥γ_{lm_{n}}^{1,n,j}(·|x, ζ) − ν_{lm_{n}}(·)∥ ≤ ρ^{n}, with ρ = 1 − \frac{a^{3}}{A^{2}} e^{−2 max_{x,ζ} |⟨α,b(x,ζ)⟩|}

We have that (4.24) is less than or equal to

\overline{E}_{x,ξ} \{ ∑_{l=0}^{q_{n}−1} k_{n}[\frac{1}{m_{n}} ∑_{j=lm_{n}}^{(l+1)m_{n}−1} R(γ_{lm_{n}}^{1,n}(·\overline{X}_{lm_{n}}^{n}, \overline{Z}_{j}^{n}|)||p(·|\overline{X}_{lm_{n}}^{n}, \overline{Z}_{j}^{n})) + R(γ_{lm_{n}}^{2,n}(·)||ρ_{σ}(·))]

+\frac{1}{n} ∑_{j=q_{n}m_{n}}^{nτ^{n}−1}[R(γ_{q_{n}m_{n}}^{1,n}(·|\overline{X}_{q_{n}m_{n}}, \overline{Z}_{q_{n}m_{n}}^{n})||p(·|\overline{X}_{q_{n}m_{n}}^{n}, \overline{Z}_{j}^{n})) + R(γ_{q_{n}m_{n}}^{2,n}(·)||ρ_{σ}(·))]\} + σ

≤ ∑_{r=1}^{1/k_{n}} k_{n}\overline{E}_{x,ξ}\{∑_{l=0}^{r−1}[\frac{1}{m_{n}} ∑_{j=lm_{n}}^{(l+1)m_{n}−1} R(γ_{lm_{n}}^{1,n}(·|\overline{X}_{lm_{n}}^{n}, \overline{Z}_{j}^{n})||p(·|\overline{X}_{lm_{n}}^{n}, \overline{Z}_{j}^{n}))

+R(γ_{lm_{n}}^{2,n}(·)||ρ_{σ}(·))]1_{[(r−1)m_{n}<nτ^{n}≤rm_{n}]}} + σ

= ∑_{r=1}^{1/k_{n}} k_{n} ∑_{l=0}^{r−1} \overline{E}_{x,ξ}\{\overline{E}_{x,ξ}\{[\frac{1}{m_{n}} ∑_{j=lm_{n}}^{(l+1)m_{n}−1} R(γ_{lm_{n}}^{1,n}(·|\overline{X}_{lm_{n}}^{n}, \overline{Z}_{j}^{n})||p(·|\overline{X}_{lm_{n}}^{n}, \overline{Z}_{j}^{n}))

+R(γ_{lm_{n}}^{2,n}(·)||ρ_{σ}(·))]1_{[(r−1)m_{n}<nτ^{n}≤rm_{n}]}|\overline{Z}_{0}^{n}, …, \overline{Z}_{lm_{n}}^{n}, \overline{X}_{0}^{n}, …, \overline{X}_{rm_{n}}^{n}\}\} + σ

= ∑_{r=1}^{1/k_{n}} k_{n} ∑_{l=0}^{r−1} \overline{E}_{x,ξ}\{1_{[(r−1)m_{n}<nτ^{n}≤rm_{n}]}\overline{E}_{x,ξ}\{\frac{1}{m_{n}} ∑_{j=lm_{n}}^{(l+1)m_{n}−1} R(γ_{lm_{n}}^{1,n}(·|\overline{X}_{lm_{n}}^{n}, \overline{Z}_{j}^{n})||p(·|\overline{X}_{lm_{n}}^{n}, \overline{Z}_{j}^{n}))

+R(γ_{lm_{n}}^{2,n}(·)||ρ_{σ}(·))|\overline{Z}_{0}^{n}, …, \overline{Z}_{lm_{n}}^{n}, \overline{X}_{0}^{n}, …, \overline{X}_{rm_{n}}^{n}\}\} + σ

= ∑_{r=1}^{1/k_{n}} k_{n} ∑_{l=0}^{r−1} \overline{E}_{x,ξ}\{1_{[(r−1)m_{n}<nτ^{n}≤rm_{n}]}\overline{E}_{x,ξ}\{\frac{1}{m_{n}} ∑_{j=lm_{n}}^{(l+1)m_{n}−1} R(γ_{lm_{n}}^{1,n}(·|\overline{X}_{lm_{n}}^{n}, \overline{Z}_{j}^{n})||p(·|\overline{X}_{lm_{n}}^{n}, \overline{Z}_{j}^{n}))

+R(γ_{lm_{n}}^{2,n}(·)||ρ_{σ}(·))|\overline{Z}_{0}^{n}, …, \overline{Z}_{lm_{n}}^{n}, \overline{X}_{0}^{n}, …, \overline{X}_{lm_{n}}^{n}\}\} + σ

= ∑_{r=1}^{1/k_{n}} k_{n} ∑_{l=0}^{r−1} \overline{E}_{x,ξ}\{1_{[(r−1)m_{n}<nτ^{n}≤rm_{n}]}\overline{E}_{x,ξ}\{\frac{1}{m_{n}} ∑_{j=lm_{n}}^{(l+1)m_{n}−1}[⟨α_{lm_{n}}, ∫_{S} b(\overline{X}_{lm_{n}}^{n}, ζ)γ_{lm_{n}}^{1,n}(dζ|\overline{X}_{lm_{n}}^{n}, \overline{Z}_{j}^{n})⟩

+ ∫_{S} Ψ_{σ}(\overline{X}_{lm_{n}}^{n}; α_{lm_{n}}, ζ)γ_{lm_{n}}^{1,n}(dζ|\overline{X}_{lm_{n}}^{n}, \overline{Z}_{j}^{n}) − Ψ_{σ}(\overline{X}_{lm_{n}}^{n}; α_{lm_{n}}, \overline{Z}_{j}^{n})

−Λ(\overline{X}_{lm_{n}}^{n}, α_{lm_{n}})] + R(γ_{lm_{n}}^{2,n}(·)||ρ_{σ}(·))|\overline{Z}_{0}^{n}, …, \overline{Z}_{lm_{n}}^{n}, \overline{X}_{0}^{n}, …, \overline{X}_{lm_{n}}^{n}\}\} + σ

= ∑_{r=1}^{1/k_{n}} k_{n} ∑_{l=0}^{r−1} \overline{E}_{x,ξ}\{1_{[(r−1)m_{n}<nτ^{n}≤rm_{n}]}[\frac{1}{m_{n}} ∑_{j=lm_{n}}^{(l+1)m_{n}−1}(⟨α_{lm_{n}}, ∫_{S} b(\overline{X}_{lm_{n}}^{n}, ζ)γ_{lm_{n}}^{1,n,j}(dζ|\overline{X}_{lm_{n}}^{n}, \overline{Z}_{lm_{n}}^{n})⟩

+ ∫_{S} Ψ_{σ}(\overline{X}_{lm_{n}}^{n}; α_{lm_{n}}, ζ)γ_{lm_{n}}^{1,n,j+1}(dζ|\overline{X}_{lm_{n}}^{n}, \overline{Z}_{lm_{n}}^{n}) − ∫_{S} Ψ_{σ}(\overline{X}_{lm_{n}}^{n}; α_{lm_{n}}, ζ)γ_{lm_{n}}^{1,n,j}(dζ|\overline{X}_{lm_{n}}^{n}, \overline{Z}_{lm_{n}}^{n}) −Λ(\overline{X}_{lm_{n}}^{n}, α_{lm_{n}})) ± ∫_{S} R(γ_{lm_{n}}^{1,n}(·|\overline{X}_{lm_{n}}^{n}, ξ)||p(·|\overline{X}_{lm_{n}}^{n}, ξ))μ_{lm_{n}}(dξ) + R(γ_{lm_{n}}^{2,n}(·)||ρ_{σ}(·))]\} + σ

≤ ∑_{r=1}^{1/k_{n}} k_{n} ∑_{l=0}^{r−1} \overline{E}_{x,ξ}\{1_{[(r−1)m_{n}<nτ^{n}≤rm_{n}]}[\frac{1}{m_{n}} ∑_{j=lm_{n}}^{(l+1)m_{n}−1}⟨α_{lm_{n}}, ∫_{S} b(\overline{X}_{lm_{n}}^{n}, ζ)γ_{lm_{n}}^{1,n,j+1}(dζ|\overline{X}_{lm_{n}}^{n}, \overline{Z}_{lm_{n}}^{n})

− ∫_{S} b(\overline{X}_{lm_{n}}^{n}, ζ)μ_{lm_{n}}(dζ)⟩ + ∫_{S} R(γ_{lm_{n}}^{1,n}(·|\overline{X}_{lm_{n}}^{n}, ξ)||p(·|\overline{X}_{lm_{n}}^{n}, ξ))μ_{lm_{n}}(dξ)

+R(γ_{lm_{n}}^{2,n}(·)||ρ_{σ}(·))]\} + \frac{4}{n} ln \frac{A}{a} + σ

≤ ∑_{r=1}^{1/k_{n}} k_{n} ∑_{l=0}^{r−1} \overline{E}_{x,ξ}\{1_{[(r−1)m_{n}<nτ^{n}≤rm_{n}]}[\frac{||b||_{∞}A^{2}}{m_{n}a^{3}} max_{x∈Δ,β∈Θ}\{∥α(x, β)∥\}e^{2||b||_{∞} max_{x∈Δ,β∈Θ}\{∥α(x,β)∥\}}

+ ∫_{S} R(γ_{lm_{n}}^{1,n}(·|\overline{X}_{lm_{n}}^{n}, ξ)||p(·|\overline{X}_{lm_{n}}^{n}, ξ))μ_{lm_{n}}(dξ) + R(γ_{lm_{n}}^{2,n}(·)||ρ_{σ}(·))]\} + \frac{4}{n} ln \frac{A}{a} + σ

≤ \frac{||b||_{∞}A^{2}}{na^{3}} max_{x∈Δ,β∈Θ}\{′|α(x, β)∥\}e^{2||b||_{∞} max_{x∈Δ,β∈Θ}\{∥α(x,β)∥\}}

+ ∑_{r=1}^{1/k_{n}} k_{n} ∑_{l=0}^{r−1} \overline{E}_{x,ξ}\{1_{[(r−1)m_{n}<nτ^{n}≤rm_{n}]}[L_{σ}(\overline{X}_{lm_{n}}^{n}, \overline{β}_{lm_{n}}^{n})]\} + \frac{4}{n} ln \frac{A}{a} + σ

≤ ∑_{r=1}^{1/k_{n}} k_{n} ∑_{l=0}^{r−1} \overline{E}_{x,ξ}\{1_{[(r−1)m_{n}<nτ^{n}≤rm_{n}]}L_{σ}(ψ^{∗}(\frac{lm_{n}}{n}), ψ̇^{∗}(\frac{lm_{n}}{n}))\}

+\frac{4}{n} ln \frac{A}{a} + 2σ + \frac{||b||_{∞}A^{2}}{na^{3}} max_{x∈Δ,β∈Θ}\{∥α(x, β)∥\}e^{2||b||_{∞} max_{x∈Δ,β∈Θ}\{∥α(x,β)∥\}}

≤ \overline{E}_{x,ξ}\{∑_{l=0}^{[ \frac{τ^{n}}{kn}]} k_{n}L_{σ}(ψ^{∗}(\frac{lm_{n}}{n}), ψ̇^{∗}(\frac{lm_{n}}{n}))\} + 3σ, for n large enough,
≤ k_{n} ∑_{l=0}^{[1/k_{n}]} L_{σ}(ψ^{∗}(\frac{lm_{n}}{n}), ψ̇^{∗}(\frac{lm_{n}}{n})) + 3σ.  (4.29)

We conclude that the admissible control sequence that we constructed has running cost which is nearly optimal, as we had claimed.

We can now return to the proof of (4.20). All of the claims that follow refer to the nearly optimal admissible control sequence constructed above. Since L_{σ} is continuous, ψ^{∗} is continuous and ψ̇^{∗} has only a finite number of discontinuities,

sup_{n} \overline{E}_{x,ξ} \{\frac{1}{n} ∑_{j=0}^{n−1} R(ν_{j}^{1,n}(·) × ν_{j}^{2,n}(·)||p(·|\overline{X}_{j}^{n}, \overline{Z}_{j}^{n}) × ρ_{σ}(·))\} < ∞.  (4.30)

Then, Theorem 5.3.5 in [4] and the fact that S is compact imply that, given any subsequence of \{(ν^{1,n}, ν^{2,n}, \overline{X}^{n}, \overline{U}^{n}, τ^{n}), n ∈ IN\}, there exists a subsubsequence such that (ν^{1,n}, ν^{2,n}, \overline{X}^{n}, \overline{U}^{n}, τ^{n}) converges in distribution to (ν^{1}, ν^{2}, \overline{X}, \overline{U}, τ), when n → ∞. ¿From part e) of Theorem .7 in the Appendix we know that

\overline{X}(t) = x + ∫_{0}^{t} ∫_{S} b(\overline{X}(s), ζ)ν̂_{1}(dζ|s)ds,

where ν^{1}(dζ × dy × ds) = ν̂_{1}(dζ|s) ⊗ ν̂_{2}(dy|ζ, x) ⊗ ds and ν̂_{1}(dζ|s) is an invariant measure of ν̂_{2}(dy|ζ, s). Furthermore,

\overline{U}(t) = ∫_{IR^{d}×[0,1]} yν^{2}(dy × ds),

and

\overline{Y} (t) ≐ lim_{n→∞} \overline{Y}^{n}(t) = lim_{n→∞} \overline{X}(t) + lim_{n→∞} \overline{U}(t) = \overline{X}(t) + \overline{U}(t).

Let \{(ν^{1,n}, ν^{2,n}, \overline{X}^{n}, \overline{U}^{n}, τ^{n})\} be a convergent subsubsequence. Then, (4.29) and Lemma .5(e) (with ε = σ) imply that

lim sup_{n→∞} \overline{E}_{x,ξ} \{ \frac{1}{n} ∑_{j=1}^{n−1}[R(ν_{j}^{1,n}(·)||p(·|\overline{X}_{j}^{n}, \overline{Z}_{j}^{n})) + R(ν_{j}^{2,n}(·)||ρ(·))] + h(\overline{Y}^{n})\}
≤ ∫_{0}^{1} L_{σ}(ψ^{∗}(t), ψ̇^{∗}(t))dt + 3σ + lim sup_{n→∞} Ē_{x,ξ}{h(Ȳ^{n})}
≤ ∫_{0}^{1} L_{σ}(ψ(t), ψ̇(t))dt + 4σ + lim sup_{n→∞} Ē_{x,ξ}{h(Ȳ^{n})}.

Thus, the proof of (4.20) will be complete once we prove that

lim sup \overline{E}_{x,ξ}h(\overline{Y}^{n}) ≤ h(ψ) + θ̃(σ),

with θ̃(σ) → 0 when σ → 0. This in turn will be implied by

lim_{σ→0} lim sup_{n→∞} \overline{P}_{x,ξ}\{ sup_{t∈[0,1]} ||\overline{Y}^{n}(t) − ψ^{∗}(t)|| ≥ σ\} = 0,  (4.31)

because of the Lipschitz property of h and Lemma .5(e). ¿From the definition of \overline{β}_{j}^{1,n}, and Lemma .5 (d), for each l ∈ \{0, …, [\frac{τ^{n}}{k_{n}}]\},

||\overline{β}_{lm_{n}}^{n} − ψ̇^{∗}(\frac{lm_{n}}{n})|| = ||\overline{β}_{lm_{n}}^{1,n} + \overline{β}_{lm_{n}}^{2,n} − ψ̇^{∗}(\frac{lm_{n}}{n})||
= || ∫_{S} b(\overline{X}_{lm_{n}}^{n}, ξ)μ_{lm_{n}}^{n}(dξ) + ∫_{IR^{d}} yν_{lm_{n}}^{2,n}(dy) − ψ̇^{∗}(\frac{lm_{n}}{n})||
≤ K||\overline{X}_{lm_{n}}^{n} − ψ^{∗}(\frac{lm_{n}}{n})||.  (4.32)

Also, from the proof Lemma .7(e), when n → ∞

S^{1,n}(t) ≐ x + ∫_{0}^{t} ∫_{S×} b(S^{1,n}(s), ξ_{2})ν^{1,n}(dξ_{1} × dξ_{2}|s)ds → \overline{X}(t)

and

S^{2,n}(t) ≐ ∫_{IR^{d}×[0,t]} yν^{2,n}(dy × ds) → \overline{U}(t)

in distribution for almost all t ∈ [0, 1]. Let t ∈ [0, τ]. Then,

||\overline{Y} ( t) − ψ^{∗}(t)|| = lim_{n→∞} || ∫_{0}^{t} ∫_{S×S} b(S^{n}(s), ξ_{2})ν^{1,n}(dξ_{1} × dξ_{2}|s)ds

− ∫_{S×S×[0,t]} b(X̃^{n}(s), ξ_{2})ν^{1,n}(dξ_{1} × dξ_{2}|s)ds + ∫_{S×S×[0,t]} b(X̃^{n}(s), ξ_{2})ν^{1,n}(dξ_{1} × dξ_{2}|s)ds

+ ∑_{l=0}^{[ \frac{t}{kn}]} k_{n} ∫_{IR^{d}} yν_{lm_{n}}^{2,n}(dy) − ∑_{l=0}^{[ \frac{t}{kn}]} k_{n} ∫_{S} b(X̃_{lm_{n}}^{n}, ξ)μ_{lm_{n}}^{n}(dξ)

+ ∑_{l=0}^{[ \frac{t}{kn}]} k_{n} ∫_{S} b(X̃_{lm_{n}}^{n}, ξ)μ_{lm_{n}}^{n}(dξ) − ∫_{0}^{t} ψ̇^{∗}(s)ds||

≤ lim sup_{n→∞} ∫_{0}^{1}(K||S^{1,n}(s) − X̃^{n}(s)|| ∧ 2∥b∥_{∞})ds

+ lim sup_{n→∞} ∑_{l=0}^{[ \frac{t}{kn}]} k_{n}||\frac{1}{m_{n}} ∑_{j=l}^{(l+1)m_{n}} ∫_{S} b(\overline{X}_{lm_{n}}, ζ)γ_{lm_{n}}^{1,n,j}(dζ|\overline{X}_{lm_{n}}^{n}, \overline{Z}_{lm_{n}})

− ∫_{S} b(\overline{X}_{lm_{n}}^{n}, ξ)μ_{lm_{n}}^{n}(dξ)|| + lim sup_{n→∞} K ∫_{0}^{t} ||\overline{X}^{n}(s) − ψ^{∗}(s)||ds

≤ lim sup_{n→∞} ∑_{l=0}^{[ \frac{t}{kn}]} k_{n}||b||_{∞} \frac{A^{2}}{a_{n}^{3}} e^{2||b||_{∞} max_{x∈Γ,β∈Θ}\{∥α(x,β)∥\}}

+K ∫_{0}^{t} ||\overline{X}(s) − ψ^{∗}(s)||ds

= K ∫_{0}^{t} ||\overline{X}(s) − ψ^{∗}(s)||ds
≤ ∫_{0}^{t} ||\overline{X}(s) − \overline{Y} (s)||ds + K ∫_{0}^{t} ||\overline{Y} (s) − ψ^{∗}(s)||ds
≤ K sup_{s∈[0,τ]} ||\overline{X}(s) − \overline{Y} (s)|| + K ∫_{0}^{t} ||\overline{Y} (s) − ψ^{∗}(s)||ds.

Let \overline{K} ≐ Ke^{K}. By Gronwall’s inequality,

sup_{s∈[0,τ]} ||\overline{Y} (s) − ψ^{∗}(s)|| ≤ \overline{K} sup_{s∈[0,τ]} ||\overline{X}(s) − \overline{Y} (s)|| = \overline{K} sup_{s∈[0,τ]} ||\overline{U}(s)||,

which together with Lemma .6 implies that, for any σ > 0,

lim_{σ→0} \overline{P}_{x,ξ}\{ sup_{t∈[0,τ]} ||\overline{Y} (s) − ψ^{∗}(s)|| ≥ σ\} ≤ lim_{σ→0} \overline{P}_{x,ξ}\{ sup_{t∈[0,τ]} ||\overline{U}(s)|| ≥ \frac{σ}{\overline{K}} \} = 0.

Since \overline{X} = \overline{Y} − \overline{U}, for 0 ≤ σ ≤ η/2,

lim_{σ→0} \overline{P}_{x,ξ}\{ sup_{t∈[0,τ]} ||\overline{X}(t) − ψ^{∗}(t)|| ≥ σ\} ≤ lim_{σ→0} \overline{P}_{x,ξ}\{ sup_{t∈[0,τ]} ||\overline{U}(t)|| ≥ σ/2\}

+ lim_{σ→0} \overline{P}_{x,ξ}\{ sup_{t∈[0,τ]} ||\overline{Y} (t) − ψ^{∗}(t)|| ≥ σ/2\}

= 0.

Finally, writing τ = τ_{σ}, it can be proved, following the same arguments given in [4, p. 205-206], that

lim_{σ→0} \overline{P}_{x,ξ}\{τ_{σ} < 1\} = 0,

which implies (4.31). This completes the proof of the lower bound.

Appendix

Representation Formulas

In this appendix we discuss the representation formulas used in the proof of Theorem 2.2. In particular, we shall establish variational representations for the quantity

W^{n}(x, ξ) ≐ −\frac{1}{n} log E_{x,ξ} \{exp[−nh(X^{n})]\} ,  (.33)

and for the quantity

W_{σ}^{n}(x, ξ) ≐ −\frac{1}{n} log E_{x,ξ} \{exp[−nh(Y_{σ}^{n})]\} ,  (.34)

where X^{n} and Y_{σ}^{n} are defined by (1.4) and (4.12), respectively, E_{x,ξ} denotes expectation conditioned on X_{0}^{n} = x and Z_{0}^{n} = ξ and h is bounded and continuous. We will only discuss the representation for the first quantity in detail, since the representation for the second quantity is derived in a completely analogous way.

Theorem .1 states the representation for the quantity W^{n}(x, ξ) in terms of the minimal cost function of a certain stochastic control problem. Before stating the theorem, we introduce the appropriate control problem.

We define a discrete-time controlled process taking values in IR^{d} × S denoted by {(X̄_{j}^{n}, Z̄_{j}^{n}), j = 0, …, n}. The control at time j is given by the distribution of the controlled random variable Z̄_{j}^{n}, namely, a stochastic kernel ν(dζ|X̄_{0}^{n}, …, X̄_{j}^{n}, Z̄_{j}^{n}) on S given (IR^{d})^{j+1} × S. A sequence of controls {ν_{j}^{n}, j = 0, …, n − 1} is what we refer to as an admissible control sequence.

Now, setting Z̄_{0}^{n} = ξ and X̄_{0}^{n} = x, the evolution of the controlled process is through the relation

X̄_{j+1}^{n} = X̄_{j}^{n} + \frac{1}{n}b(X̄_{j}^{n}, Z̄_{j+1}^{n}),

where the the conditional distribution of Z̄_{j+1}^{n} is given by

P̄ {Z̄_{j+1}^{n} ∈ dζ|X̄_{0}^{n}, …, X̄_{j}^{n}, Z̄_{0}^{n}, …, Z̄_{j}^{n}} = ν_{j}^{n}(dζ|X̄_{0}^{n}, …, X̄_{j}^{n}, Z̄_{j}^{n}).

Finally, we define X̄^{n} = {X̄^{n}(t), t ∈ [0, 1]} to be the piecewise linear interpolation of {X̄_{j}^{n}, j = 0, …, n} (see (1.4)). We consider the minimal cost function

V^{n}(x, ξ) ≐ inf_{\{ν_{j}^{n}\}} Ē_{x,ξ} \{\frac{1}{n} ∑_{j=0}^{n−1} R(ν_{j}^{n}(·)∥p(·|X̄_{j}^{n}, Z̄_{j}^{n})) + h(X̄^{n})\} .  (.35)

Here R is the relative entropy function; ν_{j}^{n}(·) = ν_{j}^{n}(·|X̄_{0}^{n}, …, X̄_{j}^{n}, Z̄_{j}^{n}); the infimum is taken over all admissible control sequences {ν_{j}^{n}, j = 0, …, n−1}; Ē_{x,ξ} denotes expectation conditioned on X̄_{0}^{n} = x and Z̄_{0}^{n} = ξ; {(X̄_{j}^{n}, Z̄_{j}^{n})} is the controlled process associated with a particular control sequence {ν_{j}^{n}}; and h is the same function appearing in the definition (.33) of W^{n}(x, ξ). We can now state the representation formula.

Theorem .1 Let h be a bounded measurable function mapping C([0, 1] : IR^{d}) ↦ IR. Then for all n ∈ IN, x ∈ IR^{d} and ξ ∈ S the quantity W^{n}(x, ξ) defined in (.33) equals the minimal cost function V^{n}(x, ξ) defined in (.35), so that

W^{n}(x, ξ) = inf_{\{ν_{j}^{n}\}} Ē_{x,ξ} \{\frac{1}{n} ∑_{j=0}^{n−1} R(ν_{j}^{n}(·)∥p(·|X̄_{j}^{n}, Z̄_{j}^{n})) + h(X̄^{n})\} .

Proof. For any starting time i ∈ {0, …, n} and any points x_{0}, x_{1}, …, x_{i} ∈ IR^{d} and ξ_{i} ∈ S, we start by defining

W^{n}(i, \{x_{0}, …, x_{i}\}, ξ_{i}) ≐ −\frac{1}{n} log E_{ξ} \{exp [−nh(X^{n})|X_{0}^{n} = x_{0}, …, X_{i}^{n} = x_{i}, Z_{i}^{n} = ξ_{i}]\} .

We identify x_{0} with x. Then W^{n}(0, {x}, ξ) equals W^{n}(x, ξ), while W^{n}(n, {x, …, x_{n}}, ξ_{n}) equals h(X^{n}). Taking i ∈ {0, …, n − 1}, we use the Markov property to write:

exp [−nW^{n}(i, {x, …, x_{i}}, ξ_{i})]
= E_{ξ} {exp [−nh(X^{n})] |X_{0}^{n} = x, …, X_{i}^{n} = x_{i}, Z_{0}^{n} = ξ_{0}, …, Z_{i}^{n} = ξ_{i}}
= E_{ξ} {E {exp [−nh(X^{n})] |X_{0}^{n} = x, …, X_{i+1}^{n}, Z_{i+1}^{n}, Z_{i}^{n}} |X_{0}^{n} = x, …, Z_{i}^{n} = ξ_{i}}
= E_{ξ} \{exp [−nW^{n}(i + 1, \{x, …, x_{i} + \frac{1}{n}b(x_{i}, ξ_{i+1})\}, ξ_{i+1})] |X_{0}^{n} = x, …, Z_{i}^{n} = ξ_{i}\}
= ∫_{S} exp [−nW^{n}(i + 1, \{x, …, x_{i} + \frac{1}{n}b(x_{i}, ζ)\}, ζ)] p(dζ|x_{i}, ξ_{i}).

Therefore

W^{n}(i, \{x, …, x_{i}\}, ξ_{i}) = −\frac{1}{n} log ∫_{S} exp [−nW^{n}(i + 1, \{x, …, x_{i} + \frac{1}{n}b(x_{i}, ζ)\}, ζ)] p(dζ|x_{i}, ξ_{i}).

Applying the variational formula in Proposition 1.4.2(a) of [4] we obtain a dynamic programming equation (DPE) of the form

\{ \begin{matrix}W^{n}(i, \{x, …, x_{i}\}, ξ_{i}) \\ = inf_{ν∈P(S)} \{\frac{1}{n}R(ν(·)∥p(·|x_{i}, ξ_{i})) + ∫_{S} W^{n}(i, \{x, …, x_{i} + \frac{1}{n}b(x_{i}, ζ)\}, ζ)ν(dζ)\} \\ W^{n}(n, \{x, …, x_{n}\}, ξ_{n}) = h(X^{n}). \end{matrix}

What we will show is that the quantities W^{n}(i, {x, …, x_{i}}, ξ) are not the only solution to the DPE, but that it is also satisfied by the minimal cost functions

V^{n}(i, \{x, …, x_{i}\}, ξ_{i}) ≐ inf_{\{ν_{j}^{n}\}} Ē_{i,\{x,...,x_{i}\}} \{∑_{j=i}^{n−1} \frac{1}{n}R(ν_{j}^{n}(·)∥p(·|X̄_{j}^{n}, Z̄_{j}^{n}) + h(X^{n})\} .

Since the DPE and the terminal condition have a unique solution, then the conclusion of the theorem will follow.

We know that if a certain attainment condition is satisfied, then Theorem 1.5.2 in [4] guarantees that indeed V^{n}(i, {x, …, x_{i}}, ξ) are bounded, measurable and are the unique solution to the DPE. This attainment condition requires that there exist an admissible control sequence {ν̃_{j}^{n}, j = 0, …, n} such that the infimum in the DPE is attained. Since such a sequence exists - it can be checked that the sequence of kernels {ν_{j}^{n}, j = 0, … n} on S given (IR^{d})^{i} × S defined for every Borel set B of S through

ν̃_{j}^{n}(B|x, …, x_{j}, ξ) ≐ \frac{∫_{B} exp [−nW^{n}(j + 1, \{x, …, x_{j}, x_{j} + \frac{1}{n}b(x_{j}, ζ)\}, ζ)] p(dζ|x_{j}, ξ)}{∫_{S} exp [−nW^{n}(j + 1, \{x, …, x_{j}, x_{j} + \frac{1}{n}b(x_{j}, ζ)\}, ζ)] p(dζ|x_{j}, ξ)}

is indeed infimizing - the proof of the theorem is complete.

Using the same approach, one can prove the representation in Theorem .2 for the quantity W_{σ}^{n}(x, ξ). We first state the appropriate stochastic control problem.

Let p × ρ_{σ} be the stochastic kernel on S × IR^{d}, given ξ ∈ S, x ∈ IR^{d}, defined by (p × ρ_{σ})(dζ × dy|x, ξ) ≐ p(dζ|x, ξ) × ρ_{σ}(dy). We consider admissible control sequences consisting of stochastic kernels ν_{j}^{n}(dζ × dy|x_{0}, …, x_{j}, u_{0}, …, u_{j}, z_{j}) on S × IR^{d} given (x_{0}, …, x_{j}), (u_{0}, …, u_{j}) ∈ (IR^{d})^{j+1} and z_{j} ∈ S. Once again we identify x_{0} with x. For each admissible control sequence {ν_{j}^{n}}, the controlled system is defined through

\overline{X}_{0}^{n}  ≐ x  \overline{U}_{0}^{n}  ≐ 0
\overline{X}_{j+1}^{n} ≐ \overline{X}_{j}^{n} + \frac{1}{n}b(\overline{X}_{j}^{n}, \overline{Z}_{j+1}^{n}), \overline{U}_{j+1}^{n} ≐ \overline{U}_{j}^{n} + \frac{1}{n} \overline{G}_{j}^{n}
\overline{Y} _{j}^{n} = \overline{X}_{j}^{n} + \overline{U}_{j}^{n},

where the conditional distribution of (\overline{Z}_{j+1}^{n}, \overline{G}_{j}^{n}) is given by

\overline{P}_{x,ξ}((\overline{Z}_{j+1}^{n}, \overline{G}_{j}^{n}) ∈ dζ × dy|\overline{X}_{0}^{n}, …, \overline{X}_{j}^{n}, \overline{U}_{0}^{n}, …, \overline{U}_{j}^{n}, \overline{Z}_{j}^{n}) =
ν_{j}^{n}(dζ × dy|\overline{X}_{0}^{n}, …, \overline{X}_{j}^{n}, \overline{U}_{0}^{n}, …, \overline{U}_{j}^{n}, \overline{Z}_{j}^{n}).

Define now the processes \overline{X}^{n} ≐ \{\overline{X}^{n}(t), t ∈ [0, 1]\}, \overline{U}^{n} = \{\overline{U}^{n}(t), t ∈ [0, 1]\} and \overline{Y}^{n} ≐ \{\overline{Y}^{n}(t), t ∈ [0, 1]\} as the linear interpolations of \{\overline{X}_{j}^{n}\}, \{\overline{U}_{j}^{n}\} and \{\overline{Y} _{j}^{n}\}, respectively (see (1.4)). In this case the minimal cost function takes the form

V_{σ}^{n}(x, ξ) ≐ inf_{\{ν_{j}^{n}\}} \overline{E}_{x,ξ}\{\frac{1}{n} ∑_{j=0}^{n−1} R(ν_{j}^{n}(·)||(p × ρ_{σ})(·|\overline{X}_{j}^{n}, \overline{Z}_{j}^{n})) + h(\overline{Y}^{n})\}.

Theorem .2 Let h be a bounded measurable function mapping C([0, 1] : IR^{d}) ↦ IR. Then for all n ∈ IN, x ∈ IR^{d}, ξ ∈ S and σ > 0, the quantity W_{σ}^{n}(x, ξ) defined in (.34) equals the minimal cost function V_{σ}^{n}(x, ξ), so that

W_{σ}^{n}(x, ξ) = inf_{\{ν_{j}^{n}\}} \overline{E}_{x,ξ}\{\frac{1}{n} ∑_{j=0}^{n−1} R(ν_{j}^{n}(·)||(p × ρ_{σ})(·|\overline{X}_{j}^{n}, \overline{Z}_{j}^{n})) + h(\overline{Y}^{n})\}.

Properties of the functions L and L_{σ}.

In this appendix we establish properties of the functions Λ(x, α) and L(x, β) defined in (1.3) and (2.5) respectively, and of the function L_{σ} defined in (4.13).

Lemma .3 Under Hypothesis H.1, the function Λ(x, α) defined in (1.3) satisfies the following properties. For each x ∈ IR^{d}, Λ(x, α) is a finite strictly convex function of α ∈ IR^{d} which is differentiable for all α. In addition, Λ(x, α) is a continuous function of (x, α) ∈ IR^{d} × IR^{d}.

These properties follow from Lemmas 3.1 and 3.4 in [10] given the relation between the function Λ and the solution to the eigenvalue problem given in (1.2).

The next lemma establishes important properties of the function L which is the Frechel-Legendre transform of the function Λ.

Lemma .4 Under Hypothesis H.1, the function L(x, β) defined in (2.5) satisfies the following properties. a) For each x ∈ IR^{d}, L(x, β) is a convex and lowersemicontinuous function of β ∈ IR^{d}.

b) L(x, β) ≥ −Λ(x, 0).

c) L(x, β) achieves its minimum of −Λ(x, 0) (equal to 0) at β̄ if and only if β̄ ∈ ∂Λ(0) and, furthermore, such a β̄ exists.

d) If L(x, β) is finite in a neighborhood of β′, then ∂L(x, β′) is nonempty and L(x, β′) = ⟨α, β′⟩ − Λ(x, α) if and only if α ∈ ∂L(β′).

e) There is uniqueness in the sense that there is only one convex and lower semicontinuous function Λ such that L = Λ^{∗}.

f) If L achieves its minimum at β = 0 then Λ(x, α) ≥ Λ(x, 0).

g) L(x, β) → ∞ as ∥β∥ → ∞.

h) For each x and β in IR^{d}

L(x, β) = inf {∫_{S} R(γ(ξ|·)∥p(ξ|·))μ(dξ) : γμ = μ, ∫_{S} b(x, ξ)dμ = β} .

If L is finite, then the infimum is attained uniquely.

Proof. Since Λ is finite and convex, properties a) - g) above are proved in [3, Lemma 2.1]. We now show h).

We first note that for any β ∈ IR^{d} such that L(x, β) = +∞ then the infimum is attained at any kernel γ whose invariant measure has mean β. Hence we can restrict our attention to β ∈ ri(domL(x, ·)).

For α ∈ IR^{d} let γ_{α} be the stochastic kernel defined by

\frac{dγ_{α}(ξ|·)}{dp(ξ|·)}(ζ) = \frac{e^{⟨α,b(x,ζ)⟩+ψ(ζ)}}{∫_{S} e^{⟨α,b(x,ζ)⟩+ψ(ζ)}p(ξ|dζ)}

In terms of the function Λ defined in (1.2) we can write

\frac{dγ_{α}(ξ|·)}{dp(ξ|·)}(ζ) = e^{−Λ(α)−ψ(ξ)+⟨α,b(x,ξ)⟩+ψ(ζ)}.

Let μ_{α} be the unique invariant measure of γ_{α}. (Proposition 4.1 in [10] guarantees that such a measure exists). Part d) of the present lemma implies that there exists a unique α = α(x, β) such that

L(x, β) = ⟨α(x, β), β⟩ − Λ(x, α(x, β))  (.36)

with α(x, β) ∈ ∂L(β) if and only if β ∈ ∂H(α(x, β)), so that β = ∫_{S} b(x, ξ)μ^{α}(dξ). Since β = ∇Λ(α(x, β)), Proposition 4.1 in [10] gives

E_{μ^{α}}^{γ_{α}}b(x, ξ) = ∫_{S} b(x, ξ)μ^{α}(dξ) = β.

Now let γ be any kernel (with corresponding invariant measure μ^{γ}) satisfying

∫_{S} b(x, ξ)μ^{γ}(dξ) = β

and

∫_{S} R(γ(ξ|·)∥p(ξ|·))μ^{γ}(ξ) < ∞.

Then γ(ξ|·) << p(ξ|·) for μ^{γ}- almost all ξ. Since \frac{dγ_{α}}{dp} is strictly positive, γ(ξ|·) << γ_{α}(ξ|·) for almost all ξ (with respect to μ^{γ}) and

∫ R(γ(ξ|·)∥p(ξ|·))μ^{γ}(dξ)

= ∫ ∫ log \frac{dγ(ξ|ζ)}{dp(ξ|ζ)}(ζ)γ(ξ|dζ)μ^{γ}(dξ)

= ∫ ∫ log [\frac{dγ(ξ)}{dγ_{α}(ξ)}(ζ)\frac{dγ_{α}(ξ)}{dp(ξ)}(ζ)] γ(ξ|dζ)μ^{γ}(dξ)

= ∫ [∫ log \frac{dγ(ξ)}{dγ_{α}(ξ)}(ζ)γ(ξ|dζ) + ∫ log \frac{dγ_{α}(ξ)}{dp(ξ)}(ζ)γ(ξ|dζ)] μ^{γ}(dξ)

= ∫ R(γ(ξ|·)∥γ_{α}(ξ|·))μ^{γ}(dξ) + ∫ ∫ log [exp [⟨α, b(x, ζ)⟩ + ψ(ζ) − ψ(ξ) − Λ(α)]] γ(ξ|dζ)μ^{γ}(dξ) = ∫ R(γ(ξ|·)∥γ_{α}(ξ|·))μ^{γ}(dξ) − Λ(α) − ∫ ψ(ξ)μ^{γ}(dξ) + ∫ ∫ [⟨α, b(x, ζ)⟩ + ψ(ζ)] γ(ξ|dζ)μ^{γ}(dξ) = ∫ R(γ(ξ|·)∥γ_{α}(ξ|·)μ^{γ}(dξ) − Λ(α) + ∫ ⟨α, b(x, ξ)⟩μ^{γ}(dξ) = ∫ R(γ(ξ|·)∥γ_{α}(ξ|·)μ^{γ}(dξ) − Λ(α) + ⟨α, β⟩ = ∫ R(γ(ξ|·)∥γ_{α}(ξ|·)μ^{γ}(dξ) − Λ(α) + ⟨α, β⟩ = ∫ R(γ(ξ|·)∥γ_{α}(ξ|·)μ^{γ}(dξ) + L(x, β) ≥ L(x, β).

Equality is obtained if and only if γ ≡ γ_{α}. Remark.

a) Since Λ(x, ·) is strictly convex on IR^{d}, L(x, ·) is differentiable on int(domL(x, ·)). See Theorem D.2.8 in [4].

b) For each β ∈ int(domL(x, ·)) there exists α = α(x, β) ∈ IR^{d} with α(x, β) = ∇L(x, β) and L(x, β) = ⟨α(x, β), β⟩ − Λ(x, α(x, β)). This follows from part (d) of Lemma .4

The next result establishes properties of the function L_{σ} defined in (4.13) that are needed in the proof of the lower bound.

Lemma .5 Given σ > 0, the function L_{σ}(x, β) satisfies the following properties.

(a) L_{σ}(x, β) = inf_{z∈IR^{d}}\{L(x, β − z) + \frac{||z||^{2}}{2σ^{2}} \} and L_{σ}(x, β) ≤ L(x, β).

(b) L_{σ}(x, β) is a finite, nonnegative, continuous function of (x, β) ∈ IR^{d}×IR^{d}. Moreover, L_{σ}(x, ·) is differentiable on IR^{d}

(c)

L_{σ}(x, β) = inf{∫_{S} R(γ(·|x, ξ) × υ(·)||p(·|x, ξ) × ρ_{σ}(·))μ(dξ) :
μγ = μ, ∫_{S} b(x, ξ)μ(dξ) + ∫_{IR^{d}} yυ(dy) = β}.

Further, for each x, β ∈ IR^{d}, there exist a stochastic kernel γ^{∗} and a measure υ^{∗} such that the infimum on the right hand side is achieved. For Borel sets B_{1} of S and B_{2} of IR^{d}, these are given by:

γ^{∗}(B_{1}|x, ξ) ≐ ∫_{B_{1}} e^{⟨α,b(x,ζ)⟩−Λ(x,α)−ψ_{σ}(x,α,ξ)+ψ_{σ}(x,α,ζ)}p(dζ|x, ξ)

and

υ^{∗}(B_{2}) ≐ ∫_{B_{2}} e^{⟨α,y⟩− \frac{σ^{2}||α||^{2}}{2}} ρ_{σ}(dy),

with α = α(x, β) ∈ argmax{⟨α, β⟩ − Λ_{σ}(x, α) : α ∈ IR^{d}}.

(d) Given any compact set Δ ⊂ IR^{d}, and ε ∈ (0, 1), there exists η ∈ (0, 1) such that, whenever x, y ∈ Δ, β ∈ IR^{d}, and ||x − y|| ≤ η there exists \overline{β} ∈ IR^{d} such that:

a) L_{σ}(y, \overline{β}) − L_{σ}(x, β) ≤ ε

b) ||\overline{β} − β|| ≤ K||x − y||, where K is the Lipschitz constant of b.

(e) Given ψ ∈ C([0, 1], IR^{d}) satisfying I_{x,ξ}(ψ) < ∞ and ε > 0, there exists ψ^{∗} ∈ N such

that ||ψ − ψ^{∗}||_{∞} < ε and

∫_{0}^{1} L_{σ}(ψ^{∗}(t), ψ̇^{∗}(t))dt ≤ ∫_{0}^{1} L_{σ}(ψ(t), ψ̇(t))dt + ε
≤ I_{x,ξ}(ψ) + ε.

(f) The function (x, β) → α(x, β) ∈ argmax_{α∈IR^{d}}{⟨α, β⟩ − Λ_{σ}(x, α)} is continuous. Proof.

(a) Follows from Corollay D.4.2 in [D–E], while for the second part we take z = 0.

(b) From [12, Corollary 2.6.4] and Lemma 3.4 (iv) in [10], int(Dom L_{σ}(x, ·)) = Range(∇Λ_{σ}(x, ·)) = IR^{d}. So L_{σ}(x, β) < ∞ for all (x, β) ∈ IR^{d} × IR^{d}. The nonnegativity of L_{σ}(x, β) follows from the nonnegativity of L(x, β). The continuity follows from Lemma C.8.1 in [4] and the continuity of Λ(x, α) in both variables. Finally, the differentiability follows from the strict convexity of Λ and Theorem D.2.8 in [4].

(c) Let x, β ∈ IR^{d}. From Part (b) there exists α ∈ IR^{d}, with α = α(x, β), such that β = ∇_{α}Λ_{σ}(x, α) and L_{σ}(x, β) = ⟨α, β⟩ − Λ_{σ}(x, α).

Let

γ(x, α; ξ|dζ × dy) = exp{⟨α, b(x, ζ) + y⟩ + Ψ(x; α, ζ) − Ψ(x; α, ξ) − Λ(x, α)

−\frac{σ^{2}}{2} ||α||^{2}\}p(dζ|x, ξ)ρ_{σ}(dy).

¿From Proposition 4.1 in [10],

β = ∫ b(x, ξ)μ(dξ) + ∫ ye^{− \frac{σ^{2}}{2} ||α||^{2}+⟨α,y⟩}ρ_{σ}(dy),

where μ is the unique invariant measure of the kernel

γ_{1}(x, α, ξ|dζ) = exp{⟨α, b(x, ζ) + y⟩ + Ψ(x; α, ζ) − Ψ(x; α, ξ) − Λ(x, α)}p(dζ|x, ξ)

The rest of the proof follows the same arguments given in Lemma .4 (h).

(d) Let Δ ⊂ IR^{d} compact, x, y ∈ Δ, β ∈ IR^{d}, and ε > 0. We know, from Part (c), that there exist γ^{∗} and υ^{∗} such that the infimum in part (c) is attained for (x, β). Define \overline{β} ≐ ∫_{S} b(y, ξ)μ^{γ^{∗}}(dξ) + ∫_{IR^{d}} yν^{∗}(dy). Then, from the representation formula given in Part (c),

||β − \overline{β}|| ≤ ∥ ∫ (b(x, ξ) − b(y, ξ))μ^{γ^{∗}}(dξ)∥
≤ K∥x − y∥.

Now, for any Borel set B of S, we can use part c) of Hypothesis H.1 to write

γ^{∗}(B|x, ξ) = ∫_{B} exp{⟨α, b(x, ζ)⟩ + Ψ_{σ}(x; α, ζ) − Ψ_{σ}(x; α, ξ) − Λ(x, α)}p̃^{x}(ξ, ζ)ϑ(dζ).

From the bound that we have on p̃^{x}(·, ·), it follows that γ^{∗}(·|x, ξ) is absolutely continuous with respect to p(·|y, ξ); and from the uniform continuity of p̃^{x}(ξ, ζ), there exists η > 0 such that ∥x − y∥ < η implies that

p̃^{x}(ξ, ζ) ≤ p̃^{y}(ξ, ζ)e^{ε}.  (.37)

(this is as in lines (4.26)). Then, from the variational equivalence given in Part (c), L_{σ}(y, \overline{β}) < ∞, and

L_{σ}(y, \overline{β}) ≤ ∫ R(γ^{∗}(·|x, ξ) × ν^{∗}(·)||p(·|y, ξ) × ρ_{σ}(·))μ^{γ^{∗}}(dξ)
≤ ⟨α, ∫ b(x, ξ)μ^{γ^{∗}}(dξ)⟩ − Λ(x, α) + ⟨α, ∫_{IR^{d}} yν^{∗}(dy)⟩ − \frac{σ^{2}}{2} ||α|| + ε
= ⟨α, β⟩ − Λ_{σ}(x, α) + ε
= L_{σ}(x, β) + ε

(e) The proof of this part is based in Lemmas 6.5.3 and 6.5.5 of [4], which in our case also hold due to the structural properties given in Parts (a) and (b).

(f) Given x, β ∈ IR^{d}, Part (b) and the differenciability of α → Λ_{σ}(x, α) imply that there exists a unique α(x, β) such that L_{σ}(x, β) = ⟨α(x, β), β⟩ − Λ_{σ}(x, α(x, β)), β = ∇_{α}Λ_{σ}(x, α(x, β)) and α(x, β) = ∇_{β}L_{σ}(x, β). We observe that β → L_{σ}(x, β) is continuously differentiable thanks to [12, Corollary 25.5.1]. Moreover, x → ∇_{β}L_{σ}(x, β) is continuous [12, Theorem 25.7] and in fact (x, β) → ∇_{β}L_{σ}(x, β) is continuous by the same theorem. Therefore, (x, β) → α(x, β) is continuous in both variables.

The last lemma in this appendix establishes an estimate needed in the proof of the lower bound.

Lemma .6 For any δ > 0,

lim_{σ→0} \overline{P}_{x,ξ}\{ sup_{t∈[0,1]} ||\overline{U}(t)|| ≥ δ\} = 0.

Proof. Let (ν^{1,n}, ν^{2,n}, \overline{X}^{n}, \overline{U}^{n}, τ^{n}) → (ν^{1}, ν^{2}, \overline{X}, \overline{U}, τ) and define

S^{n}(t) ≐ ∫_{IR^{d}×[0,1]} yν^{2,n}(dy × ds).

¿From (4.30), sup_{n} \overline{E}_{x,ξ}\{\frac{1}{n} ∑_{j=0}^{n−1} R(ν_{j}^{2,n}||ρ)\} < ∞, and Proposition 5.3.8 in [4] implies that S^{n} → \overline{U} in distribution in C([0, 1]; IR^{d}). The next inequality follows from the Skorohod Representation Theorem and Fatou’s Lemma:

\overline{E}_{x,ξ}\{( sup_{t∈[0,1]} ||\overline{U}(t)||)^{2}\} ≤ lim inf_{n→∞} \overline{E}_{x,ξ}\{( sup_{t∈[0,1]} ||S^{n}(t)||)^{2}\}.  (.38)

Then we have that for any δ > 0,

\overline{P}_{x,ξ}[ sup_{t∈[0,1]} ||\overline{U}(t)|| ≥ δ] ≤ \frac{1}{δ^{2}} \overline{E}_{x,ξ}\{( sup_{t∈[0,1]} ||\overline{U}(t)||)^{2}\}
≤ \frac{1}{δ^{2}} lim inf_{n→∞} \overline{E}_{x,ξ}\{( sup_{t∈[0,1]} || ∫_{IR^{d}×[0,1]} yν^{2,n}(dy × ds)||)^{2}\}
≤ \frac{1}{δ^{2}} lim inf_{n→∞} \overline{E}_{x,ξ}\{\frac{1}{n} ∑_{j=0}^{n−1} || ∫_{IR_{d}} yν_{j}^{2,n}(dy)||^{2}\}

= \frac{1}{δ^{2}} lim inf_{n→∞} \overline{E}_{x,ξ}\{\frac{1}{n} ∑_{j=0}^{nτ^{n}−1} ||β_{j}^{2,n}||^{2}\}
≤ \frac{2σ^{2}}{δ^{2}} lim inf_{n→∞} \overline{E}_{x,ξ}\{\frac{1}{n} ∑_{j=0}^{nτ^{n}−1} R(γ_{j}^{2,n}||ρ_{σ})\}
≤ \frac{2σ^{2}}{δ^{2}} lim inf_{n→∞}\{k_{n} ∑_{l=0}^{[1/k_{n}]} L_{σ}(ψ^{∗}(\frac{lm_{n}}{n}), ψ̇^{∗}(\frac{lm_{n}}{n})) + 3σ\}
= \frac{2σ^{2}}{δ^{2}} [∫_{0}^{1} L_{σ}(ψ^{∗}(t), ψ̇^{∗}(t))dt + 3σ]
≤ \frac{2σ^{2}}{δ^{2}} [I_{x,ξ}(ψ) + 4σ].

The fifth inequality follows noting that \frac{1}{2σ^{2}} ||β_{j}^{2,n}||^{2} = L_{σ}(β_{j}^{2,n}) ≤ R(γ_{j}^{2,n}||ρ), where L_{σ} is the Frechel-Legendre of the moment generating function of ρ_{σ}. The sixth line follows from (4.24) and (4.29), while in line eight we used Part (e) of Lemma .5 with ε = σ. Finally we et

\overline{P}_{x,ξ}( sup_{t∈[0,1]} ||\overline{U}(t)|| ≥ δ) ≤ lim_{σ→0} \frac{2σ^{2}}{δ^{2}} [I_{x,ξ}(ψ) + 4σ] = 0,

which proves the lemma.

Proofs of some limit results

This appendix is dedicated to the proofs of some limit results needed in the proof of Theorem 2.2.

Theorem .7 For any x ∈ IR^{d}, ξ ∈ S and each n ∈ IN, consider any admissible control sequence such that

sup_{n∈IN} Ē_{x,ξ} \{\frac{1}{n} ∑_{j=0}^{n−1} R(ν_{j}^{n}(·)∥p(·|X̄_{j}^{n}, Z̄_{j}^{n}))\} < ∞,

where ν_{j}^{n}(·) = ν_{j}^{n}(·|X̄_{0}^{n}, …, X̄_{j}^{n}, Z̄_{j}^{n}). In terms of these sequences we define the piecewise linear interpolation {X̄^{n}}, the piecewise constant interpolation {X̃^{n}}, the sequence of admissible control measures {ν^{n}} and its marginals {ν̃_{2}^{n} ⊗ λ, ν̃_{1}^{n} ⊗ λ}, and the measures {γ^{n}} as in Section 3. The following conclusions hold. a) Given any subsequence of {(ν^{n}, ν̃_{2}^{n} ⊗ λ, ν̃_{1}^{n} ⊗ λ, γ^{n}, n ∈ IN}, there exist a subsubse-

quence, a probability space (Ω̄, F̄, P̄_{x,ξ}), a a measure ν on S×S×[0, 1] with marginals μ_{1}, μ_{2}, and a measure γ on S × S × [0, 1] such that the subsubsequence converges in distribution to (ν, μ_{1}, μ_{2}, γ).

b) The stochastic kernel ν has the decomposition

ν(B_{1} × B_{2} × C) = ∫_{C} ν(B_{1} × B_{2}|t)dt = ∫_{C} ∫_{B_{1}} ν̂_{1}(dζ|t)ν̂_{2}(B_{2}|ζ, t)dt

for some stochastic kernels ν(·|t) on S×S given [0, 1]×Ω̄, ν̂_{1}(·|t) on S given [0, 1]×Ω̄ and ν̂_{2}(·|ζ, t) on S given S × [0, 1] × Ω̄.

c) We have the equality ν̂_{1} ⊗ λ = ν̂_{2} ⊗ λ.

d) Let q̄(dy|ζ, t) ≐ ν̂_{2}(dy|ζ, t). Then ν̂_{1}(dζ|t) is an invariant measure of q̄ for each t ∈ [0, 1].

e) Let {n} be the subsubsequence obtained in Part (a). Then {X̄^{n}, X̃^{n}} converges to X̄ almost surely, where for every t ∈ 0, 1]

X̄(t) ≐ x + ∫_{S×S×[0,t]} b(X̄(s), y)ν(dζ × dy × ds)
= x + ∫_{0}^{t} ∫_{S} b(X̄(s), ξ)ν̂_{1}(dζ|s)ds,

with ν̂_{1} an invariant measure for q̄.

f) The kernel γ is has the decomposition

γ(B_{1} × B_{2} × C) = ∫_{C} ∫_{S×S} ν̃_{1}(B_{1}|t) ⊗ p(ζ, B_{2}|X̄(t))dt.

Proof.

a) Given the compactness of S, we immediately get tightness of ν^{n}, of γ^{n} and of all the marginals. Since the function mapping ν^{n} into (ν^{n}, ν̃_{1}^{n} ⊗ λ, ν̃_{2}^{n} ⊗ λ) is continuous, there exist measures ν and γ over S ×S ×[0, 1] and measures μ_{1} and μ_{2} over S ×[0, 1] such that (ν^{n}, ν̃_{1}^{n} ⊗λ, ν̃_{2}^{n} ⊗λ, γ^{n}) ⟶^{D} (ν, μ_{1}, μ_{2}) [4, Theorem A.3.6]. Moreover, w.p.1 μ_{1} and μ_{2} equal the marginals of ν over (z, t) and over (y, t) respectively.

b) We let μ_{3} denote the marginal of ν over t. By the Skorohod Representation Theorem we can assume that ν^{n} ⟹ ν and for i = 1, 2 ν̃_{i}^{n} ⊗ λ ⟹ μ_{i} w.p.1 on (Ω̄, F̄, P̄). Using the fact that the marginal of ν^{n} is Lebesgue measure λ, we have that w.p.1 for any bounded continuous function g mapping [0, 1] into IR

∫_{0}^{1} g(t)μ_{3}(dt) = ∫_{S×S×[0,1]} g(t)ν(dζ × dy × dt)
= lim_{n→∞} ∫_{S×S×[0,1]} g(t)ν^{n}(dζ × dy × dt)
= lim_{n→∞} ∫_{0}^{1} g(t)dt
= ∫_{0}^{1} g(t)dt.

Since the class of bounded and continuous functions is a measure determining class [1, Theorem 1.3], this implies that w.p.1 μ_{3}(·) equals λ(·). By Theorem A.5.6 in [4], there exists a stochastic kernel ν(dζ × dy|t) on S × S given [0, 1] such that w.p.1

ν(B_{1} × B_{2} × C) = ∫_{C} ν(B_{1} × B_{2}|t) dt.

Once more Theorem A.5.6 in [4] gives the existence of stochastic kernels on S given S × [0, 1] ν̃_{2}(dy|ζ, t), ν̃_{1}(dζ|t) the second and first marginals of ν(dζ × dy|t) such that

ν(B_{1} × B_{2} × C) = ∫_{C} ∫_{B_{1}} ν̃_{1}(dζ|t)ν̃_{2}(B_{2}|ζ, t)dt.

This gives the decomposition of ν(dζ × dy × dt) given in part (b). In terms of these kernels we can write μ_{1}(dζ × dt) = ν̃_{1}(dζ|t) ⊗ λ(dt) and μ_{2}(dy × dt) = ν̃_{2}(dy|ζ, t) × ν̃_{1}(S|t) × λ(dt).

c) It is enough to check that

∫ f(y, t)(ν̃_{1} ⊗ λ)(dy × dt) = ∫ f(y, t)(ν̃_{2} ⊗ λ)(dy × dt)

with f(y, t) = g(y)h(t), g ∈ C(S : IR^{d}) and h ∈ C([0, 1] : IR^{d}) (see Theorem A.3.14 in [4]). Since

Ē_{x,ξ} {g(Z̄_{j+1}^{n}) − ∫_{S} g(y)ν_{j}^{n}(dy|X̄_{0}, … X̄_{j}^{n}, Z̄_{j}^{n})} = 0,

we have that

{g(Z̄_{j+1}^{n}) − ∫_{S} g(y)ν_{j}^{n}(dy|X̄_{0}^{n}, …, X̄_{j}^{n}, Z̄_{j}^{n})}

is a martingale difference sequence. Therefore

∫_{[0,1]×_{S}} f(ζ, t)(ν̃_{1}^{n} ⊗ λ)(dζ × dt) = ∫_{0}^{1} h(t) ∫_{S} g(ζ)ν̃_{1}^{n}(dζ|t)dt
= ∑_{l=0}^{\frac{1}{kn} −1} ∫_{lk_{n}}^{(l+1)k_{n}} h(t) ∫_{S} g(ζ)ν̃_{1}^{n}(dζ|t)dt
= ∑_{l=0}^{\frac{1}{kn} −1} ∫_{lk_{n}}^{(l+1)k_{n}} h(t)dt · ∫_{S} g(ζ)(ν_{l}^{n})_{1}(dζ)
= ∑_{l=0}^{\frac{1}{kn} −1} ∫_{lk_{n}}^{(l+1)k_{n}} h(t)dt · \frac{1}{m_{n}} ∑_{j=lm_{n}}^{(l+1)m_{n}−1} g(Z̄_{j}^{n}).

Similarly,

∫_{[0,1]×S} f(y, t)(ν̃_{2}^{n} ⊗ λ)(dy × dt)

= ∑_{l=0}^{\frac{1}{kn} −1} [\frac{1}{m_{n}} ∑_{j=lm_{n}}^{(l+1)m_{n}−1} ∫ g(y)ν_{j}^{n}(dy)] · ∫_{lk_{n}}^{(l+1)k_{n}} h(t)dt.

Therefore

∫_{0}^{1} ∫_{S} f(y, t)(ν̃_{1}^{n} ⊗ λ)(dy × dt) − ∫_{0}^{1} ∫_{S} f(y, t)(ν̃_{2}^{n} ⊗ λ)(dy × dt)

= ∑_{l=0}^{\frac{1}{kn} −1} \frac{1}{m_{n}} [∫_{lk_{n}}^{(l+1)k_{n}} h(t)dt] [ ∑_{j=lm_{n}}^{(l+1)m_{n}−1} (g(Z̄_{j+1}^{n}) − ∫ g(y)ν_{j}^{n}(dy|X̄_{0}^{n}, …, X̄_{j}^{n}, Z̄_{j}^{n}))

+[g(Z̄_{lm_{n}}^{n}) − g(Z̄_{(l+1)m_{n}}^{n})]].

Note that

∥ ∑_{l=0}^{\frac{1}{kn} −1} \frac{1}{m_{n}} [∫_{lk_{n}}^{(l+1)k_{n}} h(t)dt] [g(Z̄_{lm_{n}}^{n}) − g(Z̄_{(l+1)m_{n})}^{n}]∥ ≤ \frac{2∥g∥∥h∥}{m_{n}},

so that if m_{n} ≥ \frac{4∥g∥∥h∥}{ε} then

P̄_{x,ξ} {|∫_{S} fd(ν̃_{1}^{n} ⊗ λ) − ∫_{S} fd(ν̃_{2}^{n} ⊗ λ)| ≥ ε}

≤ P̄_{x,ξ} \{| ∑_{l=0}^{\frac{1}{kn} −1} \frac{1}{m_{n}} [∫_{lk_{n}}^{(l+1)k_{n}} h(t)dt] [ ∑_{j=lm_{n}}^{(l+1)m_{n}−1} (g(Z̄_{j+1}^{n}) − ∫ g(y)ν_{j}^{n}(dy))]| ≥ \frac{ε}{2}\}

≤ P̄_{x,ξ} \{|\frac{1}{n} ∑_{j=0}^{n−1} [g(Z̄_{j+1}^{n}) − ∫ g(y)ν_{j}^{n}(dy)]| ≥ \frac{ε}{2∥h∥}\}

≤ \frac{4∥h∥^{2}}{ε^{2}} Ē_{x,ξ} \{\frac{1}{n^{2}} (∑_{j=0}^{n−1} [g(Z̄_{j+1}^{n}) − ∫ g(y)ν_{j}^{n}(dy)])^{2}\}

≤ \frac{4∥h∥^{2}}{ε^{2}} Ē_{x,ξ} \{\frac{1}{n^{2}} ∑_{j=0}^{n−1} (g(Z̄_{j+1}^{n}) − ∫ g(y)ν_{j}^{n}(dy))^{2}\}

≤ \frac{4∥h∥^{2}}{ε^{2}} · \frac{1}{n^{2}} · 4∥g∥^{2} · n = \frac{16∥h∥^{2}∥g∥^{2}}{nε^{2}} .

This implies that ∫_{S} fd(ν̃_{1}^{n} ⊗ λ) − ∫_{S} fd(ν̃_{2}^{n} ⊗ λ) converges to zero in probability, so that ([4, Theorem A.3.7])

∫_{S} fd(ν̃_{1}^{n} ⊗ λ) − ∫_{S} fd(ν̃_{2}^{n} ⊗ λ) ⟶^{D} 0.

Given the convergence in distribution of ν̃_{1}^{n} ⊗ λ and ν̃_{2}^{n} ⊗ λ to ν_{1} ⊗ λ and ν_{2} ⊗ λ respectively, we can appply the Skorohod Representation Theorem to get w.p.1

lim_{n→∞} ∫_{S} fd(ν̃_{1}^{n} ⊗ λ) = ∫_{S} fd(ν̃_{1} ⊗ λ)

and

lim_{n→∞} ∫_{S} fd(ν̃_{2}^{n} ⊗ λ) = ∫_{S} fd(ν̃_{2} ⊗ λ).

Therefore w.p.1

∫_{S} fd(ν̃_{1} ⊗ λ) = ∫_{S} fd(ν̃_{2} ⊗ λ).  (.39)

Theorem A.3.14 in [4] implies that we can extend the equality in (.39) from f of the form f(x, t) = g(x)h(t) to all f : S × [0, 1] ↦ IR that is bounded and continuous. Since the class of bounded continous functions is measure-determing, we have that ν̃_{1} ⊗ λ = ν̃_{2} ⊗ λ, as we wanted to show. d) Now we show that for each t ∈ [0, 1], and Borel subset B_{1} of S we have

ν̃_{1}(B_{1}|t) = ∫_{S} ν̃_{2}(B_{1}|ζ, t)ν̃_{1}(dζ|t).  (.40)

Let U_{b}(S) denote the space of bounded, uniformly continuous functions mapping S into IR. Since S is Polish, there exists an equivalent metric m under which U_{b}(S, m) is separable with respect to the uniform metric. Let E be a countable dense subset of U_{b}(S, m), and let g be any function in E. For each s ∈ [0, 1] let E_{i} ⊂ [0, 1] be a sequence of sets which shrinks nicely to s, and define

f(t, x) ≐ g(x) · \frac{1}{λ(E_{i})}I_{E_{i}}(t).

Since ν̃_{1} ⊗ λ = ν̃_{2} ⊗ λ,

\frac{1}{λ(E_{i})} ∫_{E_{i}} ∫_{S} g(y)ν̃_{1}(dy|t)λ(dt) = \frac{1}{λ(E_{i})} ∫_{E_{i}} ∫_{S} ∫_{S} g(y)ν̃_{2}(dy|ζ, t)ν̃_{1}(dζ|t)λ(dt).

Define h_{1}(t) ≐ ∫_{S} g(y)ν̃_{1}(dy|t) and h_{2}(t) ≐ ∫_{S} ∫_{S} g(y)ν̃_{2}(dy|ζ, t)ν̃_{1}(dζ|t). Then we have

|h_{1}(s) − h_{2}(s)|

≤ |\frac{1}{λ(E_{i})} ∫_{E_{i}} h_{1}(t)dt − h_{1}(s)| + |\frac{1}{λ(E_{i})} ∫_{E_{i}} h_{2}(t)dt − h_{2}(s)|

≤ \frac{1}{λ(E_{i})} ∫_{E_{i}} |h_{1}(t) − h_{1}(s)| dt + \frac{1}{λ(E_{i})} ∫_{E_{i}} |h_{2}(t) − h_{2}(s)| dt,

which tends to 0 as n → ∞ for almost all s ∈ [0, 1] (see Theorem C.13 in [2]). This implies that h_{1}(s) = h_{2}(s) a.s., that is,

∫_{S} g(y)ν̃_{1}(dy|t) = ∫_{S} ∫_{S} g(y)ν̃_{2}(dy|ζ, t)ν̃_{1}(dζ|t) a.s.

This in turn implies that there exists a set B_{g} ∈ B([0, 1]) with λ(B_{g}) = 0 and such that ∫_{S} g(y)ν̃_{1}(dy|t) = ∫_{S} ∫_{S} g(y)ν̃_{2}(dy|ζ, t)ν̃_{1}(dζ|t) for all t ∉ B_{g}. Now define the set B as

B ≐ ∪_{g∈E}B_{g}.

Then λ(B) = 0 and for all t ∉ B and g ∈ E we have

∫ g(y)ν̃_{1}(dy|t) = ∫_{S} ∫_{S} g(y)ν̃_{2}(dy|ζ, t)ν̃_{1}(dζ|t).

This equality, valid for g ∈ E, is extended to g ∈ U_{b}(S, m), which implies that ν̃_{1}(dy|t) = ν̃_{2}(dy|t) for all t ∉ B. Finally, redefining in an obvious way ν̃_{1} and ν̃_{2} for t ∈ B, we get .40.

References

[1] P. Billingsley. Convergence of Probability Measures. John Wiley & Sons, New York, 1968.

[2] A. Dembo, O. Zeitouni. large Deviations Techniques and Applications Second Edition. Springer Verlag, 1998.

[3] P. Dupuis. Large deviations analysis of some recursive algorithms with state dependent noise. The Annals of Probability, 16, 1509-1536, 1988.

[4] P. Dupuis, R. Ellis. A Weak Convergence Approach to the Theory of Large Deviations. John Wiley & Sons, 1996.

[5] S.N. Ethier, T.G. Kurtz. Markov Processes: Characterization and Convergence. John Wiley & Sons, New York, 1986.

[6] M.I. Freidlin, A.D. Wentzell. Random perturbations of dynamical systems. Springer– Verlag, Berlin, 1984.

[7] H.J. Kushner. Approximation and weak convergence methods for random processes with applications to stochastic system theory. Cambridge, MIT Press, 1984.

[8] H.J. Kushner and F.J. Vázquez-Abad. Stochastic approximation methods for systems over an infinite horizon, SIAM Journal on Control and Optimization 34, 712-756, 1996.

[9] H.Y. Kushner and G.G. Yin. Stochastic Approximation Algorithms and Applications. Springer-Verlag, NY, 1997.

[10] I. Iscoe, P. Ney, E. Nummelin. Large deviations of uniformly recurrent Markov additive processes. Advances in Applied Mathematics 6, 373-412, 1985.

[11] S.P. Meyn and R.L. Tweedie. Markov Chains and Stochastic Stability, Springer-Verlag, London, 1993.

[12] R. T. Rockafellar. Convex Analysis. Princeton University Press, 1970.