# On the rare-event simulations of diffusion processes pertaining to a chain
of distributed systems with small random perturbations††thanks: Version 1.0 –
August, 2020.

Getachew K. Befekadu222Department of Electrical & Computer Engineering, Morgan
State University, 1700 E. Cold Spring Lane, Schaefer Engr. Bldg. 331,
Baltimore, MD 21251, USA (getachew.befekadu@morgan.edu).

###### Abstract

In this paper, we consider an importance sampling problem for a certain rare-
event simulations involving the behavior of a diffusion process pertaining to
a chain of distributed systems with random perturbations. We also assume that
the distributed system formed by $n$-subsystems – in which a small random
perturbation enters in the first subsystem and then subsequently transmitted
to the other subsystems – satisfies an appropriate Hörmander condition. Here
we provide an efficient importance sampling estimator, with an exponential
variance decay rate, for the asymptotics of the probabilities of the rare
events involving such a diffusion process that also ensures a minimum relative
estimation error in the small noise limit. The framework for such an analysis
basically relies on the connection between the probability theory of large
deviations and the values functions for a family of stochastic control
problems associated with the underlying distributed system, where such a
connection provides a computational paradigm – based on an exponentially-
tilted biasing distribution – for constructing efficient importance sampling
estimators for the rare-event simulation. Moreover, as a by-product, the
framework also allows us to derive a family of Hamilton-Jacobi-Bellman for
which we also provide a solvability condition for the corresponding optimal
control problem.

###### keywords:

Diffusion processes, distributed systems, exit probability, HJB equations,
importance sampling, large deviations, rare-event simulation, stochastic
control problem

###### AMS:

37H10, 35F21, 49K15, 49L20, 60F10, 65C05

##  1 Introduction

In this paper, we consider an importance sampling problem for a certain rare-
event simulations involving the behavior of a diffusion process pertaining to
a chain of distributed systems with random perturbations. We also assume that
the distributed system formed by $n$-subsystems – in which a small random
perturbation enters only in the first subsystem and then subsequently
transmitted to the other subsystems – satisfies an appropriate Hörmander
condition and, as a result of this, the corresponding diffusion process is
assumed to have a transition probability density with strong Feller property
(e.g., see [19], [21], [2] and [8] for related discussions from the physical
point of view). Here we provide an efficient importance sampling estimator,
with an exponential variance decay rate, for the asymptotics of the
probabilities of the rare-event simulations involving the behavior of such a
diffusion process which also ensures a minimum relative estimation error in
the small noise limit case. The framework for such an analysis basically
relies on the connection between the probability theory of large deviations
(i.e., the asymptotics for exit probabilities from a given bounded open
domain) and that of the values functions for a family of stochastic control
problems associated with the underlying distributed system, where such a
connection also provides a desirable computational paradigm – based on an
exponentially-tilted biasing distribution – for constructing an efficient
importance sampling estimator for rare-event simulations in the context of
such a diffusion process. Moreover, as a by-product, the framework also allows
us to derive a family of Hamilton-Jacobi-Bellman for which we also provide a
solvability condition for the corresponding optimal control problem.

Here, it is worth mentioning that a number of interesting studies based on
various approximations techniques from the theory of large deviations have
provided a framework for constructing efficient importance sampling estimators
for rare-event simulation problems involving the behavior of diffusion
processes (e.g., [4], [6], [7], [18] and [24] for additional discussions). The
main approach followed in these studies is to construct exponentially-tilted
biasing distributions, which was originally introduced for proving Cramér’s
theorem and its extension, and later on it was found to be an efficient
importance sampling distribution for certain problems with various
approximations involving rare-events (e.g., see [20], [1], [15] or [6] for
detailed discussions). Note that the rationale behind our framework follows in
some sense the settings of these papers. However, to our knowledge, the
problem of rare-event simulations involving the behavior of a diffusion
process pertaining to a chain of distributed systems has not been addressed in
the context of stochastic control arguments along with asymptotic analysis in
the small noise limit; and it is important because it provides a framework for
constructing an efficient importance sampling estimator for rare-event
simulations in the context of such a diffusion process.

This paper is organized as follows. In Section 2, we discuss our problem
formulation, where we start by considering a diffusion process pertaining to a
distributed systems with small random perturbations and we formalize our
problem formulation. In this section, we also provide an asymptotic estimate
on the exit probability using the Ventcel-Freidlin theorem [27] (see also [13,
Chapter 4]) and the stochastic control arguments from Fleming [12] (see also
[11]). In particular, as we discuss in detail in Subsection 2.2, such an
asymptotic estimate relies on the interpretation of the exit probability
function as a value function for a family of stochastic control problems that
can be associated with the underlying distributed control system with small
random perturbations. In Section 3, we provide our main result for an
efficient importance sampling estimator of the rare-events involving the
behavior of such a diffusion process. Finally, Section 4 provides some
concluding remarks.

##  2 Problem setup and preliminary results

In this section, we consider the following distributed system, which is formed
by a chain of $n$ subsystems, with small random perturbations, i.e.,

$\displaystyle\left.\begin{array}[]{l}dx_{t}^{\epsilon,1}=f_{1}(t,x_{t}^{\epsilon,1},x_{t}^{\epsilon,2},\ldots,x_{t}^{\epsilon,n})dt+\sqrt{\epsilon}\,\sigma(t,x_{t}^{\epsilon,1},x_{t}^{\epsilon,2},\ldots,x_{t}^{\epsilon,n})dW_{t}\\\
dx_{t}^{\epsilon,2}=f_{2}(t,x_{t}^{\epsilon,1},x_{t}^{\epsilon,2},\ldots,x_{t}^{\epsilon,n})dt\\\
dx_{t}^{\epsilon,3}=f_{3}(t,x_{t}^{\epsilon,2},x_{t}^{\epsilon,3},\ldots,x_{t}^{\epsilon,n})dt\\\
\quad\quad\quad~{}~{}\vdots\\\
dx_{t}^{\epsilon,n}=f_{n}(t,x_{t}^{\epsilon,n-1},x_{t}^{\epsilon,n})dt,~{}\,\text{with}~{}\,(x_{s}^{\epsilon,1},x_{s}^{\epsilon,2},\ldots,x_{s}^{\epsilon,n}),~{}\,0\leq
s\leq t\leq T,\end{array}\right.$ (6)

where

  * -

$x_{\cdot}^{\epsilon,i}$ is an $\mathbb{R}^{d}$-valued diffusion process that
corresponds to the $i$th-subsystem,

  * -

the functions $f_{i}$ are uniformly Lipschitz, with bounded first derivatives,

  * -

$\sigma\colon[0,\infty)\times\mathbb{R}^{nd}\rightarrow\mathbb{R}^{d\times d}$
is Lipschitz with the least eigenvalue of $\sigma\,\sigma^{T}$ uniformly
bounded away from zero, i.e.,

$\displaystyle\sigma(t,x)\,\sigma^{T}(t,x)\geq\lambda I_{d\times
d},\quad\forall x\in\mathbb{R}^{nd},\quad\forall t\geq 0,$

for some $\lambda>0$,

  * -

$W_{\cdot}$ (with $W_{0}=0$) is an $d$-dimensional standard Wiener process,

  * -

$\epsilon$ is a small positive number that represents the level of random
perturbation in the distributed system,

for $i=1,2,\ldots,n$.

Note that, from the physical point of view (e.g., see [19], [21], [2] or [8]),
the functions $f_{i}$, for $i\geq 3$, cannot be dependent on the position
variables $x_{t}^{1},\ldots,x_{t}^{i-1}$ and, as a result of this, the random
perturbation enters only in the first subsystem and then it subsequently
passes through the second subsystem, the third subsystem, and so on to the
$n$th-subsystem. Hence, such a distributed system is described by an
$\mathbb{R}^{nd}$-valued diffusion process, which is degenerate in the sense
that the backward operator associated with it is a degenerate parabolic
equation.

In what follows, let us denote the solution of the stochastic differential
equation (SDE) in (6) by a bold face letter
$\bigl{(}\mathbf{x}_{t}^{\epsilon}\bigr{)}_{t\geq
0}=\bigl{(}x_{t}^{\epsilon,1},x_{t}^{\epsilon,2},\ldots,x_{t}^{\epsilon,n}\bigr{)}_{t\geq
0}$ as an $\mathbb{R}^{nd}$-valued diffusion process and further rewrite the
above SDE as follows

