Long time asymptotics for constrained diffusions in polyhedral domains

We study long time asymptotic properties of constrained diffusions that arise in the heavy traffic analysis of multiclass queueing networks. We first consider the classical diffusion model with constant coefficients, namely a semimartingale reflecting Brownian motion (SRBM) in a d$d$-dimensional positive orthant. Under a natural stability condition on a related deterministic dynamical system [P. Dupuis, R.J. Williams, Lyapunov functions for semimartingale reflecting brownian motions, Annals of Probability 22 (2) (1994) 680–702] showed that an SRBM is ergodic. We strengthen this result by establishing geometric ergodicity for the process. As consequences of geometric ergodicity we obtain finiteness of the moment generating function of the invariant measure in a neighborhood of zero, uniform time estimates for polynomial moments of all orders, and functional central limit results. Similar long time properties are obtained for a broad family of constrained diffusion models with state dependent coefficients under a natural condition on the drift vector field. Such models arise from heavy traffic analysis of queueing networks with state dependent arrival and service rates.     

Simplices and Spectra of Graphs

In this note we show that the (n−2)-dimensional volumes of codimension 2 faces of an n-dimensional simplex are algebraically independent quantities of the volumes of its edge-lengths. The proof involves computation of the eigenvalues of Kneser graphs. We also show examples of families of simplices (of dimension 4 or greater) which show that the set of (n−2)-dimensional volumes of (n−2)-dimensional faces of a simplex do not determine its volume.     

Existence and uniqueness of semimartingale reflecting Brownian motions in an orthant

Summary This work is concerned with the existence and uniqueness of a class of semimartingale reflecting Brownian motions which live in the non-negative orthant of ^d . Loosely speaking, such a process has a semimartingale decomposition such that in the interior of the orthant the process behaves like a Brownian motion with a constant drift and covariance matrix, and at each of the (d-1)-dimensional faces that form the boundary of the orthant, the bounded variation part of the process increases in a given direction (constant for any particular face) so as to confine the process to the orthant. For historical reasons, this pushing at the boundary is called instantaneous reflection. In 1988, Reiman and Williams proved that a necessary condition for the existence of such a semimartingale reflecting Brownian motion (SRBM) is that the reflection matrix formed by the directions of reflection be completely-L. In this work we prove that condition is sufficient for the existence of an SRBM and that the SRBM is unique in law. It follows from the uniqueness that an SRBM defines a strong Markov process. Our results have potential application to the study of diffusions arising as approximations tomulti-class queueing networks.Research supported in part by NSF Grants DMS 8657483, 8722351 and 9023335, and a grant from AT&T Bell Labs. In addition, R.J. Williams was supported in part during the period of this research by an Alfred P. Sloan Research Fellowship     

On the kernel and shortest face complexes in the unit cube

Studying the extreme kernel face complexes of a given dimension, we obtain some lower estimates of the number of shortest face complexes in the n-dimensional unit cube. The number of shortest complexes of k-dimensional faces is shown to be of the same logarithm order as the number of complexes consisting of at most 2 ⁿ⁻¹ different k-dimensional faces if 1 ≤ k ≤ c · n and c < 0.5. This implies similar lower bounds for the maximum length of the kernel DNFs and the number of the shortest DNFs of Boolean functions.     

On a multi-channel change-point problem

A continuous change-point problem is studied in which N independent diffusion processes X _j are observed. Each process X _j is associated with a “channel”, each has an unknown piecewise constant drift and the unit diffusion coefficient. All the channels are connected only by a common change-point of drift. As the result, a change-point problem is defined in which the unknown and unidentifiable drift forms a 2N-dimensional nuisance parameter. The asymptotics of the minimax rate in estimating the change-point is studied as N → ∞. This rate is compared with the case of the known drift. This problem is a special case of an open change-point detection problem in the high-dimensional diffusion with nonparametric drift.      

Variational problem with an obstacle in ℝ<Superscript><Emphasis Type="Italic">N</Emphasis></Superscript> for a class of quadratic functionals

  A variational problem with an obstacle for a certain class of quadratic functionals is considered. Admissible vector-valued functions are assumed to satisfy the Dirichlet boundary condition, and the obstacle is a given smooth (N − 1)-dimensional surface S in ℝ ^N . The surface S is not necessarily bounded. It is proved that any minimizer u of such an obstacle problem is a partially smooth function up to the boundary of a prescribed domain. It is shown that the (n − 2)-Hausdorff measure of the set of singular points is zero. Moreover, u is a weak solution of a quasilinear system with two kinds of quadratic nonlinearities in the gradient. This is proved by a local penalty method. Bibliography: 25 titles. Dedicated to V. A. Solonnikov on the occasion of his jubilee Published in Zapiski Nauchnykh. Seminarov POMI, Vol. 362, 2008, pp. 15–47.     

Balanced complexes and complexes without large missing faces

