Explicit Solutions for Variational Problems in the Quadrant.
We study a variational problem (VP) that is related to semimartingale reflecting Brownian motions (SRBMs). Specifically, this VP appears in the large deviations analysis of the stationary distribution of SRBMs in the d-dimensional orthant Rd+. When d&equals;2, we provide an explicit analytical solution to the VP. This solution gives an appealing characterization of the optimal path to a given point in the quadrant and also provides an explicit expression for the optimal value of the VP. For each boundary of the quadrant, we construct a cone of boundary influence, which determines the nature of optimal paths in different regions of the quadrant. In addition to providing a complete solution in the 2-dimensional case, our analysis provides several results which may be used in analyzing the VP in higher dimensions and more general state spaces.
Introduction
Semimartingale reflecting Brownian motions (SRBMs) in the orthant have
been proposed as approximate models of open queueing networks (see e.g, Harrison
and Nguyen [16]). Such di#usion processes were first introduced in Harrison
and Reiman [17]. Since then, there have been two primary lines of active research
s
related to SRBMs. One line has concentrated on proving limit theorems that justify
the Brownian model approximations of queueing networks under heavy tra#c
conditions. (For recent surveys, see Chen and Mandelbaum [7] and Williams [37].)
The other focus has been to study the fundamental and analytical properties, including
recurrence conditions, of SRBMs. (For a survey, see Williams [36].) The
topic of this paper is related to the latter category.
The focus of our paper is a variational problem (VP) which arises from
the study of SRBMs. The rare event behavior of the stationary distributions of
SRBMs can be analyzed with the help of a large deviations principle (LDP). When
such a principle holds, the optimal value of the VP describes the tail behavior of
the stationary distribution and the corresponding optimal paths characterize how
certain rare events are most likely to occur. Below, we provide some motivation
both for studying the stationary distributions of SRBMs and in particular for
examining the rare event behavior.
The stationary distribution of SRBMs has been a primary object of study
because it provides estimates of congestion measures in corresponding queueing
networks. Unfortunately, even these Brownian approximations are not immediately
tractable. In fact, Harrison and Williams [18,19] showed that the stationary
density function admits a separable, exponential density if and only if the covariance
and reflection matrices satisfy a certain skew-symmetry condition. When
this condition is not satisfied, one must generally resort to developing numerical
algorithms to estimate the stationary distribution of the SRBM. One such
algorithm has been devised by Dai and Harrison [8]. If one knows the tail behavior
of the stationary distribution for the SRBMs, such algorithms can be made
to be more e#cient. Furthermore, in a recent paper of Majewski [27] it was
demonstrated that, roughly speaking, one may switch the heavy tra#c and large
deviations limits in feed-forward networks, indicating that the rare event behavior
of an SRBM can give insight into the rare event behavior of an associated
heavily loaded queueing network. This provides ample motivation for studying
the large deviations theory of SRBMs.
The study of LDPs can be roughly divided into two primary topics: (i) proving
that an LDP holds for a class of processes and (ii) analyzing the variational
problem which arises from the LDP. Our study is concerned only with the second
topic, but we provide some discussion of the first topic, both here and in the body
of the paper, since there is a close relationship between the two. As noted above,
the VPs studied in this paper are related to the stationary distribution of an
SRBM. Thus, the LDP corresponds to SRBM on the entire time interval [0, #).
When considering LDPs on a finite time interval, the large deviations principle
is easier to establish. For example, when the reflection matrix is an M-matrix,
as the one used in Harrison and Reiman [17], the SRBM can be defined through
a reflection mapping which is Lipschitz continuous on [0, T ] for each T > 0. In
this case, the LDP for the SRBM readily follows from the Contraction Principle
of large deviations theory, as demonstrated in Dupuis and Ishii [12]. To investigate
large deviations theory for the stationary distribution of an SRBM, we must
consider SRBMs on the interval [0, #), which complicates matters considerably.
However, LDP for SRBMs of this type have been established in special cases.
In particular, Majewski has established such an LDP for a stationary SRBM
when the reflection matrix R is an M-matrix [28] and when the reflection matrix
has a special structure arising from feed-forward queueing networks [26]. For a
general stationary SRBM, establishing an LDP remains an open problem (see
Conjecture 4.1), even in two dimensions.
The major thrust of this paper is to investigate the VP which arises for
the aforementioned LDPs. Our analysis provides a complete, explicit solution
to the VP when the state space is the 2-dimensional orthant R 2
. In particular,
we characterize the optimal paths to a given point v # R 2
. It turns out that
the optimal path to v is influenced by a boundary if v is contained within a
cone associated with that boundary. We identify precisely each of these "cones
of boundary influence." When v is not in either of the cones, the optimal path
is a direct, linear path. When v is contained in one of these cones, however,
the optimal path first travels along a boundary, and then travels directly to v.
Furthermore, such a path leaves the boundary and enters the interior at a unique
entrance angle which can be determined directly from the problem data. For VPs
which arise from a large deviations analysis of random walks in the quadrant,
Ignatyuk, Malyshev, and Scherbakov [21] demonstrated that similar behavior is
manifested in the optimal paths. Specifically, they are able to identify analogous
regions of boundary influence in the solutions to such VPs.
Another work closely related to our study is Majewski [28]. In this paper,
Majewski examines a general class VPs in high dimensions and among other
things, provides a general purpose numerical algorithm to solve these VPs. Our
work complements his numerical work for the 2-dimensional case. Also, a crucial
assumption in implementing such numerical algorithms is that the optimal path
consists of a finite number of linear pieces. An intermediate result in our paper
s
shows that an optimal path, in two dimensions, consists of at most two linear
pieces.
It seems clear from the literature (see, e.g. Atar and Dupuis [1]) that explicitly
characterizing the solution to VPs which arise from queueing networks
or other systems is significantly harder in three dimensions or higher versus the
2-dimensional case. Although this paper primarily focuses on the 2-dimensional
problem in R 2
should be noted that several of our results indeed hold in
higher dimensions and for general polygonal state spaces. In addition to this
more direct connection to higher dimensional problems, we hope that the problem
framework which we establish in the SRBM setting will provide motivation
for further research into the interesting and challenging open problems beyond
the 2-dimensional case.
There is a large body of literature on LDPs for random walks and queueing
networks. The book [33] by Shwartz and Weiss contains an excellent list of
references. We can only provide a short survey of the latest works which are most
closely related to our study. Recent work on LDPs for queueing networks include
O'Connell [30,31] and Dupuis and Ramanan [13] on multi-bu#er single-server
systems, Bertsimas, Paschalidis and Tsitsiklis [4] on acyclic networks, Kie#er [22]
on 2-station networks with feedback, and Dupuis and Ellis [10] and Atar and
Dupuis [1] on general queueing networks with feedback. The works by Ignatyuk,
Malyshev and Scherbakov [21] and by Borovkov and Mogulskii [5] investigate
random walks that are constrained to an orthant. Knessl and Tier [24,23,25]
used a perturbation approach to study rate functions for some queueing systems.
We now provide a brief outline of the paper. In Section 2, we introduce the
Skorohod problem and the VP. The main result of this paper (Theorem 3.1) is
stated in Section 3. In Section 4 we introduce semimartingale reflecting Brownian
motions and the large deviations principle that connects the VP with the SRBM.
We examine the VP in depth in Section 5 and characterize the optimal escape
paths in Section 6. Finally, we provide some examples in Section 7.
2. The Skorohod and Variational Problems
Let d # 1 be an integer. Throughout this paper, # is a constant vector in
R d , # is a d - d symmetric and strictly positive definite matrix, and R is a d - d
matrix. In this section, we first define the Skorohod problem associated with the
matrix R, and then define the variational problem (VP) associated with (#, R).
2.1. The Skorohod Problem
Let C([0, #),R d ) be the set of continuous functions x
R d . A function x # C([0, #),R d ) is called a path and is sometimes denoted by
x(-). The space C([0, #),R d ) is endowed with a topology in which convergence
means uniform convergence in each finite interval.
We now define the Skorohod problem associated with R and state space R d
(sometimes called an R-regulation). Note that all vector inequalities should be
interpreted componentwise and all vectors are assumed to be column vectors.
Definition 2.1 (The Skorohod Problem) Let x be a path. An R-regulation
of x is a pair of paths (z, y) # C([0, #),R d ) - C([0, #),R d ) such that
y(-) is non-decreasing,
When the R-regulation (y, z) of x is unique for each x # C([0, #),R d ), the
mapping
is called the reflection mapping from C([0, #),R d ) to C([0, #),R d
When the
R-regulation of x is not unique, we use #(x) to denote the set of all z which are
components of an R-regulation (y, z) of x. When the triple (x, y, z) is used, it is
implicitly assumed that (y, z) is an R-regulation of x.
Bernard and El Kharroubi [3] proved that there exists an R-regulation for
every x with only if R is completely-S as defined in Definition 2.2
below. For a d-d matrix R and a subset D # {1, . , d}, the principal submatrix
associated with D is the |D| - |D| matrix obtained from R by deleting the rows
and columns that are not in D, where |D| is the cardinality of D.
Definition 2.2 A d-d matrix R is said to be an S-matrix if there exists a u # 0
such that Ru > 0. The matrix R is completely-S if each principal submatrix of
R is an S-matrix.
2.2. The Variational Problem
In this section we introduce the variational problem (VP) of interest to us.
This problem arises in the study of large deviations for semimartingale reflecting
Brownian motions (SRBMs) to be defined in Section 4, and we will make this
connection in Section 4.2.
Recall that #(x) maps x to one unique path, if the corresponding Skorohod
problem has a unique solution. If the Skorohod problem is non-unique, then #(x)
represents a set of paths corresponding to x. Now, in order to establish a general
framework for posing VPs, we wish to include cases for which the Skorohod
problem is not unique. For T > 0 and v # R d
, we will adopt the following
convention. We will take
to signify that there exists a z #(x) such that z(T v. Next, for vectors
v # R d and w # R d we define the inner product
with the associated norm
We are now prepared to present the VP that will be the main focus of this
paper.
Definition 2.3 (The Variational Problem - VP)
x#H d ,#(x)(T )=v2 # T|| -
where H d is the space of all absolutely continuous functions x(-)
which have square integrable derivatives on bounded intervals and have
Definition 2.4 Let v # R d
. If a given triple of paths (x, y, z) is such that the
triple satisfies the Skorohod problem, z(T
then we will call (x, y, z) an optimal triple, for VP (2.5), with optimal value I(v).
The function x is called an optimal path if it is the first member of an optimal
triple and z is called an optimal reflected path if it is the last member of an
optimal triple. Such a triple (x, y, z) is also sometimes referred to as a solution
to the VP (2.5).
3. 2-Dimensional Results
In this section, we state our main theorem, which gives an explicit solution
to the VP in terms of the problem data, (#, R), for the 2-dimensional case. We
introduce much of the notation in this section, but defer the proof until Section
6. The proof relies on three components:
1. A reduction of the search for optimal paths to the space of piecewise linear
functions with at most two segments.
2. An analysis of "locally" optimal paths with a given structure.
3. A quantitative comparison of the VP value for the various types of locally
optimal paths to determine the globally optimal path.
It turns out that the solution to the VP in two dimensions can be stated in an
appealing way by defining "cones of boundary influence." Both this solution and
the proof method yield insights into higher dimensional VPs.
For the majority of this section, we restrict ourselves to the case 2. We
will use the term face F i , to denote one of the axes in R 2
We retain the term face because in later sections we will consider faces of the
orthant in higher dimensions. To state our main theorem, we need to define
the cone C i associated with a face F i , 2. For a face F i , each cone C i
defines a region of boundary influence on the solutions to the VP. It turns out
that the boundary influence depends on two quantities which we will term the
"exit velocity" and the "entrance velocity," which will lead to the concept of
"reflectivity" of a face. We define and discuss the relationship between these
terms presently.
Let p i be a vector that is orthogonal (under the usual Euclidean inner
product) to the ith column of the reflection matrix R, and is normalized with
1. For example, if
will be a multiple of (-r 1 , 1) # and p 2 will be a multiple of (1, -r 2 ) # .
s
Definition 3.1 The exit velocity a i associated with face F i is defined to be
a
We defer the explanation of this term until later in the section.
Definition 3.2 Face F i is said to be reflective if the ith component of a i is
negative, i.e., a i
When F i is not reflective, C i is defined to be empty. In this case, the face
F i has no boundary influence on solutions to the VP for any v # R 2
.
When F i is reflective, the characterization of the cone C i is more involved.
We need to define a key notion, the "entrance velocity" associated with face F i .
It is defined to be the "symmetry" of a i around face F i . To make this concept
precise, let e i be a directional vector on face F i , and n i be a vector that is normal
to F i , pointing to the interior of the state space. We assume that e i and n i are
normalized so that ||e i
1. For example, when
have . One can check that #e i , #n i
Thus, e i and #n i form an orthonormal basis in R 2 under the inner product #.
Therefore, any vector v # R 2 has the following (unique) representation
Thus,
a
One can then define a symmetry -
a i of a i around face F i to be
Definition 3.3 We call the symmetry - a i the entrance velocity associated with a
face F i .
One can easily check from the definition that
- a i
thus F i is reflective if and only if - a i
When F i is reflective, C i is defined to be the cone generated by e i and - a i ,
namely,
It is possible that - a i points to the outside of R 2
, even if F i is reflective. In this
case,
.
The cone C i identifies precisely the region in which the face F i has boundary
influence. With two cones, C 1 and C 2 , defined, we can partition the state space
into three regions: (R 2
and one of the two regions,
that one of the latter two regions is always
empty, namely, either R 2
Before we state the main theorem of this paper, we introduce some additional
notation and terminology. For a v # R 2
a (||#||/||v||)v. The next two
expressions will appear in the locally optimal value of the VP for various cases.
For v # R 2
I
I
2. (3.7)
Now we wish to define three triples, which start at
the origin and terminate at v. In will turn out that one or more of these triples
will be a solution to the VP. The first triple, direct triple to v,
with x 0
, the corresponding
reflected path z an R-regulation of x for
any R. One can more generally define a direct triple from w to v. The next two
triples, are broken triples through the corresponding face. For
a face F 1 , we introduce a broken triple from the origin to v through
face F 1 , which consists of two segments. Each segment of x 1 is linear, and hence
we can chose linear y 1 and z 1 , within each segment. In the first segment, x 1 has
a velocity a 1 such that z 1 stays on the boundary F 1 . The segment ends when z 1
reaches
uniquely determined by the condition that v - v 1
is parallel to - a 1 . The second segment is simply the direct triple traveling in the
interior of the state space from v 1 to v, with velocity of x 1 and z 1 being equal to
- a 1 . A broken triple through F 2 is defined similarly.
Note that in order for such a broken triple to be well-defined, we must have
(i) that F 1 is reflective and (ii) that v # C 1 (see Figure 1). In such a case, a 1 is the
velocity at which x exits the state space, and - a 1 is the velocity of x when z enters
a 1

Figure

1. An optimal broken path to v # C1 through F1
the interior of the state space. The terms exit velocity and entrance velocity are
introduced primarily to define these broken triples, although the interpretations
above are not always meaningful when a face is non-reflective.
Now we are prepared to state our main theorem, which completely characterizes
the solutions to the VP presented in the previous section, for the 2-
dimensional case.
Theorem 3.1. Consider the VP as defined in (2.5) with associated data
(#, R), with R taking the form in (3.1). Let v # R 2
and suppose that R
is completely-S and that the data satisfies the conditions
where, for an a # R, a
(a) If v # C 1 # C 2 , the optimal value is given by I 0 (v) and the direct triple
(b) If v # C 1 \ C 2 , the optimal value is given by I 1 (v) and the broken triple
(c) If v # C 2 \ C 1 , the optimal value is given by I 2 (v) and the broken triple
(d) If v # C 1 # C 2 , the optimal value is given by min{I 1 (v), I 2 (v)}. When
I 1 (v) # I 2 (v), the broken triple
the broken triple
Conditions (3.8) and (3.9) are the so-called "recurrence conditions" for the
corresponding SRBM (see Section 4.1 for more discussion). The proof of Theorem
3.1 is deferred until Section 6. Several preliminary results needed in the proof,
but which are also applicable in higher dimensional problems, are given in Section
5.
For (v) is a linear function of v, whereas I 0 (v) is not since - a 0 (v)
depends on v. In fact, in Lemma 6.1 we will check that I 0
Also it will be verified in Theorems 6.1 and 6.3 that, for
I i (v) =2 # T|| -
where T is the first time for z i to reach v, and we let C
. More interestingly,
we observe that the optimal value I i (v), depends on the velocity of
the "last segment" of z i , which is always given by -
a i .
In R d with d # 3, it is possible to have more complicated types of optimal
paths. We would now like to outline three principles which are valid for locally
optimal paths in higher dimensions. We do not demonstrate the validity of these
propositions in this tract, rather leaving this for a subsequent paper.
i. Orthogonality law. If a locally optimal triple (x, y, z) is such that z traverses
a face F , x must have a velocity of the form: a = #p while z is
on F . In the general setting, p is a vector orthogonal (under the Euclidean
inner product) to all the reflection vectors of the face.
ii. Norm preservation law. For a broken triple (x, y, z), which in general
may travel along several faces, the norm of the intermediate velocity of x
must be equal to the norm of the drift #.
iii. Symmetry law. For a broken triple (x, y, z) along F , the di#erence of the
velocity of x before and after leaving F must be orthogonal to F with respect
to the inner product induced by the covariance matrix.
With these general principles in hand, it is possible to compute locally optimal
broken paths of any chosen type (i.e. any prescribed order of traversing
the faces). One can then compare the values of each such "locally optimal" path
to discover the globally optimal path for a given point. This essentially reduces
the resolution of the VP to a numerical task. Unfortunately, to be sure that this
numerical task will indeed yield the optimal value for the general VP, one must
establish a principle as outlined in Step 1 at the beginning of Section 3. Such a
principle has been established for R 2
(see Theorem 5.1), but is lacking for more
general state spaces.
4. Semimartingale Reflecting Brownian Motions and Large
Deviations
In this section, we define semimartingale reflecting Brownian motions
(SRBMs). Such processes arise in the study of heavy tra#c approximations
to multiclass queueing networks (see, e.g., Harrison and Nguyen [16]). We also
discuss conditions under which an SRBM is positive recurrence. Finally, we
introduce large deviations principles (LDPs) for an SRBM. The LDPs connect
the VP introduced in (2.5) with a corresponding set of SRBMs and provide the
motivation for our study of such VPs.
4.1. SRBM
Throughout this section, B denotes the #-algebra of Borel subsets of R d
.
Recall that # is a constant vector in R d , # is a d-d symmetric and strictly positive
definite matrix, and R is a d - d matrix. We shall define an SRBM associated
with the data (R d
R). For this note, a
will be called a
filtered space
if# is a set, F is a #-field of subsets of # and {F t } # {F t , t # 0}
is an increasing family of sub-fields of F , i.e., a filtration. If, in addition, P
is a probability measure
will be called a filtered
probability space.
Definition 4.1 (SRBM) Given a probability measure # on (R d
reflecting Brownian motion (abbreviated as SRBM) associated with
the data (R d
#) is an {F t }-adapted, d-dimensional process Z defined on
some filtered probability
continuous paths and Z(t) # R d
(a) X is a d-dimensional Brownian motion with drift vector #, covariance
matrix # and X(0) has distribution #,
(b) {X(t) -X(0) - #t, F t , t # 0} is a martingale,
(iv) Y is an {F t }-adapted, d-dimensional process such that P # -a.s. for each
(b) Y j is continuous and non-decreasing,
(c) Y j can increase only when Z is on the face F j # {x # R d
An SRBM associated with the data (R d
is an {F t }-adapted, d-dimensional
process Z together with a family of probability measures {P x , x #
R d
} defined on some filtered
}) such that, for each x # R d
(i)-(iv) hold with being the point distribution at x.
A (R d
#)-SRBM Z has a fixed initial distribution #, whereas a
(R d
#, R)-SRBM has no fixed start point. The latter fits naturally within
a Markovian process framework. Condition (iv.c) is equivalent to the condition
that, for each t > 0, Z
Loosely speaking, an SRBM behaves like a Brownian motion with drift vector #
and covariance matrix # in the interior of the orthant R d
, and it is confined to
the orthant by instantaneous "reflection" (or "pushing") at the boundary, where
the direction of "reflection" on the jth face F j is given by the jth column of R.
The parameters # and R are called the drift vector, covariance matrix and
reflection matrix of the SRBM, respectively.
Reiman and Williams [32] showed that a necessary condition for a
(R d
to exist is that the reflection matrix R is completely-S,
as defined in Definition 2.2. Taylor and Williams [34] showed that when R is
completely-S, for any probability measure # on (R d
(R d
Z exists and is unique in distribution.
Let # be a probability measure on (R d
B). The measure # is a stationary
distribution for an SRBM Z if for each A # B,
When # is a stationary distribution, the process Z is stationary under the probability
measure P # . Harrison and Williams [18] showed that a stationary dis-
tribution, when it exists, is unique and is absolutely continuous with respect to
the Lebesgue measure on (R d
use # to denote the unique stationary
distribution when it exists. When # exists, the SRBM Z is said to be positive
recurrent. For a (R d
R is an M-matrix as defined in
Bermon and Plemmons [2], it was proved in [18] that Z is positive recurrent if
and only if
In the 2-dimensional case, we have a characterization of positive recurrence
given by Hobson and Rogers [20] and Williams [35], who have shown that a
(R 2
in the quadrant is positive recurrent if and only if (3.8) and
hold.
The following theorem by Dupuis and Williams [14] provides a su#cient
condition to check the positive recurrence of an SRBM. Let R and # be given.
For a # R d
set x a
Theorem 4.1 (Dupuis and Williams). Suppose that for each a # R d
and each
z #(x a ), lim t# the (R d
positive recurrent
for each positive definite matrix #.
Using Theorem 4.1, Budhiraja and Dupuis [6] provided a slight generalization
of the result of Harrison and Williams. For SRBMs in the orthant, no general
recurrence condition has yet been established.
4.2. Large Deviations
In this section, we provide some motivation for our study of the VPs introduced
in (2.5). The primary impetus for our study comes from the theory of large
deviations. An excellent reference for this material is Dembo and Zeitouni [9].
Most large deviations analyses can be divided into two principal parts: proving
an LDP, and solving the associated VP. For SRBMs in the orthant, considerable
progress has been made in the first area by Majewski [28] and we quote his
result shortly. The following conjecture, for SRBMs in the d-dimensional orthant,
provides motivation for our VP.
Conjecture 4.1 (General Large Deviations Principle). Consider a (R d
SRBM Z. Suppose that R is a completely-S matrix and that there exists a
probability measure P # under which Z is stationary. Then for every measurable
A # R d
lim sup
log
d
lim inf
log
where A c and A are respectively the closure and interior of A.
Our goal in the next section is to provide some results which simplify the
analysis and solution of the VPs which appear in Conjecture 4.1. In Section 6,
we narrow our focus to the 2-dimensional case. For this class of VPs, we are able
to provide a complete analytical solution.
Special cases of Conjecture 4.1 above have indeed already been established.
The most general result of which we are aware was given by Majewski [28]:
Theorem 4.1 (Large Deviations Principle). Consider a (R d
where R is an M-matrix and suppose the recurrence condition (4.2) holds. Let
# be the probability measure under which Z is stationary. For every measurable
A # R d
For clarification, it should be noted that Majewski states his result for reflection
matrices R which he terms K-matrices. This class of matrices is equivalent in
our context to what we have chosen to call M-matrices, following Bermon and
Plemmons [2]. In this case, the Skorohod problem has a unique solution and the
reflection mapping is Lipschitz continuous.
5. Optimal Path Properties
The variational problem in (2.5) requires a search over a large class of absolutely
continuous functions. In this section, we argue that, in R 2 , the optimal
reflected path can be chosen such that it consists of at most two linear pieces,
the first of which travels along one of the boundaries of the positive orthant and
another which then traverses the interior. The main result of this section is the
following theorem, which will be used to prove Theorem 3.1.
Theorem 5.1. Consider the VP as given in (2.5) and let v # R 2
. An optimal
triple (x, y, z) from 0 to v can always be chosen so that (x, y, z) is a two-segment,
piecewise linear path; during the first segment, z stays on one of boundaries of
, terminating at a point w on the boundary; during the other segment, z is a
s
direct, linear path from w to v. The first segment can be void, that is we may
have In this case, x, and hence z, is a direct, linear path from 0 to v.
When the reflection matrix is an M-matrix, this result can also be inferred from
Majewski [29], using Lemma 14 of Majewski [28], and Lemma 5.2 below. We
provide a direct proof in this section, which is based on a series of lemmas that
are of independent interest in R d
with arbitrary d # 1.
Our first lemma follows directly from Jensen's inequality. Recall that H d is
the space of all absolutely continuous functions x(-) : [0, # R d which have
square integrable derivatives on bounded intervals and have
Lemma 5.1. Let g be a convex function on R d , and let x # H d . Then for
dt. (5.1)
In other words, a linear path minimizes this unconstrained variational problem.
For our VP, the g(v) we contend with is of the form:
We now consider the boundary of R d
. Note that each face of the boundary
can be defined by partitioning the coordinates of R d into zero and non-zero com-
ponents. For a partition (K 1 , K 2 ) of {1, . , d}, we then define a face associated
with the partition by letting the coordinates in K 1 be zero and the coordinates of
K 2 be non-zero. Note that, for our purposes, the interior of R d
is also considered
a face, corresponding to K
Below, for a partition (K 1 , K 2 ) we also let xK j
be the vector . For
the reflection matrix R, we define two submatrices: R 1 is the principal submatrix
of R with the rows and columns in K 2 deleted, R 21 is the submatrix of R with
row indices in K 2 and column indices in K 1 .
Definition 5.1 We say that a reflected path z is anchored to a face corresponding
to the partition (K 1 , K 2 ) in the interval
finitely many t # (t 1 , t 2 ).
Lemma 5.2. Consider the VP as given in (2.5) and let (x, y, z) be an optimal
triple for this VP. If z is anchored to a face of the boundary of R d
in the interval
there exists an optimal triple (-x, -
y, - z) such that
and -
z
Proof. For completeness, we now explicitly write out the variational problem
under consideration. For a given v 1
consider the
minimization problem:
ds (5.2)
subject to
y(-) is non-decreasing,
We consider an optimal triple (x, y, z), with z anchored to a face corresponding
to some partition (K 1 , K 2 ). Without loss of generality, we assume that y(t 1
for each optimal triple (x, y, z). Thus, z(t 1
By the complementarity condition, -
with our convention that y(t 1
Therefore, we have
and it follows that
By condition (iii) of Definition 5.1,
s
and we then have
which implies
In other words we can "linearize" the paths x and y as follows:
and
then (5.3) and (5.4) show that the new reflected path - z is anchored to the same
face as z on the interval (t 1 , t 2 ). In fact, -
z is now on the face for the entire
interval. Furthermore, it can be checked that -
hence the new reflected path also has the same endpoints. By
Lemma 5.1
#dt.
Thus, - x has equal or lower energy than the original path and hence any optimal
path can be reduced to an equivalent optimal path which has a constant derivative
while its reflection is on a fixed face of the boundary.
The reduction of the VP to a class of piecewise linear functions is not particularly
surprising. Other authors, including O'Connell [31] and Dupuis and
Ishii [11] have achieved similar reductions, but only for special cases, i.e. in R 2 or
for a limited class of reflection matrices. Since Lemma 5.1 holds for any convex
function and in large deviations applications, the kernel which appears in the VP
is always convex (for LDPs associated with random vectors), our proof is valid
for VPs arising from a wide range of LDPs. We have not specifically addressed
the nature of the piecewise linear functions which may solve the VP. In particu-
lar, we have not ruled out a piecewise linear function with an infinite number of
discontinuities in -
x. With the help of the next several lemmas, we can rule out
such paths, at least in R 2 .
Lemma 5.3 (Scaling Lemma). Consider the VP in R d as given in (2.5), with
target point v in the positive orthant.
(a) For any positive k,
(b) If (x, y, z) is an optimal triple for v, then (-x, -
y, -
z) is an optimal triple for kv,
Proof. Let (x, y, z) be an optimal triple which solves the Skorohod problem with
It is clear that (-x, -
y, -
z) also solves the Skorohod problem with -
thermore, we
Hence I(kv) # kI(v). Now since, k > 0 is arbitrary, we have
I(kv). Thus, we have This proves (a) and
the above calculation proves (b).
A similar scaling lemma for variational problems arising from random walks
in an orthant is stated in Ignatyuk et. al. [21].
Lemma 5.4 (Merge Lemma). Let be an R-regulation triple on [0, t 1
with z 1 be an R-regulation triple on [s 2 ,
with z 2 Suppose that both x 1 and x 2 are absolutely
continuous. Define
s
and y, z) is an R-regulation triple on [0, s] with
and such that x is absolutely continuous on [0, s] and2 # s|| -
Proof. Since both x 1 and x 2 are absolutely continuous, x is absolutely continuous
on [0, s]. Also one can check that y is non-decreasing,
We now check that
Clearly, (5.6) is satisfied for is an R-regulation with
Thus, (5.6) holds for s, from which one can readily show that (x, y, z) is
an R-regulation on [0, s]. Finally, (5.5) follows from the definition of x.
In the following, we use E i to denote the one-dimensional edge {v # R d
Lemma 5.5 (Reduction Lemma). Consider the VP in R d as given in (2.5). Let
Suppose that is an optimal triple from 0 to v such that
there exists an
optimal triple (x, y, z) on [0, T ] from 0 to v such that z(t) # E i for
with
Proof. We start by assuming that z 1 be an optimal
triple with z 1
Next, by the Scaling Lemma 5.3 we have k # 1 and
by assumption k #= 1, thus k < 1. Since it follows from Lemma 5.3
that the triple (-x, -
y, -
z) is an optimal triple from 0 to w, where -
By Lemma 5.4, piecing together the triple (-x, - y, -
z) on [0, kt 1 ] with the triple
we have the triple
Furthermore, by (5.5), the triple is optimal, and z 2 (t)
ks 1 . We now iterate our argument, with a new scaling parameter in each
iteration, . Then we have for each integer n # 1, there
exists an optimal triple
k < 1, we have that k n # 0 and hence s n and |z n (s n )| both converge to zero.
By construction, it can be seen that
z
on (s n , t n ) for all n, where each c i # R d is a constant independent of n. Thus
Now we are prepared to construct an optimal triple with the stated prop-
erties. We set (x, y, t, c 3 t) on [0, T ]. By (5.7) we have that
y, z) - (x, y, z)(s 1 ) is an R-regulation on [s 1 , t 1 ] and then by Lemma 5.4,
y, z) is an R-regulation on [0, t 1 - s 1 ]. From the linearity of the Skorohod
problem it is therefore also an R-regulation on [0, T ]. Note that, by construction,
we also have z(T It remains only to show that (x, y, z) is optimal. Note
that each triple must have optimal cost. Hence, if we show that
lim
then we are done. By repeated application of the Scaling Lemma 5.3, (5.5), and
(5.7), we
sn
s
the first part converges to zero. Since t n # T and s n # 0, the
second part, and thus the entire cost, converges to (T/2)||c 1 - #|| 2 , which is just
the cost of the constructed triple (x, y, z). Hence (x, y, z) is an optimal triple.
apply the Scaling Lemma 5.3 with
this k 0 . We are then back in the case z 1 can proceed as before.
Now, using the Reduction Lemma 5.5, we can prove the main theorem of
this section, which states that in R 2 , an optimal reflected path can be chosen
such that it consists of at most two linear pieces.
Proof of Theorem 5.1. Throughout the proof we assume that v # R 2
and that
all paths are piecewise linear as per Lemma 5.2. We divide our argument into
three cases.
(1) Let v be in the interior of R 2
and let (x, y, z) be an optimal triple to v.
Then z either goes directly from the origin to v or else z reaches some point
us assume that t 2 is the last such time.
By Lemma 5.2, z must touch another point on
hence the triple can be chosen so that z(t) # E then by
Lemma 5.5 there exists an optimal triple (-x, -
y, - z) from 0 to w with -
for
two-segment triple, formed by
merging (-x, -
y, - z) and (x, y, z), is optimal.
(2) Suppose v is on a face E 1 of R 2
. Let (x, y, z) be an optimal triple with
another point on E 1 \ {0}, then by Lemma 5.5 the
triple can be chosen such that it is linear. Otherwise, by Lemma 5.2, z has to
touch a (last) point w and stay on E 2 in some time interval. Again by
Lemma 5.2, the triple must be linear from w to v. Furthermore, by Lemma 5.5,
the triple can be chosen to be linear from 0 to w. Hence, in this case, we can
again chose an optimal triple with two linear segments.
then we interchange the roles of E 1 and E 2 in the case 2 argument.
We have thus shown that for any optimal triple, we can choose an equivalent
optimal triple that falls into one of the cases in the statement of Theorem 5.1.
A major open problem is to determine whether or not Theorem 5.1 can be
extended to the case d > 2. The problem in higher dimensions is to eliminate
consideration of paths which "spiral" around the boundary. In R 2 , spiraling
cannot occur (without retracing part of a path) and hence the reduction to a
piecewise linear path with just two pieces is relatively straightforward. One hopes
that in R d that one need only consider piecewise linear paths with d pieces, thus
reducing the general VP to a finite dimensional optimization problem.
In the case reduced our possible solutions to paths which
either go directly from the origin to v through the interior or first travel along
one axis and then travel through the interior to v. In particular, we need only
search over three types of piecewise paths. In the next section, we will argue that
this search can be restricted to just three paths.
6. Further Constrained Variational Problems
In this section we provide the analysis of the VP in R 2 which justifies Theorem
3.1. We first consider the VP defined in (2.5), adding additional constraints
on the allowed path x(-). Recall that the definitions of the direct triple
and the broken triples were given in Section 3. When
we restrict x(-) such that it only takes values in R 2
, the corresponding VP has the
direct triple as an optimal triple. We next consider "broken" triples
in which the reflected path first moves along a face F i and then traverses the inte-
rior. When F i is reflective, and v # C i , the broken triple is an optimal
triple among all two segment broken triples through F i . Once these principles
have been established, the proof of Theorem 3.1 will then follow directly.
Before studying these further constrained VPs, we present the following
lemma.
Lemma 6.1. Let I 0 (v), I 1 (v), and I 2 (v) be given in (3.6) and (3.7). Then,
(a) I 0
(b) I i (v) # I 0 (v) for v # R 2
2. Furthermore, I i
only if v is in the same direction as - a i .
Proof. Part (a). From the definition of I 0 (v) in Section 3, we have
I
s
Part (b). First, note that it follows from (3.2) that
#.
Hence, ||a i
||#||. Furthermore, from the definition of -
a i , we can immediately
observe that ||-a i
||, and thus we have
Using then (3.6) and (3.7), we conclude
I
6.1. Interior Escape Paths
Now let us consider a point v # R 2
and the VP as defined in (2.5). In this
section, we add the additional constraint that x(-) may only take values in R 2
We will use -
I 0 (v) to denote the resulting optimal value, namely,
I
x#H d ,x(T )=v2 # T|| -
for
For the VP (2.5), if we only consider paths which travel in the interior of the
orthant, then by Theorem 5.2 the optimal path is linear and has constant velocity
proportional to the point v that we wish to reach. Hence, we need only determine
the optimal speed to minimize the value of the VP. So we set ct v and the
VP in (6.2) reduces to the following:
I
This is a one-dimensional minimization problem which has a unique minimum at
leading us to the following result.
Theorem 6.1. Among the possible direct triples from the origin to a fixed point
v, the direct triple optimal. The corresponding minimal cost -
I 0 (v)
is I 0 (v).
6.2. Single Segment Boundary Escapes
We now consider optimal reflected paths which travel along face F i to reach
a point along this face. For v # F i , we use -
I i (v) to denote the resulting optimal
value, namely,
I
x#H d ,z(T )=v2 # T|| -
where z(-) is a reflected path associated with x(-), and z(t) # F i for
Theorem 6.2. Let v # F i .
(a) If boundary F i is reflective, then the broken triple
is optimal for (6.4) with -
I
(b) If boundary F i is not reflective, then the direct triple
optimal for (6.4) with -
I
To prove the theorem we will need the following elementary lemma from calculus.
Lemma 6.2. Let f(v) and g(v) be two di#erentiable functions on R d . Let
f(v)/g(v) be defined for v # R d with g(v) #= 0. Then, for any v satisfying
there exists a constant k such that
Proof of Theorem 6.2. We prove the theorem for . In this
proof, we let the normalization of Section 3. In light of
Theorem 5.2, the search of an optimal boundary path can be confined to linear
paths be an R-regulation associated
with x(-) that satisfies z(t) # F 1 for t # 0. Then we have,
Since it is always cheaper to take a z(-) such that z 2 (t) > 0 for
we have y 2
have
s
must be positive and we also must have
that
I
Using Lemma 6.2, it can be checked that each critical point b of the unconstrained
form of (6.7) must satisfy
From (6.8), b - substituting k#p 1 into the left side of (6.9), we
have
Thus, the unconstrained form of (6.7) has two critical points
with
Next, we show that the first critical point
corresponding to not feasible. This is true because, in this case
the regulated speed, -
z 2 (t), along F 1 would then be given by #
a detailed calculation, is negative under our stability condition (3.9). The second
critical point corresponds to our expression for a 1 given in (3.2). One can check
that (a 1 by (3.9), is positive.
Note that when |b| #, away from the boundary, the function in (6.7)
goes to infinity; when b approaches the boundary b # 0, from the interior of
the feasible region, the function in (6.7) goes to infinity. Therefore, the infimum
in (6.7) takes place either at a critical point in the interior or at b
If F 1 is not reflective, then by definition, we have a 1
In this case, then
there are no critical points in the interior of the feasible region and the minimum
must occur at the constraint b which indicates that the direct path along
F 1 is optimal and we have -
I
If F 1 is reflective, then a 1
1 < 0, and this quantity is a critical point which
is in the interior of the feasible region. The value of the VP (6.4) at the critical
point a 1
and we have
where the first equality follows from (6.8) and the second from the definition of - a 1 .
Since I 1 (v) # I 0 (v), as demonstrated in Lemma 6.1, we then have -
I
and the theorem is proved.
The theorem demonstrates that if a face is reflective, then a regulated boundary
path may be part of an optimal path to a point in the face. In the stochastic
setting, we envision such paths as "bouncing paths" which repeatedly bounce
against a face and are heavily regulated to keep them within the quadrant.
Furthermore, it should be noted that the stability conditions (3.8) and (3.9)
for SRBM in R 2
are required for our solution to be valid. In particular the
conditions are used in the proof to eliminate a critical point. If one of the stability
conditions does not hold, then the VP will have optimal value zero for any points
along some ray in R 2 . This means that the VPs given in (4.3)-(4.4), will have
value zero for many sets of interest. This result should be expected, since a
stationary distribution for the SRBM will not exist in cases where the stability
conditions do not hold, hence the LDP of Section 4.2 does not hold.
It is a subject of ongoing research to determine explicit stability conditions
in higher dimensions and analyze their relation to the corresponding VP. It is
possible that heretofore unknown stability conditions will manifest themselves in
solving the VP in higher dimensions.
6.3. Two Segment Boundary Escapes
Recall that, for a point v # R 2
, a broken triple (x, y, z) to v through face F i
consists of two segments: during the first segment, z travels from the origin along
F i up to a point w # F i , and during the second segment, z is a non-regulated
path traveling from w to v. When 0, the broken triple is actually a direct
triple.
In this section, we consider the VP (2.5) when constrained to all broken
triples through a face. For a point v # R 2
, our goal is to determine an optimal
broken triple among all such triples. The corresponding optimal value is denoted
by -
I i (v). The optimal broken triple is an extension of the optimal single segment
triple previously considered for a point v on a boundary face. Thus we employ
the same symbol -
I i (-) to denote the optimal value.
s
Theorem 6.3. Let v # R 2
.
(a) If v # C i , then is an optimal broken triple to v through F i . The
optimal broken path z i has unique breakpoint w # F i with v -
#. Furthermore, the optimal cost -
I i (v) is given by I i (v).
(b) If v # C i , then the direct triple among all broken
triples to v through F i with -
I
Proof. When F i is not reflective, by part (b) of Theorem 6.2, Lemma 5.2 and
Theorem 6.1, the direct triple among all broken triples.
Now we assume that F i is reflective. The optimal total cost for a broken
path through F i to v with a breakpoint at
I(t,
I
I 0 (v - w).
It follows from Theorems 6.1 and 6.2 that
I(t,
Note that -
I(t, v) # tI i (e i ), which goes to infinity as t #. Hence, the minimum
of the function -
I(-, v) must either occur at a critical point in (0, #) or at the
boundary to minimize this function with respect to t, for t > 0, we
take derivatives to obtain:
#t
I(t,
Setting this equal to zero and rearranging yields:
. (6.11)
by (6.1), the breakpoint must satisfy
Thus, v-w must be in the same direction of a i or - a i . The first case is not possible
for a reflective face F i . Thus,
for some c > 0.
To prove part (a), we note that when C i is nonempty, F i is reflective. In
this case, one can check that the critical point
exists and is unique.
To find c, we use the expansion (3.3) on v, (3.4), and the fact that
to obtain
or
#. With breakpoint w, by (6.10) the total cost is
# .
Note that, again using (6.1)
Therefore, we have
I(0, v), as demonstrated in Section 3, we have -
I
and part (a) is proved.
When v # C i and F i is reflective, then no such critical point
exists. Hence, in this case, the optimum occurs at the boundary point
i.e. the optimal triple to v through F i is simply a direct triple, with
corresponding cost -
I
(v). If face F i is not reflective, then the
optimal triple to v through F i is also a direct triple, as discussed at the beginning
of the proof. This establishes part (b), and hence Theorem 6.3.
6.4. Proof of Theorem 3.1
Now we prove the main theorem of the paper. By Theorem 5.1 we may
conclude that any optimal triple can be reduced to an equivalent direct triple or
broken triple through one of the faces. Now, let v # R 2
. The remainder of the
theorem follows directly from the results we have established in this section. We
briefly outline the connection for each case of Theorem 3.1:
(a) The fact that the optimal value is I 0 (v) follows directly from part (b) of
Theorem 6.3.
(b) The result follows from Theorem 6.3, parts (a) and (b), and Lemma 6.1,
part (b).
(c) Analogous to (b) above.
(d) In this case the result follows from part (a) of Theorem 6.3 and Lemma 6.1,
part (b).
In each case, there is a broken or direct triple which attains the corresponding
minimum value.
7. Examples
In this section we apply the main theorem of the paper in some illustrative
examples. In addition to illuminating the results, we expect that this section will
provide a connection to previous results obtained for the stationary distribution
of SRBMs.
7.1. An SRBM from a Tandem Network
We next provide an example of the solution to the VP for SRBM data arising
from di#usion approximations of 2-station tandem queueing networks (Har-
rison [15]). We consider a (R 2
with the following data. We let
# .
It is easy to verify that R is an M-matrix, which implies that the corresponding
reflection mapping, and hence the associated SRBM, is well defined. In
this case, the recurrence conditions are given by (4.2), which reduce to # 1 < 0
From (3.2) and (3.4), some simple calculations yield:
# .
Furthermore, we will have
I
I 1 (v) =-# 1 (v 1

Figure

2. An optimal broken path to v # C1 and an optimal direct path to w # R 2
fixed sign by the recurrence conditions, let us examine more closely
the cases # 2 > 0, # 2 < 0, and #
In the case that # 2 > 0, we note that - a 1
a 2
reflective and face F 2 is non-reflective, with C the broken triple
through F 1 is optimal and the optimal value is given by I 1 (v) above. Within
(which is non-empty) the direct triple is optimal and the value of the VP
is given by I 0 (v). Figure 2 illustrates this case.
now reflective and F 1
non-reflective, and we have that both C 2 and R 2
are non-empty.
In the final case, # we see that -
a 1 is a multiple of (0, 1) # and - a 2 a
multiple of (1, both faces of the quadrant are non-reflective and thus
Furthermore, the direct triple is optimal for all v # R 2
and the
optimal value I 0 (v) simplifies to
I
For this case, Harrison [15] explicitly obtained the density function for the stationary
distribution of the SRBM, which is given by cr -1/2 cos(#/2) exp # 1 |(v 1 +r) #
with It is reassuring to note
that, as expected, the exponent obtained by Harrison exactly matches the VP
value above.
7.2. Skew-Symmetric case
In Harrison and Williams [18,19] it was demonstrated that the stationary
density function for a (R d
admits a separable, exponential form
if and only if the data satisfies the following skew-symmetry condition:
us then assume that the skew-symmetry
condition holds. In this case, a (R d
#, R)-SRBM has a stationary
distribution if and only if (4.2) holds. Furthermore, the stationary density is
given by c exp(-# v), where c is a normalizing constant and
In this subsection, we discuss the solution to the VP in two dimensions in the
case that the data satisfies (7.1) and (4.2). This provides a check of the large
deviations analysis versus an explicit calculation of the stationary density.
Consider a (R 2
loss of we assume the following:
is just the identity matrix and the
skew-symmetry condition (7.1) in fact reduces to just one equation:
With the skew-symmetry condition, we have a number of interesting simplifications
to the expressions derived for the VP, which are summarized in our
next theorem.
Theorem 7.1. Consider a (R 2
whose data satisfies (7.1) and
(4.2). For this SRBM the following hold:
(a) -
a 2 .
(b) At least one of the two faces is reflective.
(c) If F 1 is reflective, and F 2 is not, C and the cone C 1 covers the entire
state space, namely, C 1 # R 2
(d) If F 2 is reflective, and F 1 is not, C and the cone C 2 covers the entire
state space.
- a
- a
(i) F2 is non-reflective (ii) F1 is non-reflective (iii) Both F1 and F2 are reflective
- a

Figure

3. Optimal paths for the skew-symmetric case
both faces are reflective, the cones C 1 and C 2 partition the state space R 2
and possess a common boundary which has direction - a
(f) For any v # R
2 , the optimal value given in (7.2).

Figure

3 illustrates the three general possibilities that can occur for VP solutions
in the skew-symmetry case, as outlined in (c), (d), and (e).
consequence of our theorem is that, for any v # R 2
an optimal triple is always a broken triple, except when both faces are reflective
and v is in the direction of -
a. In this exceptional case, the direct path to v is
optimal. The theorem also verifies that the optimal value I(v) is given by the
exponent in Harrison and Williams [18], as expected.
Proof of Theorem 7.1. We first prove (a). Using (3.2), we have
By (7.3), we have
a 1
a 2
. (7.5)
To prove - a is su#cient to show that
#).
s
By the definition of - a i , we have
Thus, (7.6) reduces to
or
# 0# . (7.7)
Using the expressions for a 1
1 and a 2
2 in (7.4)-(7.5), one can easily check that (7.7)
indeed holds, thus proving - a
To prove (b), we first note from (7.1) that v # Rv > 0 for any v # R 2 . Thus,
Therefore, with (3.5) and part (a), we have
. Furthermore, from (4.2) we also have that
Collecting all of these facts we have the following
conclusions. If r 1 > 0, then (7.4) implies - a 1 > 0; if r 2 > 0, then (7.5) implies
nonnegative entries. This fact,
along with the linear equalities (7.4)-(7.5), imply that at least one of the -a i
is
positive. Since at least one component of - a is positive in every case, we have now
established (b).
Parts (c), (d) and (e) follow directly from parts (a), (b) and the definitions
of C i and reflectivity.
It remains to prove (f). From (c), (d) and (e), we know that, for any v # R 2
I(v) is equal to either #-a 1
#, v# or #-a 2
su#cient
to prove #-a - #, v# v for any v # R 2
, or equivalently, #
#) is equal to either side of (7.7), we have
which is equal to # as desired. This concludes the proof of the theorem.
8. Extensions and Further Research
We now comment on extending these ideas to more general polyhedral state
spaces. It is our hope that our study will provide a framework and road map
especially for further research on higher dimensional problems.
It is clear that much of the analysis in Section 5 will hold in higher dimensions
and for general polyhedral state spaces. However, even for more general
regions in two dimensions, we may have to choose an optimal escape path from
more than three possible types. In other words, the VP can still be reduced
to finite choice problem, but it may be more di#cult to easily characterize the
solutions as we did for the orthant in Section 6.
We encounter more serious di#culties when passing to the VP in three or
more dimensions. A primary challenge to extending the results is to investigate
if an analog to Theorem 5.1 holds in higher dimensions. From a computational
standpoint, it would be most desirable if we could eliminate paths which "spiral"
around the boundary before traversing the interior of the orthant. An example
of such a principle is a conjecture of Majewski's [28] which states that at most
d pieces are needed to solve the VP in R d
. This would limit our search in three
dimensions to 10 types of paths, significantly reducing computational e#ort, even
if it is no longer practical to completely characterize the solutions to the VP, as
we have for the quadrant. It is an interesting open problem to characterize under
what conditions, the VP may be so reduced to finite choice problem. Further
work is also needed in proving LDPs like Conjecture 4.1 for SRBMs and even
more general regulated processes.

Acknowledgments

: We are grateful to C. Knessl, Kurt Majewski, Neil
O'Connell, and Ruth Williams for generously sharing their ideas and preprints.
Part of this research was performed while Jim Dai was spending his sabbatical
visit to Stanford from December 1998 to June 1999. He would like to thank the financial
support of The Georgia Tech Foundation, the Department of Engineering-
Economic Systems/Operations Research and the Graduate School of Business of
Stanford. Partial support from NSF grants DMI-9457336 and DMI-9813345 is
also acknowledged. A good portion of this research was performed while John
Hasenbein was visiting the Centro de Investigaci-on en Matem-aticas (CIMAT) in
Guanajuato, Mexico. He would like to thank CIMAT and the National Science
Foundation, who jointly provided an International Research Fellowship (NSF
Grant INT-9971484), which made this visit possible.
s



--R

Large deviations and queueing networks: methods for rate function identification.
Nonnegative matrices in the mathematical sciences.
"orthant"
On the large deviations behaviour of acyclic networks of G/G/1 queues.
Large deviations for stationary Markov chains in a quarter plane.
Simple necessary and su
Hierarchical modeling of stochastic networks II: strong approximations.
Reflected Brownian motion in an orthant: numerical methods for steady-state analysis
Large Deviations Techniques and Applications
The large deviation principle for a general class of queueing systems.
Large deviation behaviour of two competing queues.
On Lipschitz continuity of the solution mapping to the Skorokhod problem
A Skrokhod problem formulation and large deviation analysis of a processor sharing model.
Lyapunov functions for semimartingale reflecting Brownian motions.

Brownian models of multiclass queueing networks: Current status and open problems.
Reflected Brownian motion on an orthant.
Brownian models of open queueing networks with homogeneous customer populations.
Multidimensional reflected Brownian motions having exponential stationary distributions.
Recurrence and transience of reflecting Brownian motion in the quadrant.
Boundary e


On the di

Large deviations of stationary reflected Brownian motions.
Heavy tra
Large deviations of the steady-state distribution of reflected processes with applications to queueing systems
Solving variational problems associated with large deviations of reflected Brownian motions.
Large deviations for departures from a shared bu
Large deviations for queue lengths at a multi-bu#ered resource
A boundary property of semimartingale reflecting Brownian motions.
Large deviations for performance analysis.
Existence and uniqueness of semimartingale reflecting Brownian motions in an orthant.
Recurrence classification and invariant measure for reflected Brownian motion in a wedge.
Semimartingale reflecting Brownian motions in the orthant.
On the approximation of queueing networks in heavy tra
--TR

--CTR
Sandeep Juneja , Victor Nicola, Efficient simulation of buffer overflow probabilities in jackson networks with feedback, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.15 n.4, p.281-315, October 2005
Florin Avram, On the large deviations approximation for the stationary distribution of skip-free regulated queueing networks, Performance Evaluation, v.51 n.2-4, p.171-190, February
skorohod problems;large deviations;reflecting Brownian motions;variational problems;queueing networks