$\displaystyle
d\mathbf{x}_{t}^{\epsilon}=\mathbf{f}(t,\mathbf{x}_{t}^{\epsilon})+\sqrt{\epsilon}\,\mathbf{b}\,\sigma(t,\mathbf{x}_{t}^{\epsilon})\,dW_{t},$
(7)

where $\mathbf{f}=(f_{1},f_{2},\ldots,f_{n})$ is an $\mathbb{R}^{nd}$-valued
function, $\mathbf{b}$ is an $nd\times d$ constant matrix that embeds
$\mathbb{R}^{d}$ into $\mathbb{R}^{nd}$, i.e., $\mathbf{b}=(I_{d\times
d},0,\ldots,0)^{T}$ and, moreover, for
$\mathbf{x}=(x_{1},\,x_{2},\,\ldots,\,x_{n})$, we set
$\mathbf{x}^{i,n}=(x_{i},\,\ldots,\,x_{n})$. Note that the corresponding
backward operator for the diffusion process $\mathbf{x}_{t}^{\epsilon}$, when
applied to a certain function $\upsilon^{\epsilon}(t,\mathbf{x})$, is given by

$\displaystyle\partial_{t}\upsilon^{\epsilon}+\mathcal{L}^{\epsilon}\upsilon\triangleq\frac{\partial\upsilon^{\epsilon}}{\partial
t}+\frac{\epsilon}{2}\operatorname{tr}\Bigl{\\{}a\,\upsilon_{x^{1}x^{1}}^{\epsilon}\Bigr{\\}}+\sum\nolimits_{i=1}^{n}\bigl{\langle}f_{i},\,\upsilon_{x^{i}}^{\epsilon}\bigr{\rangle},$
(8)

where $a(t,\mathbf{x})=\sigma(t,\mathbf{x})\,\sigma^{T}(t,\mathbf{x})$.

Let $\Omega\in\mathbb{R}^{nd}$ be bounded open domains with smooth boundary
(i.e., $\partial\Omega$ is a manifold of class $C^{2}$) and let $\Omega^{T}$
be an open set defined by

$\displaystyle\Omega^{T}=(0,T)\times\Omega.$

Furthermore, let us denote by $C^{\infty}(\Omega^{T})$ the spaces of
infinitely differentiable functions on $\Omega^{T}$ and by
$C_{0}^{\infty}(\Omega^{T})$ the space of the functions $\phi\in
C^{\infty}(\Omega^{T})$ with compact support in $\Omega^{T}$. A locally square
integrable function $\upsilon^{\epsilon}(t,\mathbf{x})$ on $\Omega^{T}$ is
said to be a distribution solution to the following equation

$\displaystyle\partial_{t}\upsilon^{\epsilon}+\mathcal{L}^{\epsilon}\upsilon^{\epsilon}=0,$
(9)

if, for any test function $\phi\in C_{0}^{\infty}(\Omega^{T})$, the following
holds true

$\displaystyle\int_{\Omega^{T}}\left(-\frac{\partial\phi}{\partial
t}+{\mathcal{L}^{\epsilon}}^{\ast}\phi\right)\upsilon^{\epsilon}d\Omega^{T}=0,$
(10)

where $d\Omega^{T}$ denotes the Lebesgue measure on $\mathbb{R}^{nd+1}$ and
${\mathcal{L}^{\epsilon}}^{\ast}$ is an adjoint operator corresponding to the
infinitesimal generator $\mathcal{L}^{\epsilon}$ of the process
$\mathbf{x}_{t}^{\epsilon}$, i.e.,

$\displaystyle{\mathcal{L}^{\epsilon}}^{\ast}\phi=\frac{\epsilon}{2}\sum\nolimits_{j=1}^{d}\sum\nolimits_{m=1}^{d}\bigr{(}a_{j,m}\phi\bigr{)}_{x_{j}^{1}x_{m}^{1}}-\sum\nolimits_{i=1}^{n}\sum\nolimits_{m=1}^{d}\bigl{(}f_{i}\phi\bigr{)}_{x_{m}^{i}}.$
(11)

Moreover, we also assume that the following statements hold for the
distributed system in (6).

######  Assumption 1.

  1. (a)

The function $\mathbf{f}$ is a bounded
$C^{\infty}((0,\infty)\times\Omega)$-function, with bounded first derivatives.
Moreover, $\sigma$ and $\sigma^{-1}$ are bounded
$C^{\infty}\bigl{(}(0,\infty)\times\mathbb{R}^{nd}\bigr{)}$-functions, with
bounded first derivatives.

  2. (b)

The backward operator in (8) is hypoelliptic in
$C^{\infty}((0,\infty)\times\Omega)$ (e.g., see [16] or [9]).

  3. (c)

Let $n(\mathbf{x})$ be the outer normal vector to $\partial\Omega$ and,
further, let $\Gamma^{+}$ and $\Gamma^{0}$ denote the sets of points
$(t,\mathbf{x})$, with $\mathbf{x}\in\partial\Omega$, such that

$\displaystyle\bigl{\langle}\mathbf{f}(t,\mathbf{x}),\,n(\mathbf{x})\bigr{\rangle}$

is positive and zero, respectively.111Note that
$\displaystyle\mathbb{P}_{s,\mathbf{x}_{s}^{\epsilon}}^{\epsilon}\Bigl{\\{}\bigl{(}\tau^{\epsilon},\mathbf{x}_{\tau^{\epsilon}}^{\epsilon}\bigr{)}\in\Gamma^{+}\bigcup\Gamma^{0},\,\,\tau^{\epsilon}<\infty\Bigr{\\}}=1,\quad\forall\bigl{(}s,\mathbf{x}_{s}^{\epsilon}\bigr{)}\in\Omega_{0}^{\infty}.$
where
$\tau^{\epsilon}=\inf\bigl{\\{}t>s\,\bigl{|}\,\mathbf{x}_{t}^{\epsilon}\in\partial\Omega\bigr{\\}}$.
Moreover, if
$\displaystyle\mathbb{P}_{s,\mathbf{x}_{s}^{\epsilon}}^{\epsilon}\Bigl{\\{}\bigl{(}t,\mathbf{x}_{t}^{\epsilon}\Bigr{)}\in\Gamma^{0}~{}\text{for
some}~{}t\in[s,T]\Bigr{\\}}=0,\quad\forall\bigl{(}s,\mathbf{x}_{s}^{\epsilon}\bigr{)}\in\Omega_{0}^{\infty},$
and $\tau^{\epsilon}\leq T$, then we have
$\bigl{(}\tau^{\epsilon},\mathbf{x}_{\tau^{\epsilon}}^{\epsilon}\bigr{)}\in\Gamma^{+}$,
almost surely (see [22, Section 7]).

######  Remark 2.

Here we remark that, in general, the hypoellipticity assumption (i.e., the
backward operator in (8)) is related to a strong accessibility property of
controllable nonlinear systems that are driven by white noise (e.g., see [23]
concerning the controllability of nonlinear systems, which is closely related
to [22] and [17]; see also [9, Section 3]). That is, the hypoellipticity
assumption implies that the diffusion process $\mathbf{x}_{t}^{\epsilon}$ has
a transition probability density with a strong Feller property.

###  2.1 Importance sampling

In this paper, we are mainly concerned with estimating the following quantity

$\displaystyle\mathbb{E}_{s,\mathbf{x}_{s}^{\epsilon}}^{\epsilon}\Bigl{[}\exp\Bigl{(}-\frac{1}{\epsilon}\Phi^{\epsilon}(\mathbf{x}^{\epsilon})\Bigr{)}\Bigr{]},$
(12)

