Rare Event Simulation in a Dynamical Model Describing the Spread of Traffic Congestions in Urban Network Systems

Abstract

In this chapter, we present a mathematical framework that provides a new insight for understanding the spread of traffic congestions in an urban network system. In particular, we consider a dynamical model, based on the well-known susceptible-infected-recovered (SIR) model from mathematical epidemiology, with small random perturbations, that describes the process of traffic congestion propagation and dissipation in an urban network system. Here, we provide the asymptotic probability estimate based on the Freidlin-Wentzell theory of large deviations for certain rare events that are difficult to observe in the simulation of urban traffic network dynamics. Moreover, the framework provides a computational algorithm for constructing efficient importance sampling estimators for rare event simulations of certain events associated with the spread of traffic congestions in the dynamics of the traffic network.

1. Introduction

In recent years, there have been a number of interesting studies related to modeling the spread of traffic congestion propagation and traffic dissipation in urban network systems (e.g., see [1, 2, 3, 4, 5] in the context of macroscopic traffic model involving traffic flux and traffic density; see [6, 7] in the context of percolation theory; see [8] for results based on machine-learning methods; and see [9, 10] for studies based on queuing theory). In this paper, without attempting to give a literature review, we consider a dynamical model, based on the well-known susceptible-infected-recovered (SIR) model from mathematical epidemiology, with small random perturbation, that describes the spread of traffic congestion propagation and dissipation in an urban network system, i.e.,

$$\begin{array}{l}{\mathit{dc}}^{\epsilon }\left(t\right)=\left(-\mu +\mathit{\beta k}\left(1-r^{\epsilon }\left(t\right)-c^{\epsilon }\left(t\right)\right)\right)c^{\epsilon }\left(t\right)\mathit{dt}\\ +\sqrt{\epsilon }\sqrt{\left(\mu +\mathit{\beta k}\left(1+r^{\epsilon }\left(t\right)+c^{\epsilon }\left(t\right)\right)\right)c^{\epsilon }\left(t\right)}{\mathit{dW}}_1\left(t\right)\end{array}$$E1

$${\mathit{dr}}^{\epsilon }\left(t\right)=\mu r^{\epsilon }\left(t\right)+\sqrt{\epsilon }\sqrt{\mu r^{\epsilon }\left(t\right)}{\mathit{dW}}_2\left(t\right)$$E2

$$\begin{array}{l}{\mathit{df}}^{\epsilon }\left(t\right)=\left(-\mathit{\beta k}\left(1-r^{\epsilon }\left(t\right)-c^{\epsilon }\left(t\right)\right)\right)c^{\epsilon }\left(t\right)\mathit{dt}\\ +\sqrt{\epsilon }\sqrt{\left(\mathit{\beta k}\left(1+r^{\epsilon }\left(t\right)+c^{\epsilon }\left(t\right)\right)\right)c^{\epsilon }\left(t\right)}{\mathit{dW}}_3\left(t\right)\end{array}$$E3

where

• $c^{\epsilon }\left(t\right)$ represents the fraction of congested links in the network

• $r^{\epsilon }\left(t\right)$ represents the fraction of recovered links in the network

• $f^{\epsilon }\left(t\right)$ represents the fraction of free flow links in the network

• the parameters $\beta$ and $\mu$ represent respectively the propagation and recovery rates considering that a certain fraction of congested links will eventually recover as the demand for travel diminishes

• the quantity $\mathit{k\beta }/\mu$ represents the average number of newly congested links that, in a fully freely flowing traffic network, each already congested link can potentially create,

• $W_1\left(t\right)$, $W_2\left(t\right)$ and $W_3\left(t\right)$ are three independent standard (one-dimensional) Wiener processes, and

• $\epsilon$ is a small positive number that represents the level of random perturbation in the network.

Notice that Eq. (1) describes the rate at which the fraction of congested links, i.e., $c^{\epsilon }\left(t\right)$, changes over time given the propagation rate $\beta$ and recovery rate $\mu$ considering that a fraction of congested links will eventually recover as the demand for the travel volume diminishes. Moreover, Eq. (2) describes the rate at which congested links normally recover given the recovery rate $\mu$. Finally, Eq. (3) represents how the fraction of free flow links $f^{\epsilon }\left(t\right)$ in the network changes over time given $c^{\epsilon }\left(t\right)$ and $r^{\epsilon }\left(t\right)$. Note that, for a normalized SIR based traffic network dynamic model, the following mathematical condition $c^{\epsilon }\left(t\right)+r^{\epsilon }\left(t\right)+f^{\epsilon }\left(t\right)=1$ holds true for all $t>0$, where $f^{\epsilon }\left(t\right)$ represents links that have remained in a free flow state starting from $t=0$ (e.g., see Saberi et al. [11] for detailed discussions related to deterministic models).

In this chapter, we provide the asymptotic probability estimate based on the Freidlin-Wentzell theory of large deviations for certain rare events that are difficult to observe in the simulation of urban traffic network dynamics. The framework considered in this study basically relies on the connection between the probability theory of large deviations and that of the values functions for a family of stochastic control problems, where such a connection also provides a desirable computational algorithm for constructing an efficient importance sampling estimator for rare event simulations of certain events associated with the spread of traffic congestions in the dynamics of the traffic network. 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., [12, 13, 14, 15, 16] for additional discussions). The 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 [17, 18, 19] or [13] for detailed discussions). 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 spread of traffic congestions in an urban network system has not been addressed in the context of large deviations and stochastic control arguments in the small noise limit; and it is important because it provides a new insight for understanding the spread of traffic congestions in an urban network system.

This chapter is organized as follows. In Section 2, we provide an asymptotic estimate on the exit probability using the Freidlin-Wentzell theory of large deviations [20] (see also [21], Chapter 4) and the stochastic control arguments from Fleming [22] (see also [23]), where 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 SIR based traffic network dynamic model with small random perturbations. In Section 3, we discuss importance sampling and the necessary background upon which our main results rely. In Section 4, we provide our main results for an efficient importance sampling estimator for rare event simulations of certain events associated with the spread of traffic congestions in the dynamics of the traffic network. Finally, Section 5 provides some concluding remarks.

2. The Freidlin-Wentzell theory