The face numbers of simplicial complexes without missing faces of dimension larger than i are studied. It is shown that among all such (d−1)-dimensional complexes with non-vanishing top homology, a certain polytopal sphere has the componentwise minimal f-vector; and moreover, among all such 2-Cohen–Macaulay (2-CM) complexes, the same sphere has the componentwise minimal h-vector. It is also verified that the l-skeleton of a flag (d−1)-dimensional 2-CM complex is 2(d−l)-CM, while the l-skeleton of a flag piecewise linear (d−1)-sphere is 2(d−l)-homotopy CM. In addition, tight lower bounds on the face numbers of 2-CM balanced complexes in terms of their dimension and the number of vertices are established.     

On the Graph Connectivity of Skeleta of Convex Polytopes

Given a d-dimensional convex polytope P and nonnegative integer k not exceeding d−1, let denote the simple graph on the node set of k-dimensional faces of P in which two such faces are adjacent if there exists a (k+1)-dimensional face of P which contains them both. The graph is isomorphic to the dual graph of the (d−k)-dimensional skeleton of the normal fan of P. For fixed values of k and d, the largest integer m such that is m-vertex-connected for all d-dimensional polytopes P is determined. This result generalizes Balinski’s theorem on the one-dimensional skeleton of a d-dimensional convex polytope. Supported by the 70/4/8755 ELKE Research Fund of the University of Athens.     

Diffusion approximations for open multiclass queueing networks: sufficient conditions involving state space collapse

Certain diffusion processes known as semimartingale reflecting Brownian motions (SRBMs) have been shown to approximate many single class and some multiclass open queueing networks under conditions of heavy traffic. While it is known that not all multiclass networks with feedback can be approximated in heavy traffic by SRBMs, one of the outstanding challenges in contemporary research on queueing networks is to identify broad categories of networks that can be so approximated and to prove a heavy traffic limit theorem justifying the approximation. In this paper, general sufficient conditions are given under which a heavy traffic limit theorem holds for open multiclass queueing networks with head-of-the-line (HL) service disciplines, which, in particular, require that service within each class is on a first-in-first-out (FIFO) basis. The two main conditions that need to be verified are that (a) the reflection matrix for the SRBM is well defined and completely- S, and (b) a form of state space collapse holds. A result of Dai and Harrison shows that condition (a) holds for FIFO networks of Kelly type and their proof is extended here to cover networks with the HLPPS (head-of-the-line proportional processor sharing) service discipline. In a companion work, Bramson shows that a multiplicative form of state space collapse holds for these two families of networks. These results, when combined with the main theorem of this paper, yield new heavy traffic limit theorems for FIFO networks of Kelly type and networks with the HLPPS service discipline. This revised version was published online in June 2006 with corrections to the Cover Date.     

The element number of the convex regular polytopes

Let Σ be a set of n-dimensional polytopes. A set Ω of n-dimensional polytopes is said to be an element set for Σ if each polytope in Σ is the union of a finite number of polytopes in Ω identified along (n − 1)-dimensional faces. In this paper, we consider the n-dimensional polytopes in general, and extend the notion of element sets to higher dimensions. In particular, we will show that in the 4-space, the element number of the six convex regular polychora is at least 2, and in the n-space (n ≥ 5), the element number is 3, unless n + 1 is a square number.     

Large deviations for the symmetric simple exclusion process in dimensions d≥ 3

We consider symmetric simple exclusion processes with L=&ρmacr;N ^d particles in a periodic d-dimensional lattice of width N. We perform the diffusive hydrodynamic scaling of space and time. The initial condition is arbitrary and is typically far away form equilibrium. It specifies in the scaling limit a density profile on the d-dimensional torus. We are interested in the large deviations of the empirical process, N ^{− d} [∑ ^L ₁δ _{xi (·)}] as random variables taking values in the space of measures on D[0.1]. We prove a large deviation principle, with a rate function that is more or less universal, involving explicity besides the initial profile, only such canonical objects as bulk and self diffusion coefficients. Received: 7 September 1997 / Revised version: 15 May 1998     

Heavy traffic analysis of maximum pressure policies for stochastic processing networks with multiple bottlenecks

A class of open processing networks operating under a maximum pressure policy is considered in the heavy traffic regime. We prove that the diffusion-scaled workload process for a network with several bottleneck resources converges to a semimartingale reflecting Brownian motion (SRBM) living in a polyhedral cone. We also establish a state space collapse result that the queue length process can be lifted from the lower-dimensional workload process.     

Zero sets of solutions to semilinear elliptic systems of first order

Consider a nontrivial smooth solution to a semilinear elliptic system of first order with smooth coefficients defined over an n-dimensional manifold. Assume the operator has the strong unique continuation property. We show that the zero set of the solution is contained in a countable union of smooth (n−2)-dimensional submanifolds. Hence it is countably (n−2)-rectifiable and its Hausdorff dimension is at most n−2. Moreover, it has locally finite (n−2)-dimensional Hausdorff measure. We show by example that every real number between 0 and n−2 actually occurs as the Hausdorff dimension (for a suitable choice of operator). We also derive results for scalar elliptic equations of second order. Oblatum 22-V-1998 & 26-III-1999 / Published online: 10 June 1999     

Symmetries and First Integrals of Differential Equations