where $\Phi^{\epsilon}$ is an appropriate functional on
$C\bigl{(}[0,T];\mathbb{R}^{nd}\bigr{)}$ and $\mathbf{x}^{\epsilon}$ is a
solution of the SDE in (6) and our analysis is in the situation where the
level of the random perturbation is small, i.e., $\epsilon\ll 1$, and the
functional
$\mathbb{E}_{s,\mathbf{x}_{s}^{\epsilon}}^{\epsilon}\bigl{[}\exp\bigl{(}-\frac{1}{\epsilon}\Phi^{\epsilon}(\mathbf{x}^{\epsilon})\bigr{)}\bigr{]}$
is rapidly varying in $\mathbf{x}^{\epsilon}$. Note that the challenge
presented by such an analysis of rare-event probabilities is well documented
(see [3], [1] and [4] for additional discussions). In the following (and also
in Subsection 2.1 and Section 3), we specifically consider the case when the
functional $\Phi^{\epsilon}$ is bounded and nonnegative Lipschitz, with
$\Phi^{\epsilon}=0$, if $\mathbf{x}_{t}^{\epsilon}\in\Omega^{T}\subset
C([0,T]:\mathbb{R}^{nd})$ and $\Phi^{\epsilon}=\infty$ otherwise; and we
further consider analysis on the asymptotic estimates for exit probabilities
from a given bounded open domain in the small noise limit case.

Consider the following simple estimator for the quantity of interest in (12)

$\displaystyle\rho(\epsilon)=\frac{1}{N}\sum\nolimits_{j=1}^{N}\exp\Bigl{(}-\frac{1}{\epsilon}\Phi^{\epsilon}({\mathbf{x}^{\epsilon}}^{(j)})\Bigr{)},$
(13)

where $\Bigl{\\{}{\mathbf{x}^{\epsilon}}^{(j)}\Bigr{\\}}_{j=1}^{N}$ are
$N$-copies of independent samples of $\mathbf{x}^{\epsilon}$. Here we remark
that such an estimator is unbiased in the sense that

$\displaystyle\mathbb{E}_{s,\mathbf{x}_{s}^{\epsilon}}^{\epsilon}\bigl{[}\rho(\epsilon)\bigr{]}=\mathbb{E}_{s,\mathbf{x}_{s}^{\epsilon}}^{\epsilon}\Bigl{[}\exp\Bigl{(}-\frac{1}{\epsilon}\Phi^{\epsilon}(\mathbf{x}^{\epsilon})\Bigr{)}\Bigr{]},$
(14)

Moreover, its variance is given by

$\displaystyle\operatorname*{Var}\left(\rho(\epsilon)\right)=\frac{1}{N}\left(\mathbb{E}_{s,\mathbf{x}_{s}^{\epsilon}}^{\epsilon}\Bigl{[}\exp\Bigl{(}-\frac{2}{\epsilon}\Phi^{\epsilon}(\mathbf{x}^{\epsilon})\Bigr{)}\Bigr{]}-\mathbb{E}_{s,\mathbf{x}_{s}^{\epsilon}}^{\epsilon}\Bigl{[}\exp\Bigl{(}-\frac{1}{\epsilon}\Phi^{\epsilon}(\mathbf{x}^{\epsilon})\Bigr{)}\Bigr{]}^{2}\right).$
(15)

Then, we have the following for the relative estimation error

$\displaystyle\operatorname*{R_{err}}\left(\rho(\epsilon)\right)=\frac{\sqrt{\operatorname*{Var}\left(\rho(\epsilon)\right)}}{\mathbb{E}_{s,\mathbf{x}_{s}^{\epsilon}}^{\epsilon}\bigl{[}\rho(\epsilon)\bigr{]}}$
(16)

which can be further rewritten as follows

$\displaystyle\operatorname*{R_{err}}\left(\rho(\epsilon)\right)=\bigl{(}1/\sqrt{N}\bigr{)}\sqrt{\Delta\left(\rho(\epsilon)\right)-1},$
(17)

where

$\displaystyle\Delta\left(\rho(\epsilon)\right)=\frac{\mathbb{E}_{s,\mathbf{x}_{s}^{\epsilon}}^{\epsilon}\Bigl{[}\exp\Bigl{(}-\frac{2}{\epsilon}\Phi^{\epsilon}(\mathbf{x}^{\epsilon})\Bigr{)}\Bigr{]}}{\mathbb{E}_{s,\mathbf{x}_{s}^{\epsilon}}^{\epsilon}\Bigl{[}\exp\Bigl{(}-\frac{1}{\epsilon}\Phi^{\epsilon}(\mathbf{x}^{\epsilon})\Bigr{)}\Bigr{]}^{2}}.$
(18)

Note that, as we might expect, the relative estimation error may decrease with
increasing the number of the sample size $N$. However, from Varahhan’s lemma
(e.g., see [25]; see also [26] and [27]), under suitable assumptions, we also
have the following conditions

$\displaystyle\limsup_{\epsilon\rightarrow
0}\epsilon\,\log\mathbb{E}_{s,\mathbf{x}_{s}^{\epsilon}}^{\epsilon}\Bigl{[}\exp\Bigl{(}-\frac{1}{\epsilon}\Phi^{\epsilon}(\mathbf{x}^{\epsilon})\Bigr{)}\Bigr{]}=-\inf_{\begin{subarray}{c}\varphi\in
C_{sT}\bigl{(}[s,T],\mathbb{R}^{nd}\bigr{)}\\\
\varphi(s)=\mathbf{x}_{s}\end{subarray}}\Bigl{\\{}I(\varphi)+\Phi^{\epsilon}(\varphi)\Bigr{\\}}$
(19)

and

$\displaystyle\limsup_{\epsilon\rightarrow
0}\epsilon\,\log\mathbb{E}_{s,\mathbf{x}_{s}^{\epsilon}}^{\epsilon}\Bigl{[}\exp\Bigl{(}-\frac{2}{\epsilon}\Phi^{\epsilon}(\mathbf{x}^{\epsilon})\Bigr{)}\Bigr{]}=-\inf_{\begin{subarray}{c}\varphi\in
C_{sT}\bigl{(}[s,T],\mathbb{R}^{nd}\bigr{)}\\\
\varphi(s)=\mathbf{x}_{s}\end{subarray}}\Bigl{\\{}I(\varphi)+2\Phi^{\epsilon}(\varphi)\Bigr{\\}}$
(20)

where $C_{sT}\bigl{(}[s,T],\mathbb{R}^{nd}\bigr{)}$ is the set of absolutely
continuous functions from $[s,T]$ into $\mathbb{R}^{nd}$, with $0\leq s\leq
t\leq T$, and $I(\varphi)$ is the rate functional for the diffusion process
$\mathbf{x}_{t}^{\epsilon}$. From Jensen’s inequality, the above equations in
(19) and (20) also imply the following condition
$\Delta\left(\rho(\epsilon)\right)\geq 1$.

In the following subsection, i.e., Subsection 2.2 (see also Section 3, the
framework that we use to address rare-event simulation problem basically
relies on the connection between the probability theory of large deviations
(i.e., the asymptotics for exit probabilities) and the values functions for a
family of stochastic control problems associated with the underlying
distributed system. Note that such a connection provides a computational
paradigm – based on an exponentially-tilted biasing distribution – for
constructing an efficient importance sampling estimators for rare-event
simulations that further improves the efficiency of Monte Carlo simulations.

###  2.2 Exit probabilities and stochastic optimal control

Let $\mathbf{x}_{t}^{\epsilon}$, for $0\leq t\leq T$, be the diffusion process
associated with (6) and consider the following boundary value problem

$\displaystyle\left.\begin{array}[]{c}\partial_{s}\upsilon^{\epsilon}+\mathcal{L}^{\epsilon}\upsilon^{\epsilon}=0\quad\text{in}\quad\Omega^{T}\\\
\upsilon^{\epsilon}\bigl{(}s,\mathbf{x}\bigr{)}=1\quad\text{on}\quad\Gamma_{T}^{+}\\\
\upsilon^{\epsilon}\bigl{(}s,\mathbf{x}\bigr{)}=0\quad\text{on}\quad\\{T\\}\times\Omega\end{array}\right\\}$
(24)

where $\mathcal{L}^{\epsilon}$ is the backward operator in (8) and

$\displaystyle\Gamma_{T}^{+}=\Bigl{\\{}\bigl{(}s,\mathbf{x}\bigr{)}\in\Gamma^{+}\,\bigl{|}\,0<s\leq
T\Bigr{\\}}.$

Further, let $\Omega^{0T}$ be the set consisting of
$\Omega^{T}\bigcup\\{T\\}\times\Omega$, together with the boundary points
$\bigl{(}s,\mathbf{x}\bigr{)}\in\Gamma^{+}$, with $0<s<T$. Then, the following
proposition, whose proof is given in [2], provides a solution to the exit
probability
$\mathbb{P}_{s,\mathbf{x}_{s}^{\epsilon}}^{\epsilon}\bigl{\\{}\tau^{\epsilon}\leq
T\bigr{\\}}$ with which the diffusion process $\mathbf{x}_{t}^{\epsilon}$
exits from the domain $\Omega$.