In this section, we briefly review the classical Freidlin-Wentzell theory of large deviations for the stochastic differential equations (SDEs) with small noise terms. In what follows, let us denote the solution of the SDEs in Eqs. (1)–(3) by a bold face letter ${\left({\mathbf{x}}_t^{\epsilon }\right)}_{t\ge 0}={\left(x_t^{\epsilon ,1},x_t^{\epsilon ,2},x_t^{\epsilon ,3}\right)}_{t\ge 0}\triangleq {\left(c^{\epsilon }\left(t\right),r^{\epsilon }\left(t\right),f^{\epsilon }\left(t\right)\right)}_{t\ge 0}$ as an ${\mathbb{R}}^3$-valued diffusion process and rewrite the above equations as follows

$$d{\mathbf{x}}_t^{\epsilon }=\mathbf{f}\left({\mathbf{x}}_t^{\epsilon }\right)\mathit{dt}+\sqrt{\epsilon }\sigma \left({\mathbf{x}}_t^{\epsilon }\right){\mathit{dW}}_t,$$E4

where $\mathbf{f}\left({\mathbf{x}}_t^{\epsilon }\right)={\left[f_1\left({\mathbf{x}}_t^{\epsilon }\right),f_2\left({\mathbf{x}}_t^{\epsilon }\right),f_3\left({\mathbf{x}}_t^{\epsilon }\right)\right]}^T$ with

$$\begin{array}{cc}{f}_1\left(x_t^{\epsilon ,1},x_t^{\epsilon ,2},x_t^{\epsilon ,3}\right)& =\left(-\mu +\mathit{\beta k}\left(1-x_t^{\epsilon ,2}-x_t^{\epsilon ,1}\right)\right)x_t^{\epsilon ,1}\\ f_2\left(x_t^{\epsilon ,1},x_t^{\epsilon ,2},x_t^{\epsilon ,3}\right)& =\mu x_t^{\epsilon ,2}\\ f_3\left(x_t^{\epsilon ,1},x_t^{\epsilon ,2},x_t^{\epsilon ,3}\right)& =\left(-\mathit{\beta k}\left(1-x_t^{\epsilon ,2}-x_t^{\epsilon ,1}\right)\right)x_t^{\epsilon ,1}\end{array}$$E5

and $\sigma \left({\mathbf{x}}_t^{\epsilon }\right)={\left[{\sigma }_1\left({\mathbf{x}}_t^{\epsilon }\right),{\sigma }_2\left({\mathbf{x}}_t^{\epsilon }\right),{\sigma }_3\left({\mathbf{x}}_t^{\epsilon }\right)\right]}^T$ with

$$\begin{array}{cc}{\sigma }_1\left(x_t^{\epsilon ,1},x_t^{\epsilon ,2},x_t^{\epsilon ,3}\right)& =\sqrt{\left(\mu +\mathit{\beta k}\left(1+x_t^{\epsilon ,2}+x_t^{\epsilon ,1}\right)\right)x_t^{\epsilon ,1}}\\ {\sigma }_2\left(x_t^{\epsilon ,1},x_t^{\epsilon ,2},x_t^{\epsilon ,3}\right)& =\sqrt{\mu x_t^{\epsilon ,2}}\\ {\sigma }_3\left(x_t^{\epsilon ,1},x_t^{\epsilon ,2},x_t^{\epsilon ,3}\right)& =\sqrt{\left(\mathit{\beta k}\left(1+x_t^{\epsilon ,2}+x_t^{\epsilon ,1}\right)\right)x_t^{\epsilon ,1}}.\end{array}$$E6

Moreover, $W_t$ is a standard three-dimensional Wiener process. Note that the corresponding backward operator for the diffusion process ${\mathbf{x}}_t^{\epsilon }$, when applied to a certain function ${\upsilon }^{\epsilon }\left(t,\mathbf{x}\right)$, is given by

$${\partial }_t{\upsilon }^{\epsilon }+{\mathcal{L}}^{\epsilon }\upsilon \triangleq \frac{\partial {\upsilon }^{\epsilon }\left(t,\mathbf{x}\right)}{\partial t}+\frac{\epsilon }{2}\sum _{i,j=1}^3{a}_{i,j}\left(\mathbf{x}\right)\frac{{\partial }^2{\upsilon }^{\epsilon }\left(t,\mathbf{x}\right)}{\partial x^i\partial x^j}+\mathbf{f}\left(\mathbf{x}\right)\cdot {\nabla }_{\mathbf{x}}{\upsilon }^{\epsilon }\left(t,\mathbf{x}\right),$$E7

where $a\left(\mathbf{x}\right)=\sigma \left(\mathbf{x}\right){\sigma }^T\left(\mathbf{x}\right)$.

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

$${\mathrm{\Omega }}^T=\left(0,T\right)\times \mathrm{\Omega }.$$E8

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

$${\partial }_t{\upsilon }^{\epsilon }+{\mathcal{L}}^{\epsilon }{\upsilon }^{\epsilon }=0,$$E9

if, for any test function $\varphi \in C_0^{\infty }\left({\mathrm{\Omega }}^T\right)$, the following holds true

$${\int }_{{\mathrm{\Omega }}^T}\left(-{\partial }_t\varphi +{\mathcal{L}}^{\epsilon \ast }\varphi \right){\upsilon }^{\epsilon }d{\mathrm{\Omega }}^T=0,$$E10

where $d{\mathrm{\Omega }}^T$ denotes the Lebesgue measure on ${\mathbb{R}}^3\times {\mathbb{R}}_{+}$ and ${\mathcal{L}}^{\epsilon \ast }$ is an adjoint operator corresponding to the infinitesimal generator ${\mathcal{L}}^{\epsilon }$ of the process ${\mathbf{x}}_t^{\epsilon }$.

Moreover, we also assume that the following statements hold for the SDE in (4).

Assumption 1

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

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

$$⟨\mathbf{f}\left(t,\mathbf{x}\right),n\left(\mathbf{x}\right)⟩$$E11

is positive and zero, respectively.

Remark 1Note that

$${\mathbb{P}}_{s,{\mathbf{x}}_s^{\epsilon }}^{\epsilon }\left\{\left({\tau }^{\epsilon },{\mathbf{x}}_{{\tau }^{\epsilon }}^{\epsilon }\right)\in {\mathrm{\Gamma }}^{+}\bigcup {\mathrm{\Gamma }}^0,{\tau }^{\epsilon }<\infty \right\}=1,\forall \left(s,{\mathbf{x}}_s^{\epsilon }\right)\in {\mathrm{\Omega }}_0^{\infty }.$$E12

where ${\tau }^{\epsilon }=inf\left\{t>s|{\mathbf{x}}_t^{\epsilon }\in \mathrm{\partial \Omega }\right\}$. Moreover, if