It is known that an n-dimensional system of ordinary differential equations with Lie symmetry which involves a divergence-free Liouville vector field possesses n−1 independent first integrals (i.e., it is algebraically integrable) (ünal in Phys. Lett. A 260:352–359, [1999]). In the present paper, we show that if an n-dimensional system of ordinary differential equations admits a C ^∞-symmetry vector field which satisfies some special conditions, then it also possesses n−1 independent first integrals. Several examples are given to illustrate our result. Y. Li’s research was partially supported by NSFC Grants 10531050, 10225107, SRFDP Grant 20040183030, and the 985 program of Jilin University.     

Approximation of classes of periodic multivariable functions by linear positive operators

In an N-dimensional space, we consider the approximation of classes of translation-invariant periodic functions by a linear operator whose kernel is the product of two kernels one of which is positive. We establish that the least upper bound of this approximation does not exceed the sum of properly chosen least upper bounds in m-and ((N − m))-dimensional spaces. We also consider the cases where the inequality obtained turns into the equality. __________ Translated from Ukrains’kyi Matematychnyi Zhurnal, Vol. 58, No. 1, pp. 12–19, January, 2006.     

Evolution equations for shapes and geometries

The first object of this paper is to introduce a new evolution equation for the characteristic function of the boundary Γ of a Lipschitzian domain Ω in the N-dimensional Euclidean space under the influence of a smooth time-dependent velocity field. The originality of this equation is that the evolution takes place in an L^p-space with respect to the (N − 1)-Hausdorff measure. A second more speculative objective is to discuss how that equation can be relaxed to rougher velocity fields via some weak formulation. A candidate is presented and some of the technical difficulties and open issues are discussed. Continuity results in several metric topologies are also presented. The paper also specializes the results on the evolution of the oriented distance function to initial sets with zero N-dimensional Lebesgue measure.     

Ann-dimensional search problem with restricted questions

The problem is the following: How many questions are necessary in the worst case to determine whether a pointX in then-dimensional Euclidean spaceR ⁿ belongs to then-dimensional unit cubeQ ⁿ, where we are allowed to ask which halfspaces of (n−1)-dimensional hyperplanes contain the pointX? It is known that ⌌3n/2⌍ questions are sufficient. We prove here thatcn questions are necessary, wherec≈1.2938 is the solution of the equationx log₂ x−(x−1) log₂ (x−1)=1.     

A characterization of the ellipsoid through the torsion problem

The solution u of the torsion problem in an N-dimensional bounded domain is investigated. The ratio of the partial derivative to the variable x _N is assumed to satisfy a suitable condition along the boundary. If the projection of the domain onto the hyperplane {x _N = 0} is an (N − 1)-dimensional ellipsoid, then the domain itself must be an ellipsoid symmetric in x _N in order that the problem is solvable.      

A heavy traffic limit theorem for a class of open queueing networks with finite buffers

We consider a queueing network of d single server stations. Each station has a finite capacity waiting buffer, and all customers served at a station are homogeneous in terms of service requirements and routing. The routing is assumed to be deterministic and hence feedforward. A server stops working when the downstream buffer is full. We show that a properly normalized d-dimensional queue length process converges in distribution to a fd-dimensional semimartingale reflecting Brownian motion (RBM) in a d-dimensional box under a heavy traffic condition. The conventional continuous mapping approach does not apply here because the solution to our Skorohod problem may not be unique. Our proof relies heavily on a uniform oscillation result for solutions to a family of Skorohod problems. The oscillation result is proved in a general form that may be of independent interest. It has the potential to be used as an important ingredient in establishing heavy traffic limit theorems for general finite buffer networks. This revised version was published online in June 2006 with corrections to the Cover Date.     

Positive recurrence for reflecting Brownian motion in?higher dimensions

Semimartingale reflecting Brownian motions (SRBMs) are diffusion processes with state space the d-dimensional nonnegative orthant, in the interior of which the processes evolve according to a Brownian motion, and that reflect against the boundary in a specified manner. A standard problem is to determine under what conditions the process is positive recurrent. Necessary and sufficient conditions for positive recurrence are easy to formulate in d=2, but not in d??3. Fluid paths are solutions of deterministic equations that correspond to the random equations of the SRBM. A standard result of Dupuis and Williams (in Ann. Probab. 22:680?C702, 1994) states that when every fluid path associated with the SRBM is attracted to the origin, the SRBM is positive recurrent. Employing this result, El Kharroubi et al. (in Stoch. Stoch. Rep. 68:229?C253, 2000; Math. Methods Oper. Res. 56:243?C258, 2002) gave sufficient conditions involving fluid paths for positive recurrence of SRBM in d=3. Here, we discuss two recent results regarding necessary conditions for positive recurrence of SRBM in d??3. Bramson et al. (in Ann. Appl. Probab. 20:753?C783, 2010) showed that the conditions in El Kharroubi et al. (Math. Methods Oper. Res. 56:243?C258, 2002) are, in fact, necessary in d=3. On the other hand, Bramson (in Ann. Appl. Probab., to appear, 2011) provided a family of positive recurrent SRBMs, in d??6, with linear fluid paths that diverge to infinity. The latter result shows in particular that the converse of the Dupuis?CWilliams result does not hold.