Heavy traffic analysis of controlled multiplexing systems.
The paper develops the mathematics of the heavy traffic approach to  the control and optimal control problem for multiplexing systems, where there  are many mutually independent sources which feed into a single channel via a  multiplexer (or of networks composed of such subsystems). Due to the  widely varying bit rates over all sources, control over admission, bandwidth,  etc., is needed to assure good performance. Optimal control and heavy traffic  analysis has been shown to yield systems with greatly improved performance.  Indeed, the heavy traffic approach covers many cases of great current interest,  and provides a useful and practical approach to problems of analysis and  control arising in modern high speed telecommunications. Past works on the  heavy traffic approach to the multiplexing problem concentrated on the  uncontrolled system or on the use of the heavy traffic limit control problem  for applications, and did not provide details of the proofs. This is done in  the current paper. The basic control problem for the physical system is hard,  and the heavy traffic approach provides much simplification. Owing to the  presence of the control, as well as to the fact that the cost function of main  interest is ergodic, the problem cannot be fully treated with  classical methods of heavy traffic analysis for queueing  networks. A basic result is that the optimal average costs per unit time for  the physical problem converge to the optimal cost per unit time for the limit  stationary process as the number of sources and the time interval goes to  infinity. This convergence is both in the mean and pathwise senses.  Furthermore, a nice nearly optimal control for the limit system  provides nearly optimal values for the physical system, under heavy traffic, in  both a mean and pathwise sense.
Introduction
The paper develops the mathematics of the heavy traffic approach to the control
and optimal control problem for multiplexing systems. There are many mutually
independent sources which feed into a single channel via a multiplexer or
networks of such systems. Since the process of cell generation by each source is
random, the total instantaneous rate might sometimes exceed the channel ca-
pacity, unless the channel is wastefully large. Buffers of appropriate capacities
are often used (and they will be in this paper) to help smooth the flow and
reduce losses. But, unless possibly long delays and excessive buffer sizes are
acceptable, the problem of cell loss due to buffer overflow remains. Some type
of control is often used to balance the overflows, delays and the losses that the
control itself might introduce.
In general, the sources can be divided into statistically distinct classes; for
example, data, voice and video, and these classes might be subdivided further,
depending on the assumed models for the data (cell) generation. Figures 1.1
and 1.2 illustrate systems with one and two source classes, resp. Figure 1.3
illustrates a small feedforward network.
ae-
-:
Independent Sources
Multiplexer
Buffer

Figure

1.1. A simple multiplexer system. One user class.
\Gamma'
User Class 1
User Class 2
Buffer

Figure

1.2. A simple multiplexer system. Two user classes.
ae ae ae?
-:
ae ae
ae ae ae?
\Phi \Phi \Phi \Phi \Phi \Phi*
User Class 1
User Class 2
Buffer 1 Buffer 2
User Class 3

Figure