$${\mathbb{P}}_{s,{\mathbf{x}}_s^{\epsilon }}^{\epsilon }\left\{\left(t,{\mathbf{x}}_t^{\epsilon }\right)\in {\mathrm{\Gamma }}^0\text{for\hspace{0.17em}some}t\in \left[s,T\right]\right\}=0,\forall \left(s,{\mathbf{x}}_s^{\epsilon }\right)\in {\mathrm{\Omega }}_0^{\infty },$$E13

and ${\tau }^{\epsilon }\le T$, then we have $\left({\tau }^{\epsilon },{\mathbf{x}}_{{\tau }^{\epsilon }}^{\epsilon }\right)\in {\mathrm{\Gamma }}^{+}$, almost surely (see [24], Section 7).

In what follows, let ${\mathbf{x}}_t^{\epsilon }$, for $0\le t\le T$, be the diffusion process associated with (4) (or Eqs. (1)–(3)) and consider the following boundary value problem

$$\left.\begin{array}{c}{\partial }_s{\upsilon }^{\epsilon }+{\mathcal{L}}^{\epsilon }{\upsilon }^{\epsilon }=0\text{in}{\mathrm{\Omega }}^T\\ {\upsilon }^{\epsilon }\left(s,\mathbf{x}\right)=1\mathrm{on}{\mathrm{\Gamma }}_T^{+}\\ {\upsilon }^{\epsilon }\left(s,\mathbf{x}\right)=0\mathrm{on}\left\{T\right\}\times \mathrm{\Omega }\end{array}\right\}$$E14

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

$${\mathrm{\Gamma }}_T^{+}=\left\{\left(s,\mathbf{x}\right)\in {\mathrm{\Gamma }}^{+}|0<s\le T\right\}.$$E15

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

Proposition 1 Suppose that the statements in Assumption 1 hold true. Then, the exit probability $q^{\epsilon }\left(s,{\mathbf{x}}^{\epsilon }\right)={\mathbb{P}}_{s,{\mathbf{x}}_s^{\epsilon }}^{\epsilon }\left\{{\tau }^{\epsilon }\le T\right\}$ is a smooth solution to the boundary value problem in (14) and, moreover, it is a continuous function on ${\mathrm{\Omega }}^{0T}$.

Note that, from Proposition 1, the exit probability $q^{\epsilon }\left(s,{\mathbf{x}}^{\epsilon }\right)$ is a smooth solution to the boundary value problem in (14). Further, if we introduce the following logarithmic transformation (e.g., see [22, 26] or [23])

$$I^{\epsilon }\left(s,{\mathbf{x}}^{\epsilon }\right)=-\epsilon log{q}^{\epsilon }\left(s,{\mathbf{x}}^{\epsilon }\right).$$E16

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

$$I^{\epsilon }\left(s,{\mathbf{x}}^{\epsilon }\right)\to I^0\left(s,{\mathbf{x}}^{\epsilon }\right)\mathrm{as}\epsilon \to 0.$$E17

The starting point 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 (21). Then, this also allows us to reinterpret the exit probability function as a value function for a family of stochastic control problems associated with the underlying urban traffic network dynamics with small random perturbation. Moreover, as discussed later in Section 5, 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.

Then, we consider the following boundary value problem

$$\left.\begin{array}{c}{\partial }_s{g}^{\epsilon }+\frac{\epsilon }{2}{\mathcal{L}}^{\epsilon }=0\text{in}{\mathrm{\Omega }}^T\\ g^{\epsilon }={\mathbb{E}}_{s,\mathbf{x}}^{\epsilon }\left\{exp\left(-\frac{1}{\epsilon }{\mathrm{\Phi }}^{\epsilon }\right)\right\}\mathrm{on}{\partial }^{\ast }{\mathrm{\Omega }}^T\end{array}\right\}$$E18

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

$${\mathrm{\Phi }}^{\epsilon }\left(s,{\mathbf{x}}^{\epsilon }\right)=0,\forall \left(s,{\mathbf{x}}^{\epsilon }\right)\in {\mathrm{\Gamma }}_T^{+}.$$E19

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

$$J^{\epsilon }\left(s,{\mathbf{x}}^{\epsilon }\right)=-\epsilon log{g}^{\epsilon }\left(s,{\mathbf{x}}^{\epsilon }\right).$$E20

Then, $J^{\epsilon }\left(s,{\mathbf{x}}^{\epsilon }\right)$ satisfies the following dynamic programming equation (i.e., the Hamilton-Jacobi-Bellman equation)

$${\partial }_s{J}^{\epsilon }+\frac{\epsilon }{2}\sum _{i,j=1}^3{a}_{i,j}\frac{{\partial }^2{J}^{\epsilon }}{\partial x^i\partial x^j}+H^{\epsilon }=0,\text{in}{\mathrm{\Omega }}^T,$$E21

where $H^{\epsilon }=H^{\epsilon }\left(s,{\mathbf{x}}^{\epsilon },{\nabla }_{\mathbf{x}}{J}^{\epsilon }\right)$ is given by

$$H^{\epsilon }\left(s,{\mathbf{x}}^{\epsilon },{\nabla }_{\mathbf{x}}{J}^{\epsilon }\right)=\mathbf{f}\left({\mathbf{x}}^{\epsilon }\right)\cdot {\nabla }_{\mathbf{x}}{J}^{\epsilon }\left(s,{\mathbf{x}}^{\epsilon }\right)-\frac{1}{2}{\left({\nabla }_{\mathbf{x}}{J}^{\epsilon }\left(s,{\mathbf{x}}^{\epsilon }\right)\right)}^{T}a\left({\mathbf{x}}^{\epsilon }\right){\nabla }_{\mathbf{x}}{J}^{\epsilon }\left(s,{\mathbf{x}}^{\epsilon }\right).$$E22

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

$$H^{\epsilon }\left(s,{\mathbf{x}}^{\epsilon },{\nabla }_{\mathbf{x}}{J}^{\epsilon }\right)=\underset{\widehat{u}}{inf}\left\{L^{\epsilon }\left(s,{\mathbf{x}}^{\epsilon },\widehat{u}\right)+{\nabla }_{\mathbf{x}}{J}^{\epsilon }\cdot \widehat{u}⟩\right\},$$E23

with

$$L^{\epsilon }\left(s,{\mathbf{x}}^{\epsilon },\widehat{u}\right)=\frac{1}{2}{‖\mathbf{f}\left({\mathbf{x}}^{\epsilon }\right)-\widehat{u}‖}_{{\left[a\left({\mathbf{x}}^{\epsilon }\right)\right]}^{-1}}^2,$$E24

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

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

$$J^{\epsilon }\left(s,{\mathbf{x}}^{\epsilon }\right)=\underset{\widehat{u}\in \widehat{U}\left(s,{\mathbf{x}}_s^{\epsilon }\right)}{inf}{\mathbb{E}}_{s,{\mathbf{x}}_s^{\epsilon }}\left\{{\int }_s^{\theta }{L}^{\epsilon }\left(s,{\mathbf{x}}^{\epsilon },\widehat{u}\right)\mathit{dt}+{\mathrm{\Phi }}^{\epsilon }(\theta ,{\mathbf{x}}^{\epsilon })\right\}$$E25

that corresponds to the following system of SDEs

$$d{\mathbf{x}}_t^{\epsilon }=\widehat{u}\left(t\right)\mathit{dt}+\sqrt{\epsilon }\sigma \left({\mathbf{x}}_t^{\epsilon }\right){\mathit{dW}}_t,$$E26

with an initial condition ${\mathbf{x}}_s^{\epsilon }={\mathbf{x}}^{\epsilon }$ and $\widehat{U}\left(s,{\mathbf{x}}^{\epsilon }\right)$ is a class of continuous functions for which $\theta \le T$ and $\left(\theta ,x_{\theta }^{\epsilon }\right)\in {\mathrm{\Gamma }}_T^{+}$.

Next, we provide bounds, i.e., the asymptotic lower and upper bounds, on the exit probability $q^{\epsilon }\left(s,{\mathbf{x}}^{\epsilon }\right)$.

Define

$$\begin{array}{cc}{I}_{\mathrm{\Omega }}^{\epsilon }\left(\left(s,{\mathbf{x}}^{\epsilon }\right);\mathrm{\partial \Omega }\right)& =-\underset{\epsilon \to 0}{lim}\epsilon log{\mathbb{P}}_{s,{\mathbf{x}}_s^{\epsilon }}^{\epsilon }\left\{{\mathbf{x}}_{\theta }^{\epsilon }\in \mathrm{\partial \Omega }\right\},\\ & \triangleq -\underset{\epsilon \to 0}{lim}\epsilon log{q}^{\epsilon }\left(s,{\mathbf{x}}^{\epsilon }\right),\end{array}$$E27

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

$${\tilde{I}}_{\mathrm{\Omega }}^{\epsilon }\left(s,\phi ,\theta \right)=\underset{\phi \in C_{\mathit{sT}}\left(\left[s,T\right],{\mathbb{R}}^3\right),\theta \ge s}{inf}{\int }_s^{\theta }{L}^{\epsilon }\left(t,\phi \left(t\right),\dot{\phi }\left(t\right)\right)\mathit{dt},$$E28

where the infimum is taken among all $\phi \left(\cdot \right)\in C_{\mathit{sT}}\left(\left[s,T\right],{\mathbb{R}}^3\right)$ (i.e., from the space of ${\mathbb{R}}^d$-valued locally absolutely continuous functions, with ${\int }_s^T{\left|\dot{\phi }\left(t\right)\right|}^2\mathit{dt}<\infty$ for each $T>s$) and $\theta \ge s>0$ such that $\phi \left(s\right)\in {\mathrm{\Omega }}^T$, for all $t\in \left[s,\theta \right)$, and $\left(\theta ,\phi \left(\theta \right)\right)\in {\mathrm{\Gamma }}_T^{+}$. Then, it is easy to see that

$${\tilde{I}}_{\mathrm{\Omega }}^{\epsilon }\left(s,\phi ,\theta \right)=I_{\mathrm{\Omega }}^{\epsilon }\left(\left(s,{\mathbf{x}}^{\epsilon }\right);\mathrm{\partial \Omega }\right).$$E29

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

Lemma 1 If $\phi \in C_{\mathit{sT}}\left(\left[s,T\right],{\mathbb{R}}^3\right)$, for $s>0$, and $\phi \left(s\right)={\mathbf{x}}_s^{\epsilon }$, $\left(t,\phi \left(t\right)\right)\in {\mathrm{\Omega }}^T$, for all $t\in \left[s,T\right)$, then ${lim}_{T\to \infty }{\int }_s^T{L}^{\epsilon }\left(t,\phi \left(t\right),\dot{\phi }\left(t\right)\right)\mathit{dt}=+\infty$.

Consider again the stochastic control problem in (25) together with (26). Suppose that ${\mathrm{\Phi }}_M^{\epsilon }$ (with ${\mathrm{\Phi }}_M^{\epsilon }\ge 0$) is class $C^2$ such that ${\mathrm{\Phi }}_M^{\epsilon }\to +\infty$ as $M\to \infty$ uniformly on any compact subset of ${\mathrm{\Omega }}^T\backslash {\overline{\mathrm{\Gamma }}}_T^{+}$ and ${\mathrm{\Phi }}_M^{\epsilon }$ on ${\mathrm{\Gamma }}_T^{+}$. Further, if we let $J^{\epsilon }=J_{{\mathrm{\Phi }}_M}^{\epsilon }$, when ${\mathrm{\Phi }}^{\epsilon }={\mathrm{\Phi }}_M^{\epsilon }$, then we have the following lemma.

Lemma 2 Suppose that Lemma 1 holds, then we have

$$\underset{\begin{array}{c}M\to \infty \\ \left(t,{\mathbf{x}}_t^{\epsilon }\right)\to \left(s,{\mathbf{x}}_s^{\epsilon }\right)\end{array}}{liminf}{J}_{{\mathrm{\Phi }}_M}^{\epsilon }\left(\left(s,{\mathbf{x}}^{\epsilon }\right)\right)\ge I^{\epsilon }\left(s,{\mathbf{x}}^{\epsilon }\right).$$E30

Then, we have the following result.

Proposition 2 [25, Proposition 2.8] Suppose that Lemma 1 holds, then we have

$$I^{\epsilon }\left(s,{\mathbf{x}}^{\epsilon }\right)\to I^0\left(s,{\mathbf{x}}^{\epsilon }\right)\mathrm{as}\epsilon \to 0,$$E31

uniformly for all $\left(s,{\mathbf{x}}_s^{\epsilon }\right)$ in any compact subset ${\overline{\mathrm{\Omega }}}^T$.

Proof: It is suffices to show the following conditions

$$\underset{\epsilon \to 0}{limsup}\epsilon log{\mathbb{P}}_{s,{\mathbf{x}}_s^{\epsilon }}^{\epsilon }\left\{{\mathbf{x}}_{\theta }^{\epsilon }\in \mathrm{\partial \Omega }\right\}\le -I_{\mathrm{\Omega }}^{\epsilon }\left(\left(s,{\mathbf{x}}^{\epsilon }\right);\mathrm{\partial \Omega }\right)$$E32

and

$$\underset{\epsilon \to 0}{liminf}\epsilon log{\mathbb{P}}_{s,{\mathbf{x}}_s^{\epsilon }}^{\epsilon }\left\{{\mathbf{x}}_{\theta }^{\epsilon }\in \mathrm{\partial \Omega }\right\}\ge -I_{\mathrm{\Omega }}^{\epsilon }\left(\left(s,{\mathbf{x}}^{\epsilon }\right);\mathrm{\partial \Omega }\right),$$E33

uniformly for all $\left(s,{\mathbf{x}}_s^{\epsilon }\right)$ in any compact subset ${\overline{\mathrm{\Omega }}}^T$. Note that $I_{\mathrm{\Omega }}^{\epsilon }\left(\left(s,{\mathbf{x}}^{\epsilon }\right);\mathrm{\partial \Omega }\right)=I^{\epsilon }\left(s,{\mathbf{x}}^{\epsilon }\right)$ (cf. Eq. (29)), then the upper bound in (32) can be verified using the Freidlin-Wentzell asymptotic estimates (e.g., see [27], pp. 332–334, [20] or [28]).

On the other hand, to prove the lower bound in (33), we introduce a penalty function ${\mathrm{\Phi }}_M^{\epsilon }$ (with ${\mathrm{\Phi }}_M^{\epsilon }\left(t,\mathbf{y}\right)=0$ for $\left(t,\mathbf{y}\right)\in {\mathrm{\Gamma }}_T^{+}$); and write $g^{\epsilon }=g_M^{\epsilon }$ ($\equiv {\mathbb{E}}_{s,{\mathbf{x}}_s^{\epsilon }}^{\epsilon }\left\{exp\left(-\frac{1}{\epsilon }{\mathrm{\Phi }}_M^{\epsilon }\right)\right\}$) and $J^{\epsilon }=J_{{\mathrm{\Phi }}_M}^{\epsilon }$, with ${\mathrm{\Phi }}^{\epsilon }={\mathrm{\Phi }}_M^{\epsilon }$. From the boundary condition in (18), then, for each $M$, we have

$$g^{\epsilon }\left(s,{\mathbf{x}}^{\epsilon }\right)\le g_M^{\epsilon }\left(s,{\mathbf{x}}^{\epsilon }\right).$$E34

Using Lemma 2 and noting further the following

$$J_{{\mathrm{\Phi }}_M}^{\epsilon }\left(s,{\mathbf{x}}^{\epsilon }\right)\ge I_{\mathrm{\Omega }}^{\epsilon }\left(\left(s,{\mathbf{x}}^{\epsilon }\right);\mathrm{\partial \Omega }\right).$$E35

Then, the lower bound in (33) holds uniformly for all $\left(s,{\mathbf{x}}_s^{\epsilon }\right)$ in any compact subset ${\overline{\mathrm{\Omega }}}^T$. This completes the proof of Proposition 2.$\square$

3. Importance sampling

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

$${\mathbb{E}}_{s,{\mathbf{x}}_s^{\epsilon }}^{\epsilon }\left[exp\left(-\frac{1}{\epsilon }{\mathrm{\Phi }}^{\epsilon }\left({\mathbf{x}}^{\epsilon }\right)\right)\right],$$E36

where ${\mathrm{\Phi }}^{\epsilon }$ is an appropriate functional on $C\left(\left[0,T\right];{\mathbb{R}}^3\right)$ and ${\mathbf{x}}^{\epsilon }$ is a solution of the SDE in (4) 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 }\left[exp\left(-\frac{1}{\epsilon }{\mathrm{\Phi }}^{\epsilon }\left({\mathbf{x}}^{\epsilon }\right)\right)\right]$ is rapidly varying in ${\mathbf{x}}^{\epsilon }$. Note that the challenge presented by such an analysis of rare event probabilities is well documented (see [12, 18, 29] for additional discussions). In the following (and see also Section 4), we specifically consider the case when the functional ${\mathrm{\Phi }}^{\epsilon }$ is bounded and nonnegative Lipschitz, with ${\mathrm{\Phi }}^{\epsilon }=0$, if ${\mathbf{x}}_t^{\epsilon }\in {\mathrm{\Omega }}^T\subset C\left(\left[0,T\right]:{\mathbb{R}}^3\right)$ and ${\mathrm{\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 (36)

$$\rho \left(\epsilon \right)=\frac{1}{N}\sum _{j=1}^{N}exp\left(-\frac{1}{\epsilon }{\mathrm{\Phi }}^{\epsilon }\left({\mathbf{x}}^{\epsilon \left(j\right)}\right)\right),$$E37

where ${\left\{{\mathbf{x}}^{\epsilon \left(j\right)}\right\}}_{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

$${\mathbb{E}}_{s,{\mathbf{x}}_s^{\epsilon }}^{\epsilon }\left[\rho \left(\epsilon \right)\right]={\mathbb{E}}_{s,{\mathbf{x}}_s^{\epsilon }}^{\epsilon }\left[exp\left(-\frac{1}{\epsilon }{\mathrm{\Phi }}^{\epsilon }\left({\mathbf{x}}^{\epsilon }\right)\right)\right],$$E38

Moreover, its variance is given by

$$\mathrm{Var}\left(\rho \left(\epsilon \right)\right)=\frac{1}{N}\left({\mathbb{E}}_{s,{\mathbf{x}}_s^{\epsilon }}^{\epsilon }\left[exp\left(-\frac{2}{\epsilon }{\mathrm{\Phi }}^{\epsilon }\left({\mathbf{x}}^{\epsilon }\right)\right)\right]-{\mathbb{E}}_{s,{\mathbf{x}}_s^{\epsilon }}^{\epsilon }{\left[exp\left(-\frac{1}{\epsilon }{\mathrm{\Phi }}^{\epsilon }\left({\mathbf{x}}^{\epsilon }\right)\right)\right]}^2\right).$$E39

Then, we have the following for the relative estimation error

$$R_{\mathrm{err}}\left(\rho \left(\epsilon \right)\right)=\frac{\sqrt{\mathrm{Var}\left(\rho \left(\epsilon \right)\right)}}{{\mathbb{E}}_{s,{\mathbf{x}}_s^{\epsilon }}^{\epsilon }\left[\rho \left(\epsilon \right)\right]}$$E40

which can be further rewritten as follows

$$R_{\mathrm{err}}\left(\rho \left(\epsilon \right)\right)=\left(1/\sqrt{N}\right)\sqrt{\mathrm{\Delta }\left(\rho \left(\epsilon \right)\right)-1},$$E41

where

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

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 [30]; see also [20, 28]), under suitable assumptions, we also have the following conditions

$$\underset{\epsilon \to 0}{limsup}\epsilon log{\mathbb{E}}_{s,{\mathbf{x}}_s^{\epsilon }}^{\epsilon }\left[exp\left(-\frac{1}{\epsilon }{\mathrm{\Phi }}^{\epsilon }\left({\mathbf{x}}^{\epsilon }\right)\right)\right]=-\underset{\begin{array}{c}\phi \in C_{\mathit{sT}}\left(\left[s,T\right],{\mathbb{R}}^{\mathit{nd}}\right)\\ \phi \left(s\right)={\mathbf{x}}_s\end{array}}{inf}\left\{I\left(\phi \right)+{\mathrm{\Phi }}^{\epsilon }\left(\phi \right)\right\}$$E43

and

$$\underset{\epsilon \to 0}{limsup}\epsilon log{\mathbb{E}}_{s,{\mathbf{x}}_s^{\epsilon }}^{\epsilon }\left[exp\left(-\frac{2}{\epsilon }{\mathrm{\Phi }}^{\epsilon }\left({\mathbf{x}}^{\epsilon }\right)\right)\right]=-\underset{\begin{array}{c}\phi \in C_{\mathit{sT}}\left(\left[s,T\right],{\mathbb{R}}^{\mathit{nd}}\right)\\ \phi \left(s\right)={\mathbf{x}}_s\end{array}}{inf}\left\{I\left(\phi \right)+2{\mathrm{\Phi }}^{\epsilon }\left(\phi \right)\right\}$$E44

where $C_{\mathit{sT}}\left(\left[s,T\right],{\mathbb{R}}^3\right)$ is the set of absolutely continuous functions from $\left[s,T\right]$ into ${\mathbb{R}}^3$, with $0\le s\le t\le T$, and $I\left(\phi \right)$ is the rate functional for the diffusion process ${\mathbf{x}}_t^{\epsilon }$. From Jensen’s inequality, the above equations in (43) and (44) also imply the following condition $\mathrm{\Delta }\left(\rho \left(\epsilon \right)\right)\ge 1$.

4. Main results

In this section, we present our main result that asserts the relative error decreases to zero as the small random perturbation tends to zero, which in turn implies the uniform log-efficiency for the estimation problem in (36).

In what follows, let ${\widehat{\mathbf{x}}}_t^{\epsilon }$ be the solution to the following SDE

$$\begin{array}{l}d{\widehat{\mathbf{x}}}_t^{\epsilon }=\mathbf{f}\left(t,{\widehat{\mathbf{x}}}_t^{\epsilon }\right)\mathit{dt}+\mathbf{b}\sigma \left(t,{\widehat{\mathbf{x}}}_t^{\epsilon }\right)v^{\epsilon }\left(t,{\widehat{\mathbf{x}}}_t^{\epsilon }\right)\mathit{dt}+\sqrt{\epsilon }\mathbf{b}\sigma \left(t,{\widehat{\mathbf{x}}}_t^{\epsilon }\right){\mathit{dW}}_t,\\ \text{with\hspace{0.17em}an\hspace{0.17em}initial\hspace{0.17em}condition}{\widehat{\mathbf{x}}}_s^{\epsilon }={\mathbf{x}}_s^{\epsilon },\end{array}$$E45

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

$$z^{\epsilon }=exp\left(-\frac{1}{\sqrt{\epsilon }}{\int }_s^T⟨v^{\epsilon }\left(t,{\widehat{\mathbf{x}}}_t^{\epsilon }\right),{\mathit{dW}}_t⟩-\frac{1}{2\epsilon }{\int }_s^T{\left|v^{\epsilon }(t,{\widehat{\mathbf{x}}}_t^{\epsilon })\right|}^2\mathit{dt}\right).$$E46

Then, the corresponding importance sampling estimator is given by

$$\widehat{\rho }\left(\epsilon \right)=\frac{1}{N}\sum _{j=1}^{N}exp\left(-\frac{1}{\epsilon }{\mathrm{\Phi }}^{\epsilon }\left({\widehat{\mathbf{x}}}^{{\epsilon }^{\left(j\right)}}\right)\right)z^{\epsilon \left(j\right)},$$E47

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

$$\begin{array}{cc}{\mathbb{E}}_{s,{\mathbf{x}}_s^{\epsilon }}^{\epsilon }\left[\widehat{\rho }\left(\epsilon \right)\right]& ={\mathbb{E}}_{s,{\mathbf{x}}_s^{\epsilon }}^{\epsilon }\left[exp\left(-\frac{1}{\epsilon }{\mathrm{\Phi }}^{\epsilon }\left({\mathbf{x}}^{\epsilon }\right)\right)\right]\\ & \equiv {\mathbb{E}}_{s,{\mathbf{x}}_s^{\epsilon }}^{\epsilon }\left[\rho \left(\epsilon \right)\right].\end{array}$$E48

Moreover, the relative estimation error is given by

$${\mathrm{R}}_{\mathrm{err}}\left(\widehat{\rho }\left(\epsilon \right)\right)=\frac{\sqrt{\mathrm{Var}\left(\widehat{\rho }\left(\epsilon \right)\right)}}{{\mathbb{E}}_{s,{\mathbf{x}}_s^{\epsilon }}^{\epsilon }\left[\widehat{\rho }\left(\epsilon \right)\right]}$$E49

which can be rewritten as follows

$${\mathrm{R}}_{\mathrm{err}}\left(\widehat{\rho }\left(\epsilon \right)\right)=\left(1/\sqrt{N}\right)\sqrt{\mathrm{\Delta }\left(\widehat{\rho }\left(\epsilon \right)\right)-1},$$E50

where

$$\mathrm{\Delta }\left(\widehat{\rho }\left(\epsilon \right)\right)=\frac{{\mathbb{E}}_{s,{\mathbf{x}}_s^{\epsilon }}^{\epsilon }\left[exp\left(-\frac{2}{\epsilon }{\mathrm{\Phi }}^{\epsilon }\left({\widehat{\mathbf{x}}}^{\epsilon }\right)\right)\right]{\left(z^{\epsilon }\right)}^2}{{\mathbb{E}}_{s,{\mathbf{x}}_s^{\epsilon }}^{\epsilon }{\left[exp\left(-\frac{1}{\epsilon }{\mathrm{\Phi }}^{\epsilon }\left({\mathbf{x}}^{\epsilon }\right)\right)\right]}^2}.$$E51

Hence, in order to reduce the relative estimation error ${\mathrm{R}}_{\mathrm{err}}\left(\widehat{\rho }\left(\epsilon \right)\right)$, we need to control the term $\mathrm{\Delta }\left(\widehat{\rho }\left(\epsilon \right)\right)$ in (50). Note that, from Jensen’s inequality, we have the following condition

$$\underset{\epsilon \to 0}{limsup}-\epsilon log{\mathbb{E}}_{s,{\mathbf{x}}_s^{\epsilon }}^{\epsilon }\left[exp\left(-\frac{2}{\epsilon }{\mathrm{\Phi }}^{\epsilon }\left({\widehat{\mathbf{x}}}^{\epsilon }\right)\right)\right]\le 2\underset{\epsilon \to 0}{lim}-\epsilon log{\mathbb{E}}_{s,{\mathbf{x}}_s^{\epsilon }}^{\epsilon }\left[exp\left(-\frac{1}{\epsilon }{\mathrm{\Phi }}^{\epsilon }\left({\widehat{\mathbf{x}}}^{\epsilon }\right)\right)\right]$$E52

which also implies $\mathrm{\Delta }\left(\widehat{\rho }\left(\epsilon \right)\right)\ge 1$ with ${lim}_{\epsilon \to 0}\mathrm{\Delta }\left(\widehat{\rho }\left(\epsilon \right)\right)=1$. Moreover, the statement in (49) further implies the following

$${\mathrm{R}}_{\mathrm{err}}\left(\widehat{\rho }\left(\epsilon \right)\right)=\frac{1}{\sqrt{N}}exp\left(o\left(1\right)/\epsilon \right)\mathrm{as}\epsilon \to 0,$$E53

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 (45), 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 [29] or [12]) which is useful for interpreting our main result.

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

$$\underset{\epsilon \to 0}{lim}-\epsilon log\mathrm{\Delta }\left(\widehat{\rho }\left(\epsilon \right)\right)=0.$$E54

Then, we state the following result as follows.

Proposition 3 Suppose that the importance sampling estimator $\widehat{\rho }\left(\epsilon \right)$ in (47), with $v^{\epsilon }\left(t,\mathbf{x}\right)=-{\sigma }^T\left(\mathbf{x}\right){\nabla }_{\mathbf{x}}{J}^{\epsilon }\left(t,\mathbf{x}\right)$, is uniformly log-efficient (i.e., asymptotic efficient), where $J^{\epsilon }\left(t,\mathbf{x}\right)$ satisfies the corresponding dynamic programming equation in ${\mathrm{\Omega }}^T$ with respect to the system in (45), with $J^{\epsilon }={\mathrm{\Phi }}^{\epsilon }$ on ${\partial }^{\ast }{\mathrm{\Omega }}^T$. Then, there exits a set $\mathbb{A}\subset {\mathbb{R}}^3$ such that the Hausedorf dimension of ${\mathbb{A}}^c$ is zero and

$$\underset{\epsilon \to 0}{lim}{R}_{\mathrm{err}}\left(\widehat{\rho }\left(\epsilon \right)\right)=0,$$E55

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

Proof: The above proposition basically asserts that the relative error ${\mathrm{R}}_{\mathrm{err}}\left(\widehat{\rho }\left(\epsilon \right)\right)$ decreases to zero as the small random perturbation level $\epsilon$ tends to zero. Note that, if $J^{\epsilon }\left(s,{\mathbf{x}}^{\epsilon }\right)$ satisfies the dynamic programming equation in (21), then, with $v^{\epsilon }\left(t,\mathbf{x}\right)=-{\sigma }^T\left(\mathbf{x}\right){\nabla }_{\mathbf{x}}{J}^{\epsilon }\left(t,\mathbf{x}\right)$, the importance sampling for the estimation problem in (36), i.e., ${\mathbb{E}}_{s,{\mathbf{x}}_s^{\epsilon }}^{\epsilon }\left[exp\left(-\frac{1}{\epsilon }{\mathrm{\Phi }}^{\epsilon }\left({\mathbf{x}}^{\epsilon }\right)\right)\right]$, is uniformly log-efficient if the point $\left(s,{\mathbf{x}}_s^{\epsilon }\right)$ is contained in a region of sufficient regularity that encompasses almost all ${\mathbb{R}}^3$. As a result of this, it only suffices to show that

$$\underset{\epsilon \to 0}{lim}\frac{{\mathbb{E}}_{s,{\mathbf{x}}_s^{\epsilon }}^{\epsilon }\left[exp\left(-\frac{2}{\epsilon }{\mathrm{\Phi }}^{\epsilon }\left({\widehat{\mathbf{x}}}^{\epsilon }\right)\right){\left(z^{\epsilon }\right)}^2\right]}{{\mathbb{E}}_{s,{\mathbf{x}}_s^{\epsilon }}^{\epsilon }{\left[exp\left(-\frac{1}{\epsilon }{\mathrm{\Phi }}^{\epsilon }\left({\mathbf{x}}^{\epsilon }\right)\right)\right]}^2}=1$$E56

holds uniformly for all $\left(s,{\mathbf{x}}_s^{\epsilon }\right)$ in any compact subset ${\overline{\mathrm{\Omega }}}^T$.

Let us define following two functions

$${\psi }_1^{\epsilon }\left(s,{\mathbf{x}}_s^{\epsilon }\right)=-\epsilon log{\mathbb{E}}_{s,{\mathbf{x}}_s^{\epsilon }}^{\epsilon }\left[exp\left(-\frac{2}{\epsilon }{\mathrm{\Phi }}^{\epsilon }\left({\widehat{\mathbf{x}}}^{\epsilon }\right)\right)\right]$$E57

and

$$\begin{array}{l}{\psi }_2^{\epsilon }\left(s,{\mathbf{x}}_s^{\epsilon }\right)=-\epsilon log{\mathbb{E}}_{s,{\mathbf{x}}_s^{\epsilon }}^{\epsilon }\left[exp\left(-\frac{2}{\epsilon }{\mathrm{\Phi }}^{\epsilon }\left({\widehat{\mathbf{x}}}^{\epsilon }\right)\right){\left(z^{\epsilon }\right)}^2\right]\\ =-\epsilon log{\mathbb{E}}_{s,{\mathbf{x}}_s^{\epsilon }}^{\epsilon }\left[exp\left(-\frac{2}{\epsilon }{\mathrm{\Phi }}^{\epsilon }\left({\widehat{\mathbf{x}}}^{\epsilon }\right)-\frac{2}{\sqrt{\epsilon }}{\int }_s^T⟨v^{\epsilon }(t,{\widehat{\mathbf{x}}}_t^{\epsilon }),{\mathit{dW}}_t⟩\right.\right.\\ \left.\left.-\frac{1}{\epsilon }{\int }_s^T{\left|v^{\epsilon }\left(t,{\widehat{\mathbf{x}}}_t^{\epsilon }\right)\right|}^2\mathit{dt}\right)\right].\end{array}$$E58

Note that, from the large deviations results for the diffusion process ${\widehat{\mathbf{x}}}_t^{\epsilon }$ (e.g., see [21], Chapter 4, [30] or [27], pp.332–334; and see also the asymptotic estimates in Proposition 2 of Section 3), then there exists a constant $C$, $\gamma >0$ and ${\epsilon }_0$, with $\epsilon \in \left(0,{\epsilon }_0\right)$, such that

$$\begin{array}{l}{\mathbb{E}}_{0,{\mathbf{x}}_0^{\epsilon }}^{\epsilon }\left[exp\left(-\frac{1}{\epsilon }({\psi }_2^{\epsilon }\left({\widehat{\tau }}^{\epsilon },{\widehat{\mathbf{x}}}_{{\widehat{\tau }}^{\epsilon }}^{\epsilon }\right)-2{\psi }_1^{\epsilon }({\widehat{\tau }}^{\epsilon },{\widehat{\mathbf{x}}}_{{\widehat{\tau }}^{\epsilon }}^{\epsilon }\left)\right)-{\int }_0^{{\widehat{\tau }}^{\epsilon }}\sum _{i,j=1}^3{a}_{i,j}\left({\mathbf{x}}_s^{\epsilon }\right)\frac{{\partial }^2{{\psi }_1}^{\epsilon }\left(s,{\widehat{\mathbf{x}}}_s^{\epsilon }\right)}{\partial x^i\partial x^j}\mathit{ds}\right)\right]\\ \le Cexp\left(-\gamma /2\epsilon \right),\end{array}$$E59

where ${\widehat{\tau }}^{\epsilon }=inf\left\{t>s|{\widehat{\mathbf{x}}}_t^{\epsilon }\in \mathrm{\partial \Omega }\right\}\wedge T$. Note that the above relation further implies that

$$\underset{\epsilon \to 0}{lim}exp\left(-\frac{1}{\epsilon }({\psi }_2^{\epsilon }\left(0,{\mathbf{x}}_0\right)-2{\psi }_1^0(0,{\mathbf{x}}_0\left)\right)\right)=exp\left({\int }_0^T\sum _{i,j=1}^3{a}_{i,j}\left({\mathbf{x}}_s^{\epsilon }\right)\frac{{\partial }^2{{\psi }_1}^{\epsilon }\left(s,{\widehat{\mathbf{x}}}_s^{\epsilon }\right)}{\partial x^i\partial x^j}\mathit{ds}\right).$$E60

Moreover, in the same way, we can also show the following relation

$$\underset{\epsilon \to 0}{lim}exp\left(-\frac{1}{\epsilon }({\psi }_1^{\epsilon }\left(0,{\mathbf{x}}_0\right)-{\psi }_1^0(0,{\mathbf{x}}_0\left)\right)\right)=exp\left({\int }_0^T\sum _{i,j=1}^3{a}_{i,j}\left({\mathbf{x}}_s^{\epsilon }\right)\frac{{\partial }^2{{\psi }_1}^{\epsilon }\left(s,{\widehat{\mathbf{x}}}_s^{\epsilon }\right)}{\partial x^i\partial x^j}\mathit{ds}\right).$$E61

Finally, if we combine the above two equations, then we have the condition following

$$\underset{\epsilon \to 0}{lim}exp\left(-\frac{1}{\epsilon }({\psi }_2^{\epsilon }\left(0,{\mathbf{x}}_0\right)-{\psi }_1^{\epsilon }(0,{\mathbf{x}}_0\left)\right)\right)=1,$$E62

which implies the uniform log-efficiency for the estimation problem in (36). This completes the proof of Proposition 3.

Remark 2 The above proposition basically ensures a minimum relative estimation error in the small noise limit case for the estimation problem in (36). Note that, if $J^{\epsilon }\left(t,{\mathbf{x}}^{\epsilon }\right)$ satisfies the dynamic programming equation in (21) (i.e., if it is the solution for the family of stochastic control problems that are associated with the underlying distributed system with small random perturbation). Then, with $v^{\epsilon }\left(t,\mathbf{x}\right)=-{\sigma }^T\left(\mathbf{x}\right){\nabla }_{\mathbf{x}}{J}^{\epsilon }\left(t,\mathbf{x}\right)$, one can provide a numerical computational framework for constructing efficient importance sampling estimators, with an exponential variance decay rate − based on an exponentially-tilted biasing distribution – for rare-event simulations involving the behavior of the diffusion process ${\mathbf{x}}^{\epsilon }$.

Remark 3 Here, our primary intent is to provide a theoretical framework, rather than considering some specific numerical simulation results with respect to system parameters (such as the propagation rate $\beta$ and recovery rate $\mu$ of the network), which is an ongoing research area.

5. Concluding remarks

In this chapter, we presented a mathematical framework that provides a new insight for understanding the spread of traffic congestions in an urban network system. In particular, we considered a dynamical model, based on the well-known susceptible-infected-recovered (SIR) model from mathematical epidemiology, with small random perturbations, that describes the process of traffic congestion propagation and dissipation in an urban network system. Moreover, we also provided the asymptotic probability estimate based on the Freidlin-Wentzell theory of large deviations for certain rare events that are difficult to observe in the simulation of an urban traffic network dynamic, where such a framework provides a computational algorithm for constructing efficient importance sampling estimators for rare event simulations of certain events associated with the spread of traffic congestions in the traffic network.