Two frameworks that have been used to characterize reflected diffusions include stochastic differential equations with reflection and the so-called submartingale problem. We introduce a general formulation of the submartingale problem for (obliquely) reflected diffusions in domains with piecewise C^2 boundaries and piecewise continuous reflection vector fields. Under suitable assumptions, we show that well-posedness of the submartingale problem is equivalent to existence and uniqueness in law of weak solutions to the corresponding stochastic differential equation with reflection. Our result generalizes to the case of reflecting diffusions a classical result due to Stroock and Varadhan on the equivalence of well-posedness of martingale problems and well-posedness of weak solutions of stochastic differential equations in d-dimensional Euclidean space. The analysis in the case of reflected diffusions in domains with non-smooth boundaries is considerably more subtle and requires a careful analysis of the behavior of the reflected diffusion on the boundary of the domain. In particular, the equivalence can fail to hold when our assumptions are not satisfied. The equivalence we establish allows one to transfer results on reflected diffusions characterized by one approach to reflected diffusions analyzed by the other approach. As an application, we provide a characterization of stationary distributions of a large class of reflected diffusions in convex polyhedral domains.
The paper studies distributed static parameter (vector) estimation in sensor networks with nonlinear observation models and noisy inter-sensor communication. It introduces emph{separably estimable} observation models that generalize the observability condition in linear centralized estimation to nonlinear distributed estimation. It studies two distributed estimation algorithms in separably estimable models, the $mathcal{NU}$ (with its linear counterpart $mathcal{LU}$) and the $mathcal{NLU}$. Their update rule combines a emph{consensus} step (where each sensor updates the state by weight averaging it with its neighbors states) and an emph{innovation} step (where each sensor processes its local current observation.) This makes the three algorithms of the textit{consensus + innovations} type, very different from traditional consensus. The paper proves consistency (all sensors reach consensus almost surely and converge to the true parameter value,) efficiency, and asymptotic unbiasedness. For $mathcal{LU}$ and $mathcal{NU}$, it proves asymptotic normality and provides convergence rate guarantees. The three algorithms are characterized by appropriately chosen decaying weight sequences. Algorithms $mathcal{LU}$ and $mathcal{NU}$ are analyzed in the framework of stochastic approximation theory; algorithm $mathcal{NLU}$ exhibits mixed time-scale behavior and biased perturbations, and its analysis requires a different approach that is developed in the paper.
Given a domain G, a reflection vector field d(.) on the boundary of G, and drift and dispersion coefficients b(.) and sigma(.), let L be the usual second-order elliptic operator associated with b(.) and sigma(.). Under suitable assumptions that, in particular, ensure that the associated submartingale problem is well posed, it is shown that a probability measure $pi$ on bar{G} is a stationary distribution for the corresponding reflected diffusion if and only if $pi (partial G) = 0$ and $int_{bar{G}} L f (x) pi (dx) leq 0$ for every f in a certain class of test functions. Moreover, the assumptions are shown to be satisfied by a large class of reflected diffusions in piecewise smooth multi-dimensional domains with possibly oblique reflection.
This paper presents a heavy-traffic analysis of the behavior of a single-server queue under an Earliest-Deadline-First (EDF) scheduling policy in which customers have deadlines and are served only until their deadlines elapse. The performance of the system is measured by the fraction of reneged work (the residual work lost due to elapsed deadlines) which is shown to be minimized by the EDF policy. The evolution of the lead time distribution of customers in queue is described by a measure-valued process. The heavy traffic limit of this (properly scaled) process is shown to be a deterministic function of the limit of the scaled workload process which, in turn, is identified to be a doubly reflected Brownian motion. This paper complements previous work by Doytchinov, Lehoczky and Shreve on the EDF discipline in which customers are served to completion even after their deadlines elapse. The fraction of reneged work in a heavily loaded system and the fraction of late work in the corresponding system without reneging are compared using explicit formulas based on the heavy traffic approximations. The formulas are validated by simulation results.
A many-server queueing system is considered in which customers with independent and identically distributed service times enter service in the order of arrival. The state of the system is represented by a process that describes the total number of customers in the system, as well as a measure-valued process that keeps track of the ages of customers in service, leading to a Markovian description of the dynamics. Under suitable assumptions, a functional central limit theorem is established for the sequence of (centered and scaled) state processes as the number of servers goes to infinity. The limit process describing the total number in system is shown to be an Ito diffusion with a constant diffusion coefficient that is insensitive to the service distribution. The limit of the sequence of (centered and scaled) age processes is shown to be a Hilbert space valued diffusion that can also be characterized as the unique solution of a stochastic partial differential equation that is coupled with the Ito diffusion. Furthermore, the limit processes are shown to be semimartingales and to possess a strong Markov property.
This work considers a server that processes $J$ classes using the generalized processor sharing discipline with base weight vector $alpha=(alpha _1,...,alpha_J)$ and redistribution weight vector $beta=(beta_1,...,beta_J)$. The invariant manifold $mathcal{M}$ of the so-called fluid limit associated with this model is shown to have the form $mathcal{M}={xinmathbb{R}_+^J:x_j=0 for jinmathcal{S}}$, where $mathcal{S}$ is the set of strictly subcritical classes, which is identified explicitly in terms of the vectors $alpha$ and $beta$ and the long-run average work arrival rates $gamma_j$ of each class $j$. In addition, under general assumptions, it is shown that when the heavy traffic condition $sum_{j=1}^Jgamma_j=sum_{j=1}^Jalpha_j$ holds, the functional central limit of the scaled unfinished work process is a reflected diffusion process that lies in $mathcal{M}$. The reflected diffusion limit is characterized by the so-called extended Skorokhod map and may fail to be a semimartingale. This generalizes earlier results obtained for the simpler, balanced case where $gamma_j=alpha_j$ for $j=1,...,J$, in which case $mathcal{M}=mathbb{R}_+^J$ and there is no state-space collapse. Standard techniques for obtaining diffusion approximations cannot be applied in the unbalanced case due to the particular structure of the GPS model. Along the way, this work also establishes a comparison principle for solutions to the extended Skorokhod map associated with this model, which may be of independent interest.
We consider the Skorokhod problem in a time-varying interval. We prove existence and uniqueness for the solution. We also express the solution in terms of an explicit formula. Moving boundaries may generate singularities when they touch. We establish two sets of sufficient conditions on the moving boundaries that guarantee that the variation of the local time of the associated reflected Brownian motion is, respectively, finite and infinite. We also apply these results to study the semimartingale property of a class of two-dimensional reflected Brownian motions.
The Skorokhod map is a convenient tool for constructing solutions to stochastic differential equations with reflecting boundary conditions. In this work, an explicit formula for the Skorokhod map $Gamma_{0,a}$ on $[0,a]$ for any $a>0$ is derived. Specifically, it is shown that on the space $mathcal{D}[0,infty)$ of right-continuous functions with left limits taking values in $mathbb{R}$, $Gamma_{0,a}=Lambda_acirc Gamma_0$, where $Lambda_a:mathcal{D}[0,infty)tomathcal{D}[0,infty)$ is defined by [Lambda_a(phi)(t)=phi(t)-sup_{sin[0,t]}biggl[bigl( phi(s)-abigr)^+wedgeinf_{uin[s,t]}phi(u)biggr]] and $Gamma_0:mathcal{D}[0,infty)tomathcal{D}[0,infty)$ is the Skorokhod map on $[0,infty)$, which is given explicitly by [Gamma_0(psi)(t)=psi(t)+sup_{sin[0,t]}[-psi(s)]^+.] In addition, properties of $Lambda_a$ are developed and comparison properties of $Gamma_{0,a}$ are established.
This work considers a many-server queueing system in which customers with i.i.d., generally distributed service times enter service in the order of arrival. The dynamics of the system is represented in terms of a process that describes the total number of customers in the system, as well as a measure-valued process that keeps track of the ages of customers in service. Under mild assumptions on the service time distribution, as the number of servers goes to infinity, a law of large numbers (or fluid) limit is established for this pair of processes. The limit is characterised as the unique solution to a coupled pair of integral equations, which admits a fairly explicit representation. As a corollary, the fluid limits of several other functionals of interest, such as the waiting time, are also obtained. Furthermore, in the time-homogeneous setting, the fluid limit is shown to converge to its equilibrium. Along the way, some results of independent interest are obtained, including a continuous mapping result and a maximality property of the fluid limit. A motivation for studying these systems is that they arise as models of computer data systems and call centers.