1.3. A small network.
Even for the uncontrolled model, the problem of computing steady state
losses and delays is difficult. For the Markov modulated source with a "fluid"
model for both the cell generation and the channel transmitter, a single source
class, and an infinite buffer, the problem was resolved via use of clever transformations
in Anick, Mitra and Sondhi [1]. For the same case, the fact that
there are a large number of sources was exploited in Knessl and Morrison [7],
who used a type of heavy traffic method and a matched asymptotic expansion
to get approximations. Such methods do not seem to work with more complex
problems, where there is control or where the buffer is finite. The difficulties
only increase when there are many source classes.
A direct heavy traffic approach was taken in Kushner and Martins [16],
who showed how to get the correct limit for an uncontrolled problem but with
an arbitrary number of source classes. Numerical data for such systems as
well as for some control problems was presented in [18], which showed good
agreement with the exact results for many instances where the traffic was not
"heavy," say with a utilization of 75-85%. A large class of control problems
was exhaustively discussed in Kushner, Jarvis and Yang [14]. This work used
heavy traffic modeling of control problems, and numerical approximations to
the heavy traffic limit. The considerable advantages of the method for analysis
and design were clear.
The basic control problem for the physical system is hard, and the heavy
traffic approach provides much simplification. The control problem will be discussed
in detail below. But, basically, it is a controlled heavy traffic model,
where the average cost per unit time over an infinite time interval is of interest.
One of the cost terms of interest is the mean value of the scaled overflow from
the buffer, which is a "reflection term" in the limit. One would like to show
that the optimally controlled costs for the physical problem converge to the
optimally controlled cost for the limit problem, and that a nearly optimal control
for the limit problem is also nearly optimal for the physical problem if the
traffic is heavy. Owing to the presence of the control, as well as the ergodic cost
function, the problem is hard and cannot be treated with "classical" methods
of heavy traffic analysis.
The interest in [11, 14] was in the exploration of the practical use of the heavy
traffic limits and little attention was devoted to the proofs of convergence, although
the basic techniques needed for the proofs existed in the "controlled"
heavy traffic literature, particularly in the methods developed by the author
and coworkers [13, 15, 17, 19, 20, 22]. Heavy traffic methods for queueing type
problems have been of great interest since the early work of Iglehart and Whitt
[5] and sophisticated results [23] are available for the uncontrolled queueing net-work
problem where there is no state dependence. The work [20] introduced
the "martingale" methods for dealing with both control and general state dependence
for queueing networks. In this paper, we will describe the techniques
needed for the controlled multiplexer problem and give the relevant proofs. The
heavy traffic approach covers many cases of great current interest, and provides
a useful and practical approach to problems of analysis and control arising in
modern high speed telecommunications.
In order to motivate the overall approach, we will now say a little about
the numerical results of [14]. Many standard types of control mechanisms are
covered. A canonical control mechanism is the marking of low priority cells at
the source, and deleting them (either at the source or at the buffer entrance) if
it seems likely that an overflow problem is developing. If the rules for deletion
depend appropriately on the system state, then the system performance can be
improved substantially [14]. Under broad and reasonable conditions, such cell
deletions will occur only rarely, as was amply demonstrated by the data in [14].
Alternative control mechanisms which fit into our framework are the purchase
(in a feedback way) of extra bandwidth, more efficient coding or the controlled
use of an extra channel.
The so-called "leaky bucket" controller is commonly used. There, cells are
deleted at the sources according to a rule determined by the token and cell
arrival streams and token buffer size. It was seen in [14] that this form also fits
our framework, and that it is much inferior to the use of reasonable feedback
controls.
An important question concerns the tradeoff between losses due the deliberate
discarding of cells by the controller and losses due to arrivals of cells to
a full buffer. The latter losses are more important, and the control approach
allows us to understand the possible tradeoffs, while considering delay as well.
When there are many classes of sources, each of which can be controlled sepa-
rately, the control problem is more subtle, since losses/class would normally be
weighed differently, and there might be different constraints on the maximum
mean losses [14].
Sometimes one wants an optimal or nearly optimal control, the value of an
optimal cost, or the value of some performance measure under a control that
is optimal for some other performance measure. But optimization per se was
not necessarily the main interest in [14]. Perhaps of greater interest is the use
of optimizing or optimal control methods for exploration. The value of this
approach was amply demonstrated in [14], and many of the results were not
at all a priori obvious. The large gains due to the use of feedback control were
demonstrated. The dependence on the parameters of the problem was discussed,
as was the sensitivity of the performance to variations or approximations in the
control. It was shown that there is a near linearity of the (log of the) components
of the optimal losses as a function of the buffer size, which can be exploited to
get results where the probabilities of loss are extremely small. This was not
obvious, since for each buffer size the cost and its components are the solution
to a different optimization (hence nonlinear) problem. The structure of the
control is often simple (e.g., linear switching curves). The dependence of the
performance on the bounds on the maximum mean loss rates at the controls
and other system data, as well as the effects of the "noisiness" and modeling
errors were discussed. Codes for the numerical solution are publically available
on the internet, and documented in [6].
We assume that each source is of the Markov modulated type of Anick, Mitra
and Sondhi [1], although the limit equations are the same for other types of cell
creation mechanisms, such as low order auto regressive schemes. The general
methods apply to an arbitrary number of source classes, or even to certain
networks [14, 16, 18]. But in order to focus on the essential mathematical ideas
without excessive notational encumbrances, we will concentrate on the case
where there is only one single source class.
The basic state variables are the buffer content and the numbers of on
sources. Under appropriate scaling and centering, as the number of sources
N and channel bandwidth become large, the processes defined by the state
variables can be approximated by a controlled reflected diffusion process, which
represent the scaled and centered number of on sources and the scaled buffer
content. The "limit" variables can be interpreted as "aggregated" states. The
proofs use the fact that as the size of the system (N and bandwidth) grows, laws
of large numbers and central limit theorems can be exploited. The "limit" or
aggregate equations can be used to compute nearly optimal or good controls for
the physical system, and to get good estimates of all of the important measures
of performance. The relative simplicity of the heavy traffic limit helps us to
understand the main parametric dependencies and yields both qualitative and
quantitative information which is often very hard to get otherwise [14].
In Section 2, the physical problem is formulated for the case of a single user
class. The methods and results are the same, irrespective of the number of user
class, but we wish to minimize notational complexity. The input-output equations
are written in a form that facilitates the derivation of the limit equations,
and the heavy traffic limit is derived for a controlled problem. The analysis
is more or less straightforward diffusion approximation analysis, but using the
martingale problem methods. The basic heavy traffic condition is that the channel
speed is slightly greater (of the order O(
than the mean rate of cell
generation for all sources, and will be quantified in Section 2. It is seen in [14]
that this is sufficient for good performance. The form in which the control appears
in the input-output equations was shown in [14] to cover a large number
of important cases. Section 3 is concerned with the convergence of appropriate
costs, defined on a finite time interval. It is shown that the limit optimal control
problem can be used to get approximations for the physical control problem
under heavy traffic.
The "ergodic" or average cost per unit time problem (over an infinite time
interval) is dealt with in Sections 4 and 5. Since the convergence theory is
considerably harder than that for the problem over a finite interval, the development
is split into two parts. Section 4 deals with the uncontrolled problem.
This allows the introduction of the basic "occupation measure" method of proof
in a simpler context. The idea is to show that the sequence of costs (as N !1
and the time period goes to infinity) converges to that for the stationary limit
process, no matter how the parameters go to their limits. It turns out that
both the mean values and (in probability) the pathwise values converge to the
"ergodic" value. This is important since in any single application, we have just
one sample path, so mean values are less important than pathwise values. The
basic occupation measure technique that is used has broad applications for limit
problems (either controlled or uncontrolled) where ergodic cost criteria are im-
portant, as seen here and in [10, 17]. We try to develop the proof so that the
main ideas are represented, but it is not overencumbered with technicalities.
The ergodic control problem is treated in Section 5. The details of proof are
quite similar to what was done for the uncontrolled problem, except for certain
questions concerning the existence of "nice" almost optimal feedback controls.
But the needed additional results are essentially consequences of results in [9,
12]. A basic result is that the optimal average costs per unit time converge
to the optimal cost per unit time for the limit stationary process as
and the time interval goes to infinity in any way at all. This convergence is
both in mean and pathwise. Furthermore, a "nice" nearly optimal control for
the limit system provides nearly optimal values for the physical system, under
heavy traffic, in both a mean and pathwise sense. The fact that N and the
time can go to infinity in any way at all is important, since the result would not
be useful if, say, we required that either N or the time increase as the traffic
intensity increased, in order to get a useful approximation.
Section 6 contains some background material on weak convergence. Since
[11, 14] dealt extensively with numerical data, such data is not discussed here.
2 The Input-Output Equations: One Class of
Users
There are N mutually independent sources which are statistically identical, each
of the "Markov modulated" type of Anick, Mitra and Sondhi [1]. Thus, each
source alternates between on intervals in which cells are created and off intervals
during which no cells are created. The duration of each on (resp., off) period is
exponentially distributed with mean value 1=- (resp., 1=-). When on, a source
can create cells according to either a "fluid" or a Poisson process, with mean
rate - ? 0, or any combination of the two. By "fluid," we mean that the cell
sizes are identical and small, so that the number of cells created can be taken to
be - times the total on time. The model is intended to capture the variable bit
rate property of the source. The basic reference for the uncontrolled problem
in heavy traffic is Kushner and Martins [16].
Some cells might be deleted by a controller which can depend on the system
state information. After control, the remaining cells are queued in the flow
smoothing buffer of a transmitter of finite size B
N . An arrival to a full buffer
is rejected.
The numerical data in in Kushner, Jarvis and Yang [14] argue that
N is
the correct order for a flow smoothing buffer. This is also implied by the form
of the heavy traffic limit. If the buffer size were o(
N ), then the losses would
be large and the heavy traffic limit would not see any buffer. For a system
satisfying (2.3) with a buffer of order O(
N ), the buffer is nearly always empty
for large N; as is seen in the numerical work reported in [14]. The controller can
be located either at the sources or at the buffer. The transmitter service process
can be either fluid or non-fluid. By "fluid," we mean that the processing time
is the same for each cell. Let c N denote the transmitter (i.e., channel) rate.
The input-output equation. Let ff i;N (t) denote the number of cells deleted
from the ith source by time t; and define:
ff i;N (t):
Let X N (t) denote (1=
N )\Theta (the number of cells in the buffer at t). Let D N (t)
denote (1=
(number of cells transmitted by t, assuming that the buffer
is never empty). Let U N
(number of cells rejected by time t
due to a full buffer) and A N
(total number of cells created
by the N sources by time t). Let L N (\Delta) denote (1=
N times) the number of
"fictitious" cells transmitted when the buffer is empty. Thus D N (t) \Gamma L N (t) is
the scaled number of cells actually transmitted by time t. This way of writing
the transmitted number is both traditional and convenient for getting the limit
equations. Then the equation for the scaled buffer content is
For the fluid transmitter case, we can suppose that D N
The non-fluid transmitter case. For each N , let
the sequence of (real and fictitious) service times. They will depend on N ,
since the transmitter's work is roughly proportional to N . They are assumed
to be mutually independent, identically distributed and independent of the set
of source processes. The definitions imply that c
Assume that
there is
sup
and that there is oe
\Theta
To get the (heavy traffic) stochastic differential equation approximation,
we make the usual assumption that the transmitter works slightly faster than
the stationary total mean arrival rate of messages from all sources, which is
N-). In particular, suppose that there is constant - a
This was shown to be adequate for good performance in [14].
The controller assumptions. It is argued in [14] that in typical applications
good controllers can be represented in the following form. There are - u ? 0 and
(\Delta) such that
Z tu N (s)ds
where
~
t, as N !1: (2:4b)
Furthermore, for the general cases discussed in [14], it is also true that
sup
each t; (2:4c)
and, more generally,
sup
which will be of use for treating the ergodic cost criterion. The symbol )
denotes weak convergence. See Section 6. The controller choices at each time
depend only on the system data and prior controller choices up to time t, as
do u N (t) and ~
ff N (t). Loosely speaking, u N (t) represents the scaled conditional
(given the past data) mean rate of cell deletion at time t (or its "local average").
~
ff N (\Delta) is the "control noise;" it represents the (scaled) variation of the actual
number of cells being deleted about the conditional mean value. The upper
bound -
u is a quality of service constraint. It is a limit on the scaled mean rate
of cell deletions. It is seen in [14] that (2.4b) is a consequence of the law of large
numbers and the large value of N , and that there is no need for more control
for good performance. Since we are concerned only with the mathematics of
the convergence in this paper, the form (2.4) will be accepted, and the reader
is referred to [14] for further discussion. By an admissible control for (2.1),
we mean any measurable control rule which depends only on the available past
information and satisfies (2.4).
Simplification of the input-output equation. Let y i (t) be the indicator
function of the event that source i is on at time t. Suppose that the
source on-off processes are stationary. Define Y N
By the stationarity and the "Markov mod-
ulated" assumption, EY N Suppose that fZ N (0)g is tight. The
controls are always assumed to be admissible. The martingales ~
A N (\Delta) and ~
in the next theorem represent the "local unpredictability" in the arrival and departure
processes, resp. Let F N
t denote the minimal oe\Gammaalgebra which measures
t being the expectation
conditioned on F N
Theorem 2.1. The system equations can be written as
Z tZ N (s)ds
\Gammaff
ae N (\Delta) converges weakly and in mean to the "zero" process and ~
A N (\Delta) and
~
0 (\Delta) are martingales. The sequence
A N (\Delta); ~
(2:7a)
is tight. Write the limit of a weakly convergent subsequence as
There is a measurable process u(\Delta) satisfying 0 - u(t) -
u such that
u(s)ds and
L(\Delta) and U (\Delta) are the reflection terms. For the source fluid model, W 2
and W 3 for the transmitter output fluid model. Otherwise, the W i (\Delta) are
mutually independent Wiener processes. The other processes are non-anticipative
with respect to the Wiener processes. If there is no control and the initial conditions
fX N (0)g converge weakly, then any subsequence has the same limit.
The variance parameter of W 1 (\Delta) is oe 2
2-). For the non-fluid
cases, the variance parameters of W 2 (\Delta) and W 3 (\Delta) are oe 2
Comment on oe 2
2 . For simplicity, we have supposed either "fluid" or "Poisson"
sources. Intermediate cases are possible, where some are "fluid" and others
"Poisson," or where each source alternates between the possibilities. Then just
adjust oe 2
proportionally.
Proof. Recall that by (2.4), we can write ff N
process. For notational simplicity, it is usual
to rescale such that this will be done henceforth. Many of the
details for the uncontrolled case are in [16] but will be outlined for the sake of
self containment. Since fX N (0)g is tight, any subsequence contains a further
subsequence which converges weakly. To simplify notation, and without loss
of generality, we simply suppose that the original sequence fX N (0)g converges
weakly.
Write a i (t) for the number of cells created by source i by time t. By the
properties of Markov chains and the definition of the process y i (\Delta), we can write
dy
where ~
are orthogonal F N
t \Gammamartingales. For the "fluid" input
model, ~ a i since the source cell creation rate is then either unity or zero,
depending on whether the source is on or off.
Define the F N
\Gammamartingale process ~
A N (\Delta) by
~
A N
a
ds
Then, using the fact that EY N
A N
Z t[Y N ds
Z tEY N ds
Z tZ N ds
Define the martingale process ~
D N (\Delta) by
~
Nt
and define S N (\Delta) by S N (number of real and fictitious departures
up to time t). We have
1=
Then we can write
Using the heavy traffic condition (2.3) and the fact that
the difference between the time of the first departure at or after time t minus t,
the last term on the right can be written as
- at
Combining the above representations yields
where ~
Z N (\Delta) is an F N
t \Gammamartingale, and
Z tZ N ds \Gamma - at
\Gammaff
Standard "Markov chain" arguments yield
The f~y i (\Delta); ~a i (\Delta)g are independent of D N (\Delta); S N (\Delta). Furthermore, it is not hard
to verify that for each s ? 0
sup
A N (t)
and
sup
The tightness of the martingale sequences is a consequence of the criteria of
Theorem 6.1. Condition (2.2b) and Chebychev's inequality imply that for any
lim
sup
0:
Thus the discontinuities of ~
N (\Delta) on any finite interval go to zero as
This implies that any weak sense limit process of f ~
D N (\Delta)g has continuous paths
with probability one (see Section 6). Similar considerations (together with the
fact that their jumps are O(1=
N) imply that the sequence
f ~
is tight and that the limit processes have continuous paths with probability one.
Since S N (\Delta) converges weakly (and in mean for each t) to the process S(\Delta) with
values ct j -t=(-); the sequence f ~
D N (S N (\Delta))g is also tight. The
sequence fff N (\Delta)g is obviously tight by the conditions put on it in (2.4), and any
sense limit process has continuous paths with probability one.
The most direct way to show the tightness of the sequence of reflection terms
(\Delta))g is to use the reflection map, and work in "pieces," as follows.
define the random times
oe N
On the interval [oe N
n+1 ); there is only a "lower" reflection. On that interval,
appropriately defined H N (\Delta). Then we have
the reflection map (for
ae
t-s-oe N
\GammaH N (t)
oe
There is the analogous formula for the upper reflection term U N (\Delta) on the intervals
n These formulas and the proved tightness property of the functions
imply the tightness of fL N (\Delta); U N (\Delta)g provided that on each interval
[0; T ], there are only a finite number of excursions: i.e., that
lim
lim inf
oe N
lim
lim inf
But (2.15) follows from the tightness of fH N (\Delta)g.
Finally, since all of the other processes in (2.1) are tight, so is fX N (\Delta); Z N (\Delta)g,
and all of the weak sense limits have continuous paths with probability one. Let
us fix a weakly convergent subsequence, and index it by N for notational simplic-
ity. Let \Phi(\Delta) in (2.7b) denote the weak sense limits of the selected subsequence,
and let F t be the minimal oe\Gammaalgebra which measures f\Phi(s); s - tg. By the
convergence, it is clear that (2.8) holds. Also, it is not hard to see that
t. Furthermore, we can check that the weak convergence
implies that L(\Delta) and U (\Delta) are reflection terms: In other words, they are non-
negative, nonincreasing and can increase only when X(\Delta) takes values on the
appropriate boundary.
Since ~
process by hypothesis and 0 - u N (t) - u, it can be
readily shown that ff(\Delta) is Lipschitz continuous with Lipschitz coefficient -
u:
Thus, there is a measurable process u(\Delta) satisfying 0 - u(t) -
u such that
u(s)ds.
We need only show that the W i (\Delta) are the desired Wiener processes, and the
non-anticipativity property. If ff(\Delta) is non-anticipative, then we can take u(\Delta)
to be non-anticipative.
In the calculation below, oe 2
the source is "fluid," and oe 2
the transmitter is "fluid." Define W N
Z N (\Delta), W N
A N (\Delta), W N
3 (\Delta)): For f(\Delta) satisfying the requirements
of Theorem 6.3 (whatever the dimension), and t - 0; - ? 0, for small
(possible modulo an "end term")
f
\Theta
f
Now use a truncated second order Taylor series expansion of the terms in the
sum in (2.16), the martingale properties, (2.12) and (2.13), to get that
f
Z t+-
ds
goes to zero as N !1: Let \Phi N (\Delta) represent the set of processes in (2.7a). Now,
letting h(\Delta); t; -; t i and k satisfy the conditions in Theorem 6.3, we have that
[f
Z t+-
ds
as along the convergent subsequence. Using this fact and the weak
convergence yields that
Z t+-
ds
0:
Now Theorem 6.3 implies that (W 1 (\Delta); W 2 (\Delta)) is an F t \GammaWiener process.
An analogous argument using
f
in lieu of (2.16) and using (2.2) and the convergence properties of S N (\Delta) implies
that W 3 (\Delta) is an F t \GammaWiener process. Since (W N
3 (\Delta) are
independent, so are (W 1 (\Delta)); W 2 (\Delta)) and W 3 (\Delta). Hence W (\Delta) is an F t \GammaWiener
process.
If there is no control and the initial condition X(0) is fixed, then the subsequence
is irrelevant by the uniqueness of the limit process.
3 The Control Problem on a Finite Time In-
terval
expectation, given the initial condition (x; z): Let k(\Delta) be a
bounded and continuous function, c i ? 0 and, for T ? 0 and admissible controls
(for the physical and limit systems, resp.), define the cost
functions
Z Tk(X N (s))ds
Z Tu N (s)ds; (3:1a)
Z Tu(s)ds; (3:2a)
the infs are over the admissible controls for the various cases.
Comment on the discounted cost. For fi ? 0, define the discounted costs
Z 1e \Gammafis
\Theta

Z 1e \Gammafis [c 0 dU
Then the next theorem continues to hold, with essentially the same proof. For
small fi ? 0, the discounted cost is an alternative to the ergodic cost of Sections
4 and 5, and the proof is simpler, being essentially that of this section. The
computed controls are close to those for the ergodic cost problem for small
Theorem 3.1. For each x; z and T ,
Let q(\Delta) be a continuous real-value function which is continuous and non-increasing
in x. Define the control u N as follows. It takes values 0 and - u, with
u being the value if z \Gamma q(x) - 0 and 0 being the value otherwise. Then
Optimality of and importance of controls such as u 0 (\Delta): The assertion
concerning simply says that the control divides the (x; z)\Gammastate space into
two regions, in which we either have no control or maximum control, and that
the z \Gammaset on which control is exercised is non-decreasing as x increases and
can increase only continuously. The optimal control for the limit ergodic cost
problem takes this form, as it does for the discounted cost function. For the
finite time cost problem, the shape is the same, but depends continuously on
time. In fact, for the fluid case, where W 2 (\Delta) just a linear
function of x. Otherwise, it is strictly concave and decreasing as x increases
[14]. The convergence also holds if q(\Delta) has a finite number of discontinuities
or if the control is of the threshold type, where there is a number x 0 such
that control is exercised if and only if X N (t) - x 0 . The convergence (3.4) will
obviously hold for more general controls than u 0 (\Delta). The theorem shows that,
under heavy traffic, the costs for the physical system are nearly optimal when
using an optimal or nearly optimal control for the limit system. The optimal
switching surface for the multiclass case, where each class might have its own
control, has a similar planar or piecewise planar boundary, and the analogous
theorem holds.
Proof. Given arbitrary ffl ? 0, let u N (\Delta) be an ffl\Gammaoptimal admissible control for
the physical process. Select and work with a weakly convergent subsequence
of (2.7a), with limit represented by (2.7b) and (2.8), with
u(s)ds.
Then, by the weak convergence proved in Theorem 2.1, (3.1a) converges in
distribution to in (3.2a). Also, by the boundedness of the functions involved,
the expectations of the last two terms in (3.1a) converge to the expectations of
the analogous terms in (3.2a). Since the U N (T ) are not necessarily bounded
uniformly in N for any T ? 0, in order to show that their expectations converge
to that of the limit we need to prove that for each T ? 0
uniformly integrable. (3:5)
Write (2.6) in the form
where H N (0) 2 [0; B]: Then, by the definitions of the two reflection terms, it
can be verified that
where K N (t) equals the number of excursions of X N (\Delta) from 0 to B on the
interval [0; t]; and L N (\Delta) satisfies an analogous expression. It can readily be
verified using (2.4c), and the properties of the \Delta N
A N (\Delta) and ~
Z N (\Delta), that for
each
sup
s-T
A proof nearly identical to that used for a related problem in [Section 4][22]
shows that
sup
each integer k: (3:7b)
Inequalities (3.6) and (3.7) imply (3.5).
Since u N (\Delta) is an ffl\Gammaoptimal control for the physical system,
Given (3.5), the weak convergence and Fatou's Lemma yield that (along the
weakly convergent subsequence)
lim inf
imply that if N !1 along the selected
weakly convergent subsequence then
lim inf
Since (3.10) holds for any weakly convergent subsequence, it holds simply if
To prove the reverse inequality to (3.10), namely,
lim sup
fix arbitrary ffl ? 0 and use a "nice" ffl\Gammaoptimal control u ffl (\Delta) for the limit system
which can also be "applied" to the physical system such that
For the moment, suppose that there is such a control u ffl (\Delta) depending smoothly
on the state and time (this will be true if W 1 (\Delta) +W 2 (\Delta) is not the zero process,
and is probably true in general). Using the control u ffl (X N (\Delta); Z N (\Delta); \Delta) on the
physical process and a weak convergence argument yields (3.12). The general
case uses an appropriate "randomized" ffl\Gammaoptimal control law such that (3.12)
holds. The construction of this control law is a special case of what was done
in [13, Theorem 5.2, Chapter 10], and the details are omitted.
4 The Uncontrolled Ergodic Cost Problem
In this section, we will be concerned with the average cost per unit time problem,
when there is no control. It is notationally simpler to introduce the the basic
techniques of proof for the uncontrolled case. The extension to the control
problem, which uses essentially the same proof, is in the following section. The
following result will be needed in Theorem 4.2. Keep in mind that W 2 (\Delta) +W 3 (\Delta)
is the zero process only if the input (when the source is on) and transmitter
processes are both "fluid."
Theorem 4.1. If W 2 (\Delta) is not the zero process, then the uncontrolled
process (X(\Delta); Z(\Delta)) is strong Feller, the transition function P (x; z; t; \Delta) is mutually
absolutely continuous with respect to Lebesgue measure for each initial
condition (x; z) and t ? 0, and there is a unique invariant measure which is
mutually absolutely continuous with respect to Lebesgue measure.
is the zero process, then there is also a unique invariant
measure -(\Delta). -(\Delta) can have positive mass on the boundary
In the interior, where (x; z) 2 (0; B) \Theta IR, it is mutually absolutely continuous
with respect to Lebesgue measure.
Proof. Let not be the zero process. Then the driving Wiener
are mutually independent and non-
degenerate. The strong Feller property, and the fact that the transition function
\Delta) is absolutely continuous with respect to Lebesgue measure for each
(x; z) is shown exactly as done for a related dynamical system in [4, Section 7].
In that paper all state variables were constrained to be positive and were not
upper bounded, and a term such as Z(\Delta) did not appear in the X \Gammaequation. But
the same argument works in an almost identical manner. The cited properties of
the transition function imply that any invariant measure is mutually absolutely
continuous with respect to Lebesgue measure on the state space, from which
the uniqueness of the invariant measure follows.
(\Delta) be the zero process. It is clear from the role of Z(\Delta) in
the X \Gammaequation that P (x; z; t; \Delta) has positive mass on the boundaries. For the
unconstrained problem, P (x; z; t; \Delta) has a density which is positive with respect
to Lebesgue measure for each initial condition (the unconstrained process is
"hypoelliptic"), and this property carries over to the reflected case in that the
measure P (x; z; t; \Delta), when considered on (0; B) \Theta IR, is mutually absolutely
continuous with respect to Lebesgue measure for each (x; z). These properties
imply the uniqueness of the invariant measure.
Stationary process. Consider a vector-valued non-anticipative
process \Theta(\Delta) satisfying
Z t~
u(s)ds
where W (\Delta) is a Wiener process and ~ u(\Delta) is a non-anticipative control. The process
is said to be stationary if the measure of the set (\Theta(t
R
does not depend on t. Use the obvious analog of the definition when
some components of \Theta(\Delta) are "reflected."
The cost function. Define the (uncontrolled case) cost functions
Z Tk(X N (s))ds
Z Tk(X(s))ds
where k(\Delta) is bounded and continuous and c 0 ? 0: The proof of the following
theorem is a little more complicated than necessary for the uncontrolled case.
But the occupation measure method which is used also provides the proof for
the controlled case, and is a powerful tool for convergence theorems when the
cost functions are ergodic [17, 10].
By Theorem 4.2, the value fl 0 in (4.2) does not depend on the initial condition
(x; z) and is the same as the cost
Z 1k(X(s))ds
for the stationary (X(\Delta); Z(\Delta)) process.
Theorem 4.2.
where fl 0 is the cost for the stationary limit process. The limit in (4.2) exists
and does not depend on the initial condition. Furthermore, we have the pathwise
convergenceT
Z Tk(X N (s))ds
in probability, as N !1 and T !1 in any (deterministic) way at all. Also,
holds when the N is dropped.
Comment The pathwise convergence is perhaps more important than the convergence
of mean costs, since each realization in an application uses a single
sample path.
Proof. The proof uses a "functional occupation measure" argument, which
also can be used for the control problem. The method will be outlined. Further
details concerning the "weak convergence" issues are in [17] and [10, Chapter
5].
A simpler model problem. For the sake of expository and notational sim-
plicity, the proof will be outlined for a one dimensions problem which has the
same essential structure as our two dimensional problem. The simpler problem
with which we will work will be defined next, and the assumptions stated. The
convergence argument will work for any processes for which the analog of these
assumptions hold, whatever the dimension. There need not be reflection terms,
and the state space [0; B] to be used here for the one dimensional problem can be
replaced by an unbounded set (which would be [0; B] \Theta IR in our original prob-
lem). Analogous assumptions hold for the original system, and the proof holds
for that case in a virtually unchanged way, except for the more complicated
notation.
We will consider the one dimensional problem defined by
where X N (t) 2 [0; B] for all t, L N (\Delta) and U N (\Delta) are the reflection terms at
the end points 0 and B, resp., and B N
R tb(X N (s))ds for a bounded continuous
function b(\Delta). Let F N
t denote the smallest oe\Gammaalgebra which measures
t being the expectation conditioned
on F N
t . Suppose that W N (\Delta) is an F N
\Gammamartingale. Without loss of
generality, we suppose that the processes are defined on the same sample space
for all N so that we can use a generic sample space variable ! to index the paths
for all N:
Suppose that for each x such that X N (0) ) x,
where
where W (\Delta) is a Wiener process with covariance parameter oe 2 , X(t) 2 [0; B] for
all t, L(\Delta) and U (\Delta) are the reflection terms,
b(X(s))ds, and the limit
processes are non-anticipative with respect to W (\Delta): Suppose that (4.7) has a
unique weak sense solution for each initial condition x, and that it has a unique
invariant measure.
Assume, in addition, that
U
is uniformly integrable. (4:8a)
Suppose that
sup
We will also use the following condition. For each real-valued function f(\Delta) on
(\Gamma1; 1) which has compact support and which is continuous, together with its
derivatives up to order three, and each real - 0,
f ww (W N (s))ds
in mean, uniformly in t - 0.
Representation of the costs in terms of sample occupation measures.
The path space for the processes in (4.6) is D 4 [0; 1), and we use
for the canonical element of this space. We next write
the pathwise cost on the left side of (4.5) in terms on an occupation measure.
This representation is the key to the value of the approach. For any real-valued
function f(\Delta) on [0; 1) and t - 0, define the shifted function f t
the shifted and centered function \Delta t the processes
With these definitions, we can write
Z sb(X N
Suppose that
is tight and the weak sense limits satisfy (4.7) for some initial condition.
Let M denote the space of measures on the Borel sets of D 4 [0; 1); with the
topology used on M. In other words, mn (\Delta) ! m(\Delta) in M if and only if
for each bounded and continuous real-valued function F (\Delta) on D 4 [0; 1),
Z
Z
Define the occupation measures Q N;t (\Delta) and Q N
T (\Delta) by
Z TQ N;t (G)dt;
where G is a Borel set in D 4 [0; 1): Note that Q N
T (\Delta) is a measure-valued random
i.e., it is random variable whose values are measures on the Borel sets
of D 4 [0; 1). The role of these concepts will now be seen.
The sample cost on the left side of (4.5) can be approximated in terms of
(\Delta). We can writeT
Z T\Theta [U
Z T+1
Z 1U N (t)dt:
Thus, by the uniform integrability condition (4.8a),T U N (T
Z T\Theta

where the mean value of the "small error" goes to zero as T !1 uniformly in
N . Similarly, for s 2 [0; 1];
Z
Z Tk(X N (t))dt \Gamma
Z sk(X N (t))dt
Z T+s
where the small error goes to zero uniformly in ! as T !1: Thus, modulo an
asymptotically negligible term, we can writeT
Z Tk(X N (s))ds
Z
where
To see (4.13), note that by the definitions
Z
Z T\Theta U
dt;
and use (4.12a). An analogous calculation is used for the other term in the
cost. Note that K(\Delta), as a real-valued function on D 4 [0; 1), is not necessarily
continuous. See the comments concerning continuous functions on D[0:1) in
Section 6. But K(\Delta) is continuous at each point OE(\Delta) which is continuous. Hence
it is continuous almost everywhere with respect to the measure induced by
any limit quadruple satisfying the conditions on the processes in (4.7), since
such process have continuous paths with probability one. It is seen from the
representation (4.13) that the limits of the measure-valued random variables
T (\Delta) determine the limits in (4.5), and so we now characterize the limits of
Weak convergence of the sample occupation measures. Let Q N;!
denote the sample values of the random variable Q
denoting
the associated expectation. Let Q N;t;! (\Delta) denote the sample values of Q N;t (\Delta).
Recalling that Q N;t;! (\Delta) is the occupation measure induced by the processes
in (4.9) at sample space point !, we see from the definition of Q N;!
T (\Delta) as an
integral divided by T , that Q N;!
T (\Delta) is obtained from the Q N;t;! (\Delta); by a
randomization procedure (randomizing over the time shift), where the probability
that t 2 [a; b], 0 - a - b - T , is (b \Gamma a)=T: Thus, the process \Phi N
induced
by Q N;!
T (\Delta) is just the sample process (4.9), but where the time shift t is chosen
at random in [0; T ], as above.
Let us examine the measure-valued random variables Q N
more closely. It
is shown in [17, remark below Theorem 5.4] and analogs of the proofs of Theorem
2.1 or 4.1 in [10] that the tightness of the set of processes f\Phi N;T (\Delta); N;Tg implies
the tightness of the set fQ N
T (\Delta); N;Tg of random measures. Let the measure-valued
random variable Q(\Delta) denote a limit of a weakly convergent subsequence
of fQ N
to denote the sample
values of Q(\Delta) on whatever probability space it is defined.
Each sample value
(\Delta) of Q(\Delta), being a probability measure on D 4 [0; 1),
induces a random process \Phi ! 0
(\Delta)) with paths
in D 4 [0; 1): Keep in mind that ! 0 denotes the sample value of the random
measure, and that the sample value is a measure on D 4 [0; 1). Thus, we can
index the random process which it induces by ! 0 as well. Thus, ! 0 does not
denote a sample value of the random process, but the process itself. We now
need to show that the process induced by any measure Q
(\Delta) is (for almost all
just the stationary process of the form in (4.7). Then the uniqueness of the
measure of that stationary process (which is implied by the uniqueness of the
invariant measure -(\Delta) and the weak sense uniqueness of the solution to (4.7)
for each initial condition) will be used to complete the proof.
The limit processes. The following observations will be needed. Let fY N (\Delta)g
be sequence of processes which converges weakly to a process Y (\Delta) with paths
in D 4 [0; 1): Suppose that on each finite interval, the maximum discontinuity of
Y N (\Delta) goes to zero in probability as N !1: Then, as noted in Section 6, Y (\Delta)
must have continuous paths with probability one. Conversely, weak convergence
of fY N (\Delta)g to a continuous limit process implies that (on any finite interval) the
maximum discontinuity of Y N (\Delta) goes to zero in probability as N !1. These
observations, taken together with the "random" method of constructing each
of the Q N;!
T (\Delta) from the \Phi N
t (\Delta), the assumed weak convergence (4.6), and the
continuity of the limit processes, imply that (for almost all
(\Delta) have continuous paths with
(\Delta)\Gammaprobability one. Thus, without loss
of generality, we can suppose that all the limit processes are continuous for all
0 . It will turn out that
(\Delta) does not depend on ! 0 and that it is the measure
of the stationary process (4.7).
Until further notice, suppose that Q(\Delta) is a weak sense limit as
and T !1: It will be seen below that the uniqueness of the invariant measure
implies that the way that irrelevant. For C ? 0 and
define the function
where the subscript C refers to truncation at \SigmaC: Let F (\Delta) be a real-valued
bounded and continuous (in the Skorohod topology) function on D 4 [0; 1): Then
(by the fact that the weak topology is used on M, and with m(\Delta) being the
canonical element of M) -
R
F (OE(\Delta))m(dOE(\Delta)) is a bounded and continuous
function on M, and by the weak convergence
F (Q N
Z
F (OE(\Delta))Q N
Z
Next, suppose that F (\Delta) is only continuous
(\Delta)-almost everywhere for all ! 0 .
Then ([2, Theorem 5.1]) the convergence (4.14) continues to hold. Thus (4.14)
holds for FC (\Delta). This, the fact that the left side of (4.14) is zero for F
and the arbitrariness of C, imply that
(s))ds
for each t with
(\Delta)\Gammaprobability one, for almost all ! 0 . By the continuity of
the limit processes, we can suppose that (4.15) holds for all t. The fact that
(\Delta) and U ! 0
(\Delta) are reflection terms should be intuitively obvious; the few
details of the proof are the same as those of Part 3 of the proof of [17, Theorem
6.3] and are omitted.
The Wiener process property. We have to verify that W ! 0
(\Delta) is an F ! 0
\GammaWiener
process, with variance parameter oe 2 , where F ! 0
t is the minimal oe\Gammaalgebra which
measures
We will use the martingale method of Theorem 6.3. Let f(\Delta), h(\Delta), t - 0; -
the requirements of Theorem 6.3. We need to show
that, for almost all ! 0 ,
\Theta
f
fww
ds
0:
By Theorem 6.3, this will imply both the non-anticipativity and the Wiener
property.
It will be shown that the expectation of the square of the left side of (4.16)
is zero. The first step is to show that
\Theta
f
fww
dv
But, by the definition of Q N;!
T (\Delta), the measure with respect to which E N;!
T is
the expectation, the left side of (4.17) equalsT 2
Z Tds h
\Theta
f
t+s
fww
dv
Now, write the square of the integral in (4.18) as a double integral and use the
condition (4.8c) to get that (4.18) goes to zero as
this implies (4.17).
Now define the function F (\Delta) on D 4 [0; 1) by
and define -
R F (OE(\Delta))m(dOE(\Delta)): As discussed below (4.14), we can
suppose without loss of generality that F (\Delta) is continuous. Thus, by the weak
convergence Q N
we have the weak convergence -
F (Q N
and,
F (Q N
and the right side equals zero since the left side equals (4.17) which goes to zero.
But this implies (4.16). Now, (4.16) and Theorem 6.3 yield the asserted Wiener
and non-anticipativity properties.
Stationarity of the limit processes \Phi ! 0
(\Delta) for almost all ! 0 . Finally, we
need to show the stationarity of the limit processes \Phi ! 0
This stationarity
(with the uniqueness of the stationary process) and the uniform integrability
(4.8a) yields the assertion concerning the convergenceT
in probability as any way at all, since the limit Q(\Delta)
does not depend on the selected weakly convergent subsequence, and all of the
samples of Q(\Delta) induce the stationary process of form (4.7).
Let G be a Borel set in D 4 [0; 1): For c ? 0; define the "left shifted set" G c
by G Gg. We have
Z TI f\Phi N;t+c (\Delta)2Gg dt:
Hence
Z T+c
I f\Phi N;t+c (\Delta)2Gg
Z cI f\Phi N;t (\Delta)2Gg dt:
Thus Q N;!
for each !; c and G. Thus, we must
have
which implies that (for almost all
the sample values of the limit measures induce stationary processes.
An analogous (but much simpler, since there is no N ) argument works for
the limits in (4.2), both with and without the expectation.
5 The Controlled Problem
Define the cost functions for the limit system:
Remarks. The theorems are divided into two cases. In the first, where W
3 (\Delta) is not the zero process, the system (2.8) is not degenerate and there are
powerful methods in stochastic control for showing existence of smooth almost
optimal controls, and other strong properties of the ergodic processes involved.
Extensive numerical experience for the case where W 2 (\Delta) +W 3 (\Delta) is the zero
process indicates that the same results are true. But the existence of a smooth
ffl\Gammaoptimal feedback control for our problem has not been yet proved. The
main technical difficulties stem from the fact that the noise and the control
occur in different equations. Thus in this case, we assume that for each ffl ? 0,
there is an ffl\Gammaoptimal feedback control, which is optimal with respect to all
admissible controls, and under which the solution to (2.8) is weak sense unique
for each initial condition. [There is a unique invariant measure under such
controls.] This does not seem to be a strong condition. However, if even a small
percentage of the sources are not fluid (i.e., they create cells according to a
Poisson process for a small percentage of their on time, then we are in the nicer
first (the non-degenerate) case. The numerical problem is very well behaved
even in the degenerate case. See the discussion below the statement of Theorem
3.1 concerning the shape of the computed controls. In the "fluid" case, adding
"artificial noise" to the X \Gammaequation makes for a more conservative control [14];
it acts over a larger region, and provides a lower bound to the performance.
Theorem 5.1. Let W 2 (\Delta) +W 3 (\Delta) not be the zero process. Then -
does not depend
on (x; z): There is a state dependent feedback control which is optimal with
respect to all non-anticipative controls. For each ffl ? 0, there is an ffl\Gammaoptimal
control u(x; z) which is continuous, and under which the solution is weak sense
unique for each initial condition, and there is a unique stationary measure.
There is a unique stationary measure under a control of the form of u 0 (\Delta) in
Theorem 3.1.
Proof. The result is given in [9] for the unreflected problem, where the optimality
is with respect to feedback controls. In the last section of [12], it is extended
to optimality with respect to all non-anticipative controls. The problem with
reflections is treated in a nearly identical manner, since the crucial ideas all
involve only the strong Feller property and a Girsanov transformation method,
and these remain valid with the reflections. The stability conditions needed in
[9] all hold here by the boundedness of X(\Delta) and the stability of Z(\Delta):
Theorem 5.2. Let W 2 (\Delta) +W 3 (\Delta) not be the zero process. Then, for any ffl ? 0
and admissible controls u N (\Delta),
lim
0: (5:1)
Let u ffl (\Delta) be ffl\Gammaoptimal feedback control for the ergodic cost problem for the limit
process, which is either continuous or of the form of the u 0 (\Delta) in Theorem 3.1.
Then
lim
0: (5:2)
The N and T can go to infinity in any way at all.
Comment. The conclusions of the theorem are quite strong. It essentially says
that, under heavy traffic, the pathwise average cost cannot be better than the
optimal ergodic cost for the limit system, and the optimal cost can be nearly
realized by the use of some nearly optimal control for the limit system.
Proof. The details are very similar to those of Theorem 4.2 with the control
terminology as in Theorem 3.1 used, and only some comments concerning the
differences will be given. Let u N (\Delta) be admissible. In the terminology of Theorem
4.2, add another component \Delta t ff N (\Delta) to the vector of processes \Phi N;t (\Delta),
add the component ff(\Delta) to the vector of processes \Phi(\Delta); and redefine Q N
cordingly. The arguments of Theorem 4.2 yield the tightness of fQ N
(\Delta)g. Let
weakly convergent subsequence. There is a non-
anticipative control u(\Delta) satisfying 0 - u(t) - u and such that the controlled
limit equation (2.8) holds. As in Theorem 4.2, the limit process is stationary.
Also C N (x; z; T; u N )=N will converge in probability to the stationary cost for
the stationary limit process, as along the selected subse-
quence. Since, for each ffl ? 0, there is a continuous ffl\Gammaoptimal (with respect to
all admissible controls, hence with respect to u(\Delta)) feedback control for the limit
system with stationary cost value -
and the u N (\Delta) are arbitrary, the proof
of Theorem 4.2 yields (5.1).
Now apply u ffl (\Delta) to the physical process, and repeat the procedure of Theorem
4.2. This yields that C N converges in probability to fl(u ffl );
which yields (5.2).
Theorem 5.3. Let W 2 (\Delta) be the zero process. Assume that for each
there is a continuous feedback control u ffl (\Delta) for the limit process which is
ffl\Gammaoptimal with respect to all admissible controls, and under which the solution
to (2.8) is weak sense unique for each initial condition, or else that there is
an ffl\Gammaoptimal control u ffl (\Delta) of the form of the u 0 (\Delta) in Theorem 3.1. Then the
conclusions of Theorem 5.2 continue to hold.
Proof. With the assumption concerning the existence of such an ffl\Gammaoptimal
control, the proof is the same as that of Theorem 5.2 since there is a unique
stationary process under u ffl (\Delta):
6 Comments on Weak Convergence
A few of the basic definitions and tools from weak convergence theory that are
needed in the paper will be given.
1g be a sequence of random variables with values in a complete
and separable metric space S. We say that converges weakly to a
random variable Y and write Yn ) Y , if for each continuous and bounded real-valued
function F (\Delta) on S we have EF (Y n
be real-valued, bounded, measurable, and continuous only almost everywhere
with respect to the measure of Y . Then [2, Theorem 5.1] EF (Y n
The sequence fYn is said to be tight if for each ffi ? 0 there is a compact
set K ffi ae S such that PfYn 62 K ffi Tightness implies the existence
of a weakly convergent subsequence [3, p104].
Let D r [0; 1) denote the space of R r \Gammavalued functions on the interval [0; 1)
which are right continuous and have left hand limits (and are continuous at
simply D[0; 1). The Skorohod topology [2, 3] is
used, with which D[0; 1) can be considered to be a complete and separable
metric space. We note that if a sequence fOE n (\Delta)g in D[0; 1) converges to a
continuous function OE(\Delta) in this topology, then the convergence is uniform on
each bounded time interval. Let OE(\Delta) denote the canonical point in D[0; 1), and
the function F (\Delta) defined by F OE(t) is not necessarily
continuous in the Skorohod topology. But it is continuous at each point OE(\Delta)
which is continuous at t. The following criterion for tightness is very useful for
our needs.
Theorem 6.1. [8, Theorem 2.7b], [3, Theorem 8.6, Chapter 3]. Let fAn (\Delta)g
be a sequence of processes which have paths in D[0; 1). Suppose that for each
each t in a dense set in [0; 1); there is a compact set K ffi;t in IR such
that
and that for each positive T ,
lim
lim sup
sup
-T
sup
where - is a stopping time. Then fAn (\Delta)g is tight in D[0; 1).
Verifying That a Process Is a Martingale. A convenient criterion for
showing that a process is a martingale is needed, and a useful approach is
suggested by the definition of a martingale in terms of conditional expectations.
Theorem 6.2. Let U (\Delta) be a random process with paths in D r [0; 1), and where
U (t) is measurable on the oe\Gammaalgebra F V
t determined by fV (s); s - tg for some
given process V (\Delta) and let EjU (t)j ! 1 for each t. Suppose that for each real
each integer k and each set of real numbers t i - t,
and each bounded and continuous real-valued function h(\Delta),
Then U (t) is an F V
\Gammamartingale.
The Wiener Process. Let the IR r \Gammavalued process W (\Delta) have continuous
paths and satisfy W be a sequence of nondecreasing
oe\Gammaalgebras such that W (t) is F t \Gammameasurable and let EF t [W
with probability one for each t and each s - 0: Thus, W (\Delta) is an F t \Gammamartingale.
Let there be a nonnegative definite matrix \Sigma such that for each t and each s - 0
Then W (\Delta) is a vector-valued Wiener process with covariance \Sigma, and it is also
called an F t \Gamma Wiener process [21, Volume 1, Theorem 4.1]. If W (\Delta) is an
\Gammamartingale and a Wiener process with respect to any nondecreasing sequence
of oe\Gammaalgebras, then it is an F t \GammaWiener process.
The criterion of Theorem 6.2 for verifying that a process is a martingale
can be adapted to verify that it is a vector-valued F t \Gamma Wiener process for
appropriate Suppose that W (\Delta) is a continuous vector-valued process with
each t. Let V (\Delta) be a random process and let F V
t be the smallest
oe\Gammaalgebra which measures fV (s); W
be arbitrary but satisfy the conditions put on these quantities in Theorem 6.2.
Suppose that
and that there is a nonnegative definite matrix \Sigma such that
\Theta
\Theta

0: (6:5)
Then W (\Delta) is an F V
process, with covariance parameter \Sigma.
Proving that (6.4) holds in applications when W (\Delta) is the weak sense limit
of a sequence of martingales fW n (\Delta)g is usually not too hard. But the proof of
might require showing that fjW n (t)j 2 g is uniformly integrable for each t.
This can be avoided by using the following equivalent characterization.
Theorem 6.3. [24] Let f(\Delta) be an arbitrary continuous real-valued function
on IR r which has compact support and whose mixed partial derivatives up to
order three are continuous and bounded. Let V (\Delta) be a random process. Let
the IR r \Gammavalued process W (\Delta) have continuous paths with probability one, and
a nonnegative definite symmetric matrix. Suppose that for each real
each integer k and each set of real numbers t i - t;
and each bounded and continuous real-valued function h(\Delta),
Z t+-
Then W (\Delta) is an F V
\GammaWiener process with covariance parameter \Sigma, where F V
is the smallest oe\Gammaalgebra which measures fV (s); W (s); s - tg.



--R

Stochastic theory of a data handling system with multiple sources.
Convergence of Probability Measures.
Markov Processes: Characterization and Con- vergence
Brownian models of open queueing networks with homogeneous customer populations.
Multiple channel queues in heavy traffic.
Codes for optimal stochastic control: documentation and users guide.
Heavy traffic analysis of a data handling system with multiple sources.
Approximation of Population Processes
Optimality conditions for the average cost per unit time problem with a diffusion model.
Weak Convergence Methods and Singularly Perturbed Stochastic Control and Filtering Problems
Analysis of controlled multiplexing systems via numerical stochastic control techniques.
Control of trunk line systems in heavy traffic.
Numerical Methods for Stochastic Control Problems in Continuous Time.
Controlled and optimally controlled multiplexing systems: A numerical exploration.
Numerical methods for stochastic singular control problems.
Heavy traffic analysis of a data transmission system with many independent sources.
Limit theorems for pathwise average cost per unit time problems for queues in heavy traffic.
Numerical methods for controlled and uncontrolled multiplexing and queueing systems.
Heavy traffic analysis of a controlled multi class queueing network via weak convergence theory.
Optimal and approximately optimal control policies for queues in heavy traffic.
Statistics of Random Processes.
Routing and singular control for queueing networks in heavy traffic.
Open queueing networks in heavy traffic.
Multidimensional Diffusion Processes.
--TR
multiplexing systems;ergodic cost problem;controlled multiplexing;heavy traffic