######  Proposition 3.

Suppose that the statements (a)-(c) in the above assumption (i.e., Assumption
1) hold true. Then, the exit probability
$q^{\epsilon}(s,\mathbf{x}^{\epsilon})=\mathbb{P}_{s,\mathbf{x}_{s}^{\epsilon}}^{\epsilon}\bigl{\\{}\tau^{\epsilon}\leq
T\bigr{\\}}$ is a smooth solution to the boundary value problem in (24) and,
moreover, it is a continuous function on $\Omega^{0T}$.

Note that, from Proposition 3, the exit probability
$q^{\epsilon}\bigl{(}s,\mathbf{x}^{\epsilon}\bigr{)}$ is a smooth solution to
the boundary value problem in (24). Further, if we introduce the following
logarithmic transformation (e.g., see [12],[10] or [11])

$\displaystyle
I^{\epsilon}\bigl{(}s,\mathbf{x}^{\epsilon}\bigr{)}=-\epsilon\log
q^{\epsilon}\bigl{(}s,\mathbf{x}^{\epsilon}\bigr{)}.$ (25)

Then, using ideas from stochastic control theory (see [12] for similar
arguments), we present results useful for proving the following asymptotic
property

$\displaystyle I^{\epsilon}\bigl{(}s,\mathbf{x}^{\epsilon}\bigr{)}\rightarrow
I^{0}\bigl{(}s,\mathbf{x}^{\epsilon}\bigr{)}\quad\text{as}\quad\epsilon\rightarrow
0.$ (26)

The starting poin for such an analysis is to introduce a family of related
stochastic control problems whose dynamic programming equation, for
$\epsilon>0$, is given below by (32). Then, this also allows us to reinterpret
the exit probability function as a value function for a family of stochastic
control problems that are associated with the underlying distributed system
with small random perturbation.

In what follows, we consider the following boundary value problem

$\displaystyle\left.\begin{array}[]{c}\partial_{s}g^{\epsilon}+\frac{\epsilon}{2}\operatorname{tr}\Bigl{\\{}a\,g_{x^{1}x^{1}}^{\epsilon}\Bigr{\\}}+\sum\nolimits_{j=1}^{n}\bigl{\langle}f_{j},\,g_{x^{j}}^{\epsilon}\bigr{\rangle}=0\quad\text{in}\quad\Omega^{T}\\\
g^{\epsilon}=\mathbb{E}_{s,\mathbf{x}}^{\epsilon}\Bigl{\\{}\exp\Bigl{(}-\frac{1}{\epsilon}\Phi^{\epsilon}\Bigr{)}\Bigr{\\}}\quad\text{on}\quad\partial^{\ast}\Omega^{T}\end{array}\right\\}$
(29)

where $\Phi^{\epsilon}\bigl{(}s,\mathbf{x}^{\epsilon}\bigr{)}$ is a bounded,
nonnegative Lipschitz function such that

$\displaystyle\Phi^{\epsilon}\bigl{(}s,\mathbf{x}^{\epsilon}\bigr{)}=0,\quad\forall\bigl{(}s,\mathbf{x}^{\epsilon}\bigr{)}\in\Gamma_{T}^{+}.$
(30)

Observe that the function
$g^{\epsilon}\bigl{(}s,\mathbf{x}^{\epsilon}\bigr{)}$ is a smooth solution in
$\Omega^{T}$ to the backward operator in (8); and it is also continuous on
$\partial^{\ast}\Omega^{T}$. Moreover, if we introduce the following logarithm
transformation (cf. Equation (25))

$\displaystyle
J^{\epsilon}\bigl{(}s,\mathbf{x}^{\epsilon}\bigr{)}=-\epsilon\log
g^{\epsilon}\bigl{(}s,\mathbf{x}^{\epsilon}\bigr{)}.$ (31)

Then, $J^{\epsilon}\bigl{(}s,\mathbf{x}^{\epsilon}\bigr{)}$ satisfies the
following dynamic programming equation

$\displaystyle\partial_{s}J^{\epsilon}+\frac{\epsilon}{2}\operatorname{tr}\Bigl{\\{}a\,J_{x^{\epsilon,1}x^{\epsilon,1}}^{\epsilon}\Bigr{\\}}+\sum\nolimits_{j=1}^{n}\bigl{\langle}f_{j},\,J_{x^{\epsilon,j}}^{\epsilon}\bigr{\rangle}+H^{\epsilon}=0,\quad\text{in}\quad\Omega^{T},$
(32)

where
$H^{\epsilon}=H^{\epsilon}\bigl{(}s,\mathbf{x}^{\epsilon},J_{x^{\epsilon,1}}^{\epsilon}\bigr{)}$
is given by

$\displaystyle
H^{\epsilon}\bigl{(}s,\mathbf{x}^{\epsilon},J_{x^{\epsilon,1}}^{\epsilon}\bigr{)}=\bigl{\langle}f_{1}(s,\mathbf{x}^{\epsilon}),\,J_{x^{\epsilon,1}}^{\epsilon}\bigr{\rangle}-\frac{1}{2}\Bigl{(}J_{x^{\epsilon,1}}^{\epsilon}\Bigr{)}^{T}a(s,\mathbf{x}^{\epsilon})J_{x^{\epsilon,1}}^{\epsilon}.$
(33)

Note that the duality relation between
$H^{\epsilon}\bigl{(}s,\mathbf{x}^{\epsilon},\,\cdot\bigr{)}$ and
$L^{\epsilon}\bigl{(}s,\mathbf{x}^{\epsilon},\,\cdot\bigr{)}$, i.e.,

$\displaystyle
H^{\epsilon}\bigl{(}s,\mathbf{x}^{\epsilon},J_{x^{\epsilon,1}}^{\epsilon}\bigr{)}=\inf_{\hat{u}}\biggl{\\{}L^{\epsilon}\bigl{(}s,\mathbf{x}^{\epsilon},\hat{u}\bigr{)}+\bigl{\langle}J_{x^{\epsilon,1}}^{\epsilon},\,\hat{u}\bigr{\rangle}\biggr{\\}},$
(34)

with

$\displaystyle
L^{\epsilon}\bigl{(}s,\mathbf{x}^{\epsilon},\hat{u}\bigr{)}=\frac{1}{2}\Bigl{\|}f_{1}(s,\mathbf{x}^{\epsilon})-\hat{u}\Bigr{\|}_{[a(s,\mathbf{x}^{\epsilon})]^{-1}}^{2},$

where $\|\,\cdot\,\|_{[a(s,\mathbf{x}^{\epsilon})]^{-1}}^{2}$ denotes the
Riemannian norm of a tangent vector.

Then, it is easy to see that
$J^{\epsilon}\bigl{(}s,\mathbf{x}^{\epsilon}\bigr{)}$ is a solution in
$\Omega^{T}$, with $J^{\epsilon}=\Phi^{\epsilon}$ on
$\partial^{\ast}\Omega^{T}$, to the dynamic programming in (32), where the
latter is associated with the following stochastic control problem

$\displaystyle
J^{\epsilon}\bigl{(}s,\mathbf{x}^{\epsilon}\bigr{)}=\inf_{\hat{u}\in\hat{U}(s,\mathbf{x}_{s}^{\epsilon})}\mathbb{E}_{s,\mathbf{x}_{s}^{\epsilon}}\Biggl{\\{}\int_{s}^{\theta}L^{\epsilon}\bigl{(}s,\mathbf{x}^{\epsilon},\hat{u}\bigr{)}dt+\Phi^{\epsilon}\bigl{(}\theta,\mathbf{x}^{\epsilon}\bigr{)}\Biggr{\\}}$
(35)

that corresponds to the following system of SDEs

$\displaystyle\left.\begin{array}[]{l}dx_{t}^{\epsilon,1}=\hat{u}(t)dt+\sqrt{\epsilon}\,\sigma\bigl{(}t,\mathbf{x}^{\epsilon}(t)\bigr{)}dW_{t}\\\
dx_{t}^{\epsilon,2}=f_{2}(t,\mathbf{x}_{t}^{\epsilon})dt\\\
dx_{t}^{\epsilon,3}=f_{3}(t,\mathbf{x}_{t}^{\epsilon,3,n})dt\\\
\quad\quad\quad~{}~{}\vdots\\\
dx_{t}^{\epsilon,n}=f_{n}(t,\mathbf{x}_{t}^{\epsilon,n-1,n})dt\\\ {}\\\
\quad\quad\text{with an initial
condition}\quad\mathbf{x}_{s}^{\epsilon}\end{array}\right.$ (43)

where
$\mathbf{x}_{t}^{\epsilon,i,n}=(x^{\epsilon,i},\,\ldots,\,x^{\epsilon,n})$,
with $i\geq 3$, and $\hat{U}(s,\mathbf{x}^{\epsilon})$ is a class of
continuous functions for which $\theta\leq T$ and
$(\theta,x_{\theta}^{\epsilon})\in\Gamma_{T}^{+}$.

In what follows, we provide bounds (i.e., the asymptotic lower and upper
bounds) on the exit probability
$q^{\epsilon}\bigl{(}s,\mathbf{x}^{\epsilon}\bigr{)}$.

Define

$\displaystyle
I_{\Omega}^{\epsilon}\bigl{(}\bigl{(}s,\mathbf{x}^{\epsilon}\bigr{)};\,\partial\Omega\bigr{)}$
$\displaystyle=$ $\displaystyle-\lim_{\epsilon\rightarrow
0}\epsilon\,\log\mathbb{P}_{s,\mathbf{x}_{s}}^{\epsilon}\bigl{\\{}\mathbf{x}_{\theta}^{\epsilon}\in\partial\Omega\bigl{\\}},$
(44) $\displaystyle\triangleq$ $\displaystyle-\lim_{\epsilon\rightarrow
0}\epsilon\,\log q^{\epsilon}\bigl{(}s,\mathbf{x}^{\epsilon}\bigr{)},$

where $\theta$ (or $\theta=\tau^{\epsilon}\wedge T$) is the first exit-time of
$\mathbf{x}_{t}^{\epsilon}$ from the domain $\Omega$. Furthermore, let us
introduce the following supplementary minimization problem

$\displaystyle\tilde{I}_{\Omega}^{\epsilon}\bigl{(}s,\varphi,\theta\bigr{)}=\inf_{\varphi\in
C_{sT}\bigl{(}[s,T],\mathbb{R}^{d}\bigr{)},\theta\geq
s}\int_{s}^{\theta}L^{\epsilon}\big{(}t,\varphi(t),\dot{\varphi}(t)\big{)}dt,$
(45)

where the infimum is taken among all $\varphi(\cdot)\in
C_{sT}\bigl{(}[s,T],\mathbb{R}^{d}\bigr{)}$ (i.e., from the space of
$\mathbb{R}^{d}$-valued (locally) absolutely continuous functions, with
$\int_{s}^{T}\bigl{|}\dot{\varphi}(t)\bigr{|}^{2}dt<\infty$ for each $T>s$)
and $\theta\geq s>0$ such that $\varphi(s)=x_{s}^{\epsilon,1}$,
$\bigl{(}t,\varphi(t),\mathbf{x}_{t}^{\epsilon,2,n}\bigr{)}\in\Omega^{T}$, for
all $t\in[s,\,\theta)$, and
$\bigl{(}\theta,\varphi(\theta),\mathbf{x}_{\theta}^{\epsilon,2,n}\bigr{)}\in\Gamma_{T}^{+}$.
Then, it is easy to see that

$\displaystyle\tilde{I}_{\Omega}^{\epsilon}\bigl{(}s,\varphi,\theta\bigr{)}=I_{\Omega}^{\epsilon}\bigl{(}\bigl{(}s,\mathbf{x}^{\epsilon}\bigr{)};\,\partial\Omega\bigr{)}.$
(46)

Next, we state the following lemma that will be useful for proving Proposition
6 (cf. [12, Lemma 3.1]).

######  Lemma 4.

If $\varphi\in C_{sT}\bigl{(}[s,T],\mathbb{R}^{d}\bigr{)}$, for $s>0$, and
$\varphi(s)=x_{s}^{\epsilon,1}$,
$\bigl{(}t,\varphi(t),\mathbf{x}_{t}^{\epsilon,2,n}\bigr{)}\in\Omega^{T}$, for
all $t\in[s,T)$, then
$\lim_{T\rightarrow\infty}\int_{s}^{T}L^{\epsilon,\ell}\big{(}t,\varphi(t),\dot{\varphi}(t)\big{)}dt=+\infty$.

Consider again the stochastic control problem in (35) together with (43).
Suppose that $\Phi_{M}^{\epsilon}$ (with $\Phi_{M}^{\epsilon}\geq 0$) is class
$C^{2}$ such that $\Phi_{M}^{\epsilon}\rightarrow+\infty$ as
$M\rightarrow\infty$ uniformly on any compact subset of
$\Omega^{T}\setminus\bar{\Gamma}_{T}^{+}$ and $\Phi_{M}^{\epsilon}$ on
$\Gamma_{T}^{+}$. Further, if we let $J^{\epsilon}=J_{\Phi_{M}}^{\epsilon}$,
when $\Phi^{\epsilon}=\Phi_{M}^{\epsilon}$, then we have the following lemma.

######  Lemma 5.

Suppose that Lemma 4 holds, then we have

$\displaystyle\liminf_{\begin{subarray}{c}M\rightarrow\infty\\\
\bigl{(}t,\mathbf{x}_{t}^{\epsilon}\bigr{)}\rightarrow\bigl{(}s,\mathbf{x}_{s}^{\epsilon}\bigr{)}\end{subarray}}J_{\Phi_{M}}^{\epsilon}(\bigl{(}s,\mathbf{x}^{\epsilon}\bigr{)})\geq
I^{\epsilon}\bigl{(}s,\mathbf{x}^{\epsilon}\bigr{)}.$ (47)

Then, we have the following result.

######  Proposition 6.

Suppose that Lemma 4 holds, then we have

$\displaystyle I^{\epsilon}\bigl{(}s,\mathbf{x}^{\epsilon}\bigr{)}\rightarrow
I^{0}\bigl{(}s,\mathbf{x}^{\epsilon}\bigr{)}\quad\text{as}\quad\epsilon\rightarrow
0,$ (48)

uniformly for all
$\bigl{(}s,x^{\epsilon,1}(s),x^{\epsilon,2}(s),\ldots,x^{\epsilon,\ell}(s)\bigr{)}$
in any compact subset $\bar{\Omega}_{\ell}^{T}$.

###### Proof.

It is suffices to show the following conditions

$\displaystyle\limsup_{\epsilon\rightarrow
0}\epsilon\,\log\mathbb{P}_{s,\mathbf{x}_{s}}^{\epsilon}\Bigl{\\{}\mathbf{x}_{\theta}^{\epsilon}\in\partial\Omega\Bigl{\\}}\leq-
I_{\Omega}^{\epsilon}\bigl{(}\bigl{(}s,\mathbf{x}^{\epsilon}\bigr{)};\,\partial\Omega\bigr{)}$
(49)

and

$\displaystyle\liminf_{\epsilon\rightarrow
0}\epsilon\,\log\mathbb{P}_{s,x_{s}}^{\epsilon}\Bigl{\\{}\mathbf{x}_{\theta}^{\epsilon}\in\partial\Omega\Bigl{\\}}\geq-
I_{\Omega}^{\epsilon}\bigl{(}\bigl{(}s,\mathbf{x}^{\epsilon}\bigr{)};\,\partial\Omega\bigr{)},$
(50)

uniformly for all $\bigl{(}s,\mathbf{x}_{s}^{\epsilon}\bigr{)}$ in any compact
subset $\bar{\Omega}^{T}$.

Note that
$I_{\Omega}^{\epsilon}\bigl{(}\bigl{(}s,\mathbf{x}^{\epsilon}\bigr{)};\,\partial\Omega\bigr{)}=I^{\epsilon}\bigl{(}s,\mathbf{x}^{\epsilon}\bigr{)}$
(cf. Equation (46)), then the upper bound in (49) can be verified using the
Ventcel-Freidlin asymptotic estimates (see [14, pp. 332–334], [27] or [26]).

On the other hand, to prove the lower bound in (50), we introduce a penalty
function $\Phi_{M}^{\epsilon}$ (with
$\Phi_{M}^{\epsilon}\bigl{(}t,\mathbf{y}\bigr{)}=0$ for
$\bigl{(}t,\mathbf{y}\bigr{)}\in\Gamma_{T}^{+}$); and write
$g^{\epsilon}=g_{M}^{\epsilon}$
($\equiv\mathbb{E}_{s,\mathbf{s}}^{\epsilon}\bigl{\\{}\exp\bigl{(}-\frac{1}{\epsilon}\Phi_{M}^{\epsilon}\bigr{)}\bigr{\\}}$)
and $J^{\epsilon}=J_{\Phi_{M}}^{\epsilon}$, with
$\Phi^{\epsilon}=\Phi_{M}^{\epsilon}$. From the boundary condition in (29),
then, for each $M$, we have

$\displaystyle g^{\epsilon}\bigl{(}s,\mathbf{x}^{\epsilon}\bigr{)}\leq
g_{M}^{\epsilon}\bigl{(}s,\mathbf{x}^{\epsilon}\bigr{)}.$ (51)

Using Lemma 5 and noting further the following

$\displaystyle
J_{\Phi_{M}}^{\epsilon}\bigl{(}s,\mathbf{x}^{\epsilon}\bigr{)}\geq
I_{\Omega}^{\epsilon}\bigl{(}\bigl{(}s,\mathbf{x}^{\epsilon}\bigr{)};\,\partial\Omega\bigr{)}.$
(52)

Then, the lower bound in (50) holds uniformly for all
$\bigl{(}s,\mathbf{x}_{s}^{\epsilon}\bigr{)}$ in any compact subset
$\bar{\Omega}^{T}$. This completes the proof of Proposition 6. $\Box$

##  3 Main results

Let $\hat{\mathbf{x}}_{t}^{\epsilon}$ be the solution to the following SDE

$\displaystyle d\hat{\mathbf{x}}_{t}^{\epsilon}$
$\displaystyle=\mathbf{f}(t,\hat{\mathbf{x}}_{t}^{\epsilon})+\mathbf{b}\,\sigma(t,\hat{\mathbf{x}}_{t}^{\epsilon})\,v^{\epsilon}(t,\hat{\mathbf{x}}_{t}^{\epsilon})+\sqrt{\epsilon}\,\mathbf{b}\,\sigma(t,\hat{\mathbf{x}}_{t}^{\epsilon})\,dW_{t},$
$\displaystyle\quad\quad\text{with an initial
condition}\quad\hat{\mathbf{x}}_{s}^{\epsilon}=\mathbf{x}_{s}^{\epsilon},$
(53)

where $v^{\epsilon}$ is an appropriate control function (which also depends on
$\epsilon$) to be chosen so as to reduce the variance of the importance
sampling estimator.

Let

$\displaystyle
z^{\epsilon}=\exp\Bigl{(}-\frac{1}{\sqrt{\epsilon}}\int_{s}^{T}\bigl{\langle}v^{\epsilon}(t,\hat{\mathbf{x}}_{t}^{\epsilon}),\,dW_{t}\bigr{\rangle}-\frac{1}{2\epsilon}\int_{s}^{T}\bigl{|}v^{\epsilon}(t,\hat{\mathbf{x}}_{t}^{\epsilon})\bigr{|}^{2}dt\Bigr{)}.$
(54)

The corresponding importance sampling estimator is then given by

$\displaystyle\hat{\rho}(\epsilon)=\frac{1}{N}\sum\nolimits_{j=1}^{N}\exp\Bigl{(}-\frac{1}{\epsilon}\Phi^{\epsilon}(\hat{\mathbf{x}}^{\epsilon^{(j)}})\Bigr{)}{z^{\epsilon}}^{(j)},$
(55)

where
$\left\\{\bigl{(}\hat{\mathbf{x}}^{\epsilon^{(j)}},{z^{\epsilon}}^{(j)}\bigr{)}\right\\}_{j=1}^{N}$
are $N$-copies of independent samples of
$\bigl{(}\hat{\mathbf{x}}^{\epsilon},z^{\epsilon}\bigr{)}$. Note that, for an
appropriately chosen control function $v^{\epsilon}$, the above importance
sampling estimator in (55) is an unbiased estimator for (13), i.e.,

$\displaystyle\mathbb{E}_{s,\mathbf{x}_{s}^{\epsilon}}^{\epsilon}\bigl{[}\hat{\rho}(\epsilon)\bigr{]}$
$\displaystyle=\mathbb{E}_{s,\mathbf{x}_{s}^{\epsilon}}^{\epsilon}\Bigl{[}\exp\Bigl{(}-\frac{1}{\epsilon}\Phi^{\epsilon}(\mathbf{x}^{\epsilon})\Bigr{)}\Bigr{]}$
$\displaystyle\equiv\mathbb{E}_{s,\mathbf{x}_{s}^{\epsilon}}^{\epsilon}\bigl{[}\rho(\epsilon)\bigr{]}.$
(56)

Moreover, the relative estimation error is given by

$\displaystyle\operatorname*{R_{err}}\left(\hat{\rho}(\epsilon)\right)$
$\displaystyle=\frac{\sqrt{\operatorname*{Var}\left(\hat{\rho}(\epsilon)\right)}}{\mathbb{E}_{s,\mathbf{x}_{s}^{\epsilon}}^{\epsilon}\bigl{[}\hat{\rho}(\epsilon)\bigr{]}}$
(57)

which can be rewritten as follows

$\displaystyle\operatorname*{R_{err}}\left(\hat{\rho}(\epsilon)\right)$
$\displaystyle=\bigl{(}1/\sqrt{N}\bigr{)}\sqrt{\Delta\left(\hat{\rho}(\epsilon)\right)-1},$
(58)

where

$\displaystyle\Delta\left(\hat{\rho}(\epsilon)\right)=\frac{\mathbb{E}_{s,\mathbf{x}_{s}^{\epsilon}}^{\epsilon}\Bigl{[}\exp\Bigl{(}-\frac{2}{\epsilon}\Phi^{\epsilon}(\hat{\mathbf{x}}^{\epsilon})\Bigr{)}\Bigr{]}\bigl{(}z^{\epsilon}\bigr{)}^{2}}{\mathbb{E}_{s,\mathbf{x}_{s}^{\epsilon}}^{\epsilon}\Bigl{[}\exp\Bigl{(}-\frac{1}{\epsilon}\Phi^{\epsilon}(\mathbf{x}^{\epsilon})\Bigr{)}\Bigr{]}^{2}}.$
(59)

Hence, in order to reduce the relative estimation error
$\operatorname*{R_{err}}\left(\hat{\rho}(\epsilon)\right)$, we need to control
the term $\Delta\left(\hat{\rho}(\epsilon)\right)$ in (58). Note that, from
Jensen’s inequality, we have the following condition

$\displaystyle\limsup_{\epsilon\rightarrow
0}-\epsilon\,\log\mathbb{E}_{s,\mathbf{x}_{s}^{\epsilon}}^{\epsilon}\Bigl{[}\exp\Bigl{(}-\frac{2}{\epsilon}\Phi^{\epsilon}(\hat{\mathbf{x}}^{\epsilon})\Bigr{)}\Bigr{]}\leq
2\lim_{\epsilon\rightarrow
0}-\epsilon\,\log\mathbb{E}_{s,\mathbf{x}_{s}^{\epsilon}}^{\epsilon}\Bigl{[}\exp\Bigl{(}-\frac{1}{\epsilon}\Phi^{\epsilon}(\hat{\mathbf{x}}^{\epsilon})\Bigr{)}\Bigr{]}$
(60)

which also implies $\Delta\left(\hat{\rho}(\epsilon)\right)\geq 1$ with
$\lim_{\epsilon\rightarrow 0}\Delta\left(\hat{\rho}(\epsilon)\right)=1$.
Moreover, the statement in (57) further implies the following

$\displaystyle\operatorname*{R_{err}}\left(\hat{\rho}(\epsilon)\right)=\frac{1}{\sqrt{N}}\exp\bigl{(}o(1)/\epsilon\bigr{)}\quad\text{as}\quad\epsilon\rightarrow
0,$

which is generally referred as asymptotic efficiency or optimality. In this
paper, our main objective is to choose appropriately the control function
$v^{\epsilon}$ in (53), so that the resulting importance sampling estimator
achieves a minimum rate of error growth. For this reason, we introduce the
following standard definition from simulation theory (e.g., see [3] or [4])
which is useful for interpreting our result.

######  Definition 7.

An importance sampling estimator of the form (55) is log-efficient (i.e.,
asymptotic efficiency or optimal) if

$\displaystyle\lim_{\epsilon\rightarrow
0}-\epsilon\log\Delta\left(\hat{\rho}(\epsilon)\right)=0.$ (61)

Then, we state our main result as follows.

######  Proposition 8.

Suppose that the importance sampling estimator $\hat{\rho}(\epsilon)$ in (55),
with
$v^{\epsilon}(t,\mathbf{x})=-\sigma^{T}(t,\mathbf{x})J_{x^{\epsilon,1}}^{\epsilon}(t,\mathbf{x})$,
is uniformly log-efficient (i.e., asymptotic efficient), where
$J^{\epsilon}(t,\mathbf{x})$ satisfies the corresponding dynamic programming
equation in $\Omega^{T}$, w.r.t. the system in (53), with
$J^{\epsilon}=\Phi^{\epsilon}$ on $\partial^{\ast}\Omega^{T}$. Then, there
exits a set $\mathbb{A}\subset\mathbb{R}^{nd}$ such that the Hausedorf
dimension of $\mathbb{A}^{c}$ is zero and

$\displaystyle\lim_{\epsilon\rightarrow
0}\operatorname*{R_{err}}\left(\hat{\rho}(\epsilon)\right)=0,$ (62)

for all $x\in\mathbb{A}$.

##  4 Concluding remarks

In this paper, we considered an importance sampling problem for a certain
rare-event simulations involving the behavior of a diffusion process
pertaining to a chain of distributed systems with random perturbations. In
particular, we have provided an efficient importance sampling estimator, with
an exponential variance decay rate, for the asymptotics of the probabilities
of the rare-events involving the behavior of such a diffusion process on
finite time intervals which also ensures a minimum relative estimation error
in the small noise limit. The framework for such an analysis basically relies
on the connection between the probability theory of large deviations and the
values functions for a family of stochastic control problems associated with
the underlying distributed system, where such a connection provides a
computational paradigm – based on an exponentially-tilted biasing distribution
– for constructing efficient importance sampling estimators for the rare-event
simulation. Moreover, as a by-product, the framework also allows us to derive
a family of Hamilton-Jacobi-Bellman for which we also provide a solvability
condition for the corresponding optimal control problem.

## References

  * [1] S. Asmussen and P. W. Glynn, Stochastic simulation: algorithms and analysis, Springer, New York, 2010.
  * [2] G.K. Befekadu and P.J. Antsaklis, On the asymptotic estimates for exit probabilities and minimum exit rates of diffusion processes pertaining to a chain of distributed control systems, SIAM J. Control Optim. 53 (2015), pp. 2297–2318.
  * [3] J.A. Bucklew, Introduction to rare-event simulation, Springer Series in Statistics. Springer, New York, 2004.
  * [4] A. Budhiraja and P. Dupuis, Analysis and approximation of rare events: representations and weak convergence methods, Prob. Theory and Stoch. Modelling Series, 94, Springer, 2019.
  * [5] F. Delarue and S. Menozzi, Density estimates for a random noise propagating through a chain of differential equations, J. Funct. Anal., 259 (2010), pp. 1577–1630.
  * [6] P. Dupuis and R. Ellis, A weak convergence approach to the theory of large deviations, Wiley, New York, 1997.
  * [7] P. Dupuis and H. Wang, Importance sampling, large deviations, and differential games, Stoch. Stoch. Rep. 76 (2004), pp. 481–508.
  * [8] J.P. Eckmann, C.A. Pillet and L. Rey-Bellet, Non-equilibrium statistical mechanics of anharmonic chains coupled to two heat baths at different temperatures, Comm. Math. Phys. 201 (1999), pp. 657–697.
  * [9] D.L. Elliott, Diffusions on manifolds arising from controllable systems, in Geometric Methods in System Theory, D. Q. Mayne and R.W. Brockett, eds. Reidel Publ. Co., Dordrecht, Holland, 1973, pp. 285–294.
  * [10] L.C Evans and H. Ishii, A PDE approach to some asymptotic problems concerning random differential equations with small noise intensities, Ann. Inst. H. Poincaré Anal. Non Linearé, 2 (1985), pp. 1–20.
  * [11] W.H. Fleming and R.W. Rishel, Deterministic and stochastic optimal control, Springer-Verlag, New York, 1975.
  * [12] W.H. Fleming, Exit probabilities and optimal stochastic control, Appl. Math. Optim., 4 (1978), pp. 329–346.
  * [13] M.I. Freidlin and A.D. Wentzell, Random perturbations of dynamical systems, Springer, Berlin, 1984.
  * [14] A. Friedman, Stochastic differential equations and applications, Dover Publisher, Inc., Mineola, New York, 2006.
  * [15] J. Gártner, On large deviations from the invariant measure, Th. Prob. Appl. 22 (1977), pp. 24-39.
  * [16] L. Hörmander, Hypoelliptic second order differential operators, Acta Math. 119 (1967), pp. 147–171.
  * [17] K. Ichihara and H. Kunita, A classification of the second order degenerate elliptic operators and its probabilistic characterization, Z. Wahrscheinlichkeitstheor. Verw. Geb., 30 (1974), pp. 253–254.
  * [18] E.W. Ren and E. Vanden-Eijnden, Minimum action method for the study of rare events, Comm. Pure Appl. Math. 57 (2004), pp. 637–656.
  * [19] L. Rey-Bellet and L.E. Lawrence, Asymptotic behavior of thermal nonequilibrium steady states for a driven chain of anharmonic oscillators, Comm. Math. Phys. 215 (2000), pp. 1–24.
  * [20] D. Siegmund, Importance sampling in the monte carlo study of sequential tests, The Annals of Statistics, (1976), pp. 673–684.
  * [21] C. Soize, The Fokker-Planck equation for stochastic dynamical systems and its explicit steady state solutions, Ser. Adv. Math. Appl. Sci., vol. 17, World Scientific Publishing Co., Inc., River Edge, NJ, 1994.
  * [22] D. Stroock and S.R.S. Varadhan, On degenerate elliptic-parabolic operators of second order and their associated diffusions, Comm. Pure Appl. Math., 25 (1972), pp. 651–713.
  * [23] H.J. Sussmann and V. Jurdjevic, Controllability of nonlinear systems, J. Diff. Equ. 12 (1972), pp. 95–116.
  * [24] E. Vanden-Eijnden and J. Weare, Rare event simulation of small noise diffusions, Comm. Pure Appl. Math. 65 (2012), pp. 1770–1803.
  * [25] S.R.S. Varadhan, Large deviations and applications, CBMS-NSF Regional Conference Series in Applied Mathematics, 46. SIAM, Philadelphia, 1985.
  * [26] A.D. Ventcel, Limit theorems on large deviations for stochastic processes, Theo. Prob. Appl., 18 (1973), pp. 817–821.
  * [27] A.D. Ventcel and M.I. Freidlin, On small random perturbations of dynamical systems, Russian Math. Surv. 25 (1970), pp. 1–55.


the sequence ${(L''_i,R''_i)}_{i<N''}$ given by

\[
\begin{array}{l c l !{\qquad} l c l !{\qquad} l}
& \deq
& L_j
& R''_j
& \deq
& R_j
& \text{(for $j<N$)}
\\
& \deq
& L'_k
& R''_{N+k}
& \deq
& R'_k
& \text{(for $k<N'$)}
\\
\end{array}
\]

Case of $(\ex x \psi)$
Note that we can assume $x \notin V$.
We apply the induction hypothesis on $\psi$ twice:

once with $V \cup\{x\} $ and once with $V$.
This gives sequences
resp. ${(L_j,R_j)}_{j<N}$
For $\ex x \psi$ we take
$N'' \deq N+N'$ and
the sequence ${(L''_i,R''_i)}_{i<N''}$ given by

\[
\begin{array}{l c l !{\qquad} l c l !{\qquad} l}
& \deq
& \ex x L_j
& R''_j
& \deq
& R_j
& \text{(for $j<N$)}
\\
& \deq
& L'_k
& R''_{N+k}
& \deq
& \ex x R'_k
& \text{(for $k<N'$)}
\\
\end{array}
\]

The disjunction is then seen to be equivalent to $\ex x \psi$
by making a case analysis over whether $x \Leq n$ holds.

Case of $(\ex X \psi)$
Let ${(L_j,R_j)}_{j<N}$ be obtained by induction hypothesis on $\psi$.
Then for $\ex X \psi$ we keep the same $N$
and it directly follows from (<ref>) that we can take
the sequence ${(L'_j,R'_j)}_{j<N}$ given by
$L'_j \deq \exists X L_j$ and
$R'_j \deq \exists X R_j$.

Case of $(\lnot \psi)$
By induction hypothesis, we have a
natural number $N$ and two sequences of formulae
${(L_j, R_j)}_{j < N}$
such that
$\psi \longliff
\bigdisj_{j < N}
L_j\restr{[- \Leq n]} \land R_j \restr{[- \Gt n]}$.
Hence all we need to do is to add the negation,
push it through the disjunction and conjunctions using De Morgan laws and
make the disjuncts commute over the conjunction in the obtained formula.

More explicitly (leaving the parameters implicit), we have:

\begin{align*}
\lnot \psi
&\hspace{2ex}\longliff\hspace{2ex} \bigconj\limits_{j < N}
\lnot L_j \restr{[- \Leq n]} \lor \lnot R_j \restr{[- \Gt n]}
\\
&\hspace{2ex}\longliff\hspace{2ex} \bigdisj\limits_{f \in \two^{\{0 , \dots, N - 1 \}}}
{\bigconj\limits_{j \in f^{-1}(0)} \lnot L_j} \restr{[- \Leq n]}
\land {\bigconj\limits_{j \in f^{-1}(1)} \lnot R_j\restr{[- \Gt n]}}
\tag*{\qedhere}
\end{align*}

Note that there is a combinatorial explosion in the case of $\lnot \psi$
in Lem. <ref> since $N_{\lnot \psi} = 2^{N_\psi}$.
It follows that the sizes of the formulae computed
in Lem. <ref> and the subsequent
Thm. <ref> are non-elementary in the size of $\psi$.

§ AUTOMATA FOR ATOMIC FORMULAE (<REF>)

We give below the automaton $\Sing$ (of <ref>)
and automata for the atomic
formulae of Fig. <ref>.
These automata are presented as deterministic Büchi automata
(with accepting states circled).
As uniform automata, each of them has set of moves $\one$.
Note that automata for atomic formulae involving individual variables
do not detect if the corresponding inputs actually represent natural numbers.
This is harmless, since all statements of <ref> actually assume
streams representing natural numbers to be singletons,
and since in Fig. <ref>,
quantifications over individuals are relativized to $\Sing$.

* $\bm{\Sing}$ :

\[
\begin{tikzpicture}[->,node distance=3.5cm,every state/.style={inner sep=2}]
\node[state,initial,initial text=] (A) {$0$} ;
\node[state,accepting] (B) [right of=A] {$1$};
\node[state] (C) [right of=B] {$2$};

\path (A) edge [loop above] node[above, style={font=\footnotesize}] {$0$} (A) ;
\path (A) edge node[above, style={font=\footnotesize}] {$1$} (B) ;
\path (B) edge [loop above] node[above, style={font=\footnotesize}] {$0$} (B) ;
\path (B) edge node[above,style={font=\footnotesize}] {$1$} (C) ;
\path (C) edge [loop right] node[right, style={font=\footnotesize}] {$*$} (C) ;
\end{tikzpicture}
\]

* $\bm{(x_1 \Eq x_2)}$ :

\[
\begin{tikzpicture}[->,node distance=3.5cm,every state/.style={inner sep=2}]
\node[state,accepting,initial,initial text=] (A) {$0$} ;
\node[state] (B) [right of=A] {$1$};

\path (A) edge [loop above] node[above, style={font=\footnotesize}]
{$(i,i)$} (A) ;

\path
(A) edge node[above, style={font=\footnotesize}] {$(i,1-i)$} (B) ;

\path (B) edge [loop right] node[right, style={font=\footnotesize}]
{$(*,*)$} (B) ;
\end{tikzpicture}
\]

* $(x_1 \In X_1)$ :

\[
\begin{tikzpicture}[->,node distance=3.5cm,every state/.style={inner sep=2}]
\node[state,initial,initial text=] (A) {$0$} ;
\node[state,accepting] (B) [right of=A] {$1$};

\path (A) edge [loop above] node[above, style={font=\footnotesize}]
{$(0,*) (1,0)$} (A) ;

\path
(A) edge node[above, style={font=\footnotesize}] {$(1,1)$} (B) ;

\path (B) edge [loop right] node[right, style={font=\footnotesize}]
{$(*,*)$} (B) ;
\end{tikzpicture}
\]

* $(x_1 \Leq x_2)$ :

\[
\begin{tikzpicture}[->,node distance=3.5cm,every state/.style={inner sep=2}]
\node[state,initial,initial text=] (A) {$0$} ;
\node[state] (B) [right of=A] {$1$};
\node[state,accepting] (C) [right of=B] {$2$};

\path (A) edge [loop above] node[above, style={font=\footnotesize}]
{$(0,*)$} (A) ;

\path (A) edge node[above, style={font=\footnotesize}] {$(1,0)$} (B) ;

\path (A) edge[bend right] node[above, style={font=\footnotesize}] {$(1,1)$} (C) ;

\path (B) edge [loop above] node[above, style={font=\footnotesize}]
{$(*,0)$} (B) ;

\path (B) edge node[above,style={font=\footnotesize}] {$(*,1)$} (C) ;

\path (C) edge [loop right] node[right, style={font=\footnotesize}]
{$(*,*)$} (C) ;
\end{tikzpicture}
\]

* $\Succ(x_1,x_2)$ :

\[
\begin{tikzpicture}[->,node distance=2cm,every state/.style={inner sep=2}]
\node[state,initial,initial text=] (A) {$0$} ;
\node (a) [right of=A] {};
\node[state] (B) [above right of=a] {$1$};
\node[state] (C) [below right of=a] {$2$};
\node (d) [below right of=B] {};
\node[state,accepting] (D) [right of=d] {$3$};

\path (A) edge [loop above] node[above, style={font=\footnotesize}]
{$(0,*)$} (A) ;

\path (A) edge node[above, style={font=\footnotesize}] {$(1,0)$} (B) ;

\path (A) edge[right] node[above, style={font=\footnotesize}] {$(1,1)$} (C) ;

\path (B) edge node[above,style={font=\footnotesize}] {$(*,1)$} (D) ;

\path (B) edge node[right, style={font=\footnotesize}] {$(*,0)$} (C) ;

\path (C) edge [loop right] node[right, style={font=\footnotesize}]
{$(*,*)$} (C) ;

\path (D) edge [loop right] node[right, style={font=\footnotesize}]
{$(*,*)$} (D) ;
\end{tikzpicture}
\]

* $\Zero(x_1)$ :

\[
\begin{tikzpicture}[->,node distance=2cm,every state/.style={inner sep=2}]
\node[state,initial,initial text=] (A) {$0$} ;
\node (a) [right of=A] {};
\node[state,accepting] (B) [above right of=a] {$1$};
\node[state] (C) [below right of=a] {$2$};

\path (A) edge node[above, style={font=\footnotesize}] {$1$} (B) ;

\path (A) edge[right] node[above, style={font=\footnotesize}] {$0$} (C) ;

\path (B) edge [loop right] node[right, style={font=\footnotesize}] {$*$} (B) ;

\path (C) edge [loop right] node[right, style={font=\footnotesize}]
{$*$} (C) ;
\end{tikzpicture}
\]

* $\True$ and $\False$:

[->,node distance=3.5cm,every state/.style=inner sep=2,
baseline=(current bounding box.center)]
[state,accepting,initial,initial text=] (A) $0$ ;
(A) edge [loop right] node[right, style=font=] $*$ (A) ;

and        [->,node distance=3.5cm,every state/.style=inner sep=2,
baseline=(current bounding box.center)]
[state,initial,initial text=] (A) $0$ ;
(A) edge [loop right] node[right, style=font=] $*$ (A) ;