Light traffic for workload in queues

General exact light traffic limit theorems are given for the distribution of steadystate workloadV, in open queueing networks having as input a general stationary ergodic marked point process {(t _n ,K _n )n0 (where t_n denotes the arrival time and K_n the routing and service times of the nth customer). No independence assumptions of any kind are required of the input. As the light traffic regime, it is only required that the Palm distribution for the exogenous interarrival time converges weakly to infinity (while the service mechanism is not allowed to change much). As is already known in the context of a single-server queue, work is much easier to deal with mathematically in light traffic than is customer delayD, and consequently, our results are far more general than existing results forD. We obtain analogous results for multi-channel and infinite-channel queues. In the context of open queueing networks, we handle both the total workload in the network as well as the workload at isolated nodes.Research supported in part by the Japan Society for the Promotion of Science during the author's fellowship in Tokyo, and by NSF Grant DDM 895 7825.     

On the Loday symbol in the Deligne-Beilinson cohomology

Let A be an algebraic smooth variety over , X ₀,..., X _n be global regular functions on A, be a global invertible regular function on X of value 1 on the divisor Y defined by X ₀ and Z denned by X ₁... X _n. Then the cup product {¦ _A–Z , X ₁,...,X _n} in the Deligne-Beilinson cohomology group H _D ⁿ⁺¹ (A - Z, Y; extends across Z to a so-called Loday symbol, denoted by {, X ₁,..., X_n}, in H _D ⁿ⁺¹ (A,Y,Z(n+1))In this article, we give explicit formulae for {X ₁, ..., X _n} as a ech cocycle. Thereby, one obtains a proof of Beilinson's formula for the evaluation of the Loday symbol along certain homology cycles.Supported by Heisenberg Programm, Max Planck Institut für Mathematik.     

Counting Cocomponents of a Topological Space

Dualizing the statement about a number of components of a topological space X, we say that, for a natural number n, the space X has at most n cocomponents if every continuous map f:X ⁿ⁺¹X factorizes through X ⁿ , i.e., f depends on at most n coordinates. We construct metrizable spaces X ₁,X ₂,X ₃ such that(1) X ₁ does not have finitely many cocomponents but every continuous map X ₁ X ₁ depends only on finitely many coordinates;(2) X ₂=A×B for rigid spaces A,B and there is a continuous map X ₂ X ₂ depending on all coordinates;(3) X ₃(n) has precisely n cocomponents but it cannot be expressed as A×B with |A|>1 and |B|>1.     

Recurrent random walks in nonnegative matrices II

Summary In this paper, we continue the study undertaken in our earlier paper [M1]. One of the main results here can be described as follows. LetX ₀,X ₁, ... be a sequence of iid random affine maps from (R ⁺) ^d into itself. Let us write:W _n X _n X _n –1...X ₀ andZ _n X ₀ X ₁...X _n , where composition of maps is the rule of multiplication. By the attractorA(u),u(R ⁺) ^d , we mean the setA u={y(R⁺)^d:P(W_n uN i.o.) > 0 for every openN containingy}. It is shown that the attractorA(u), under mild conditions, is the support of a stationary probability measure, when the random walk (Z _n ) has at least one recurrent state.     

Stochastic approximation from ergodic sample for linear regression

Summary Robbins-Monro stochastic approximation procedure is used to solve the linear equation Ax=y in Hilbert space, where y _n and A _n are estimators such that their arithmetic means converge to y and A, respectively. Under some additional conditions it is shown that X _n goes to the unique solution of this equation.     

The martin boundary for general isotropic random walks in a tree

LetT=T _a+1 be a homogeneous tree of degreea+1. Anisotropic random walk onT is a Markov chain{X _n } such thatp(x,y)=A _d =P[X _n+1=y|X _n=x] depends only on the number of edgesd=d(x,y) betweenx andy. Assuming only thatA _d>0 for some oddd, the Martin boundary is characterized, and it is proven that nonnegativep-harmonic functions onT are the same as nearest-neighbor harmonic functions, i.e.,u(x)= _yT p(x,y)u(y) for allx T if and only ifu(x)= _d(x,y)=1 u(y)/(a)+1 for allx T. Examples are given where the Martin boundary forp is not the same as in the nearest-neighbor case. A non-Abelian renewal theory is developed such that Tauberian conditions onA _d ^* =P[d(X ₁,x)=d|X]₀=x] guarantee the equivalence of the Martin boundary. For example, the Martin boundary and Martin kernel are the same forp as for nearest-neighbor random walk if dA _d ^* < or if lim supA _d+1 ^* /A _d ^* <–1. The same techniques show the existence of renewal sequences{u _n } such thatf _k+1/f _k<- for arbitrary >1 but limu _n+1/u _n does not exist.     

Central limit theorems in D[0, 1]

Summary Let X be a stochastic process with sample paths in the usual Skorohod space D[0, 1]. For a sequence {X _n} of independent copies of X, let S _n=X₁++X_n. Conditions which are either necessary or sufficient for the weak convergence of n ^–1/2(S _n–ES_n) to a Gaussian process with sample paths in D[0, 1] are discussed. Stochastically continuous processe are considered separately from those with fixed discontinuities. A bridge between the two is made by a Decomposition central limit theorem.     

The exact density function of the ratio of two dependent linear combinations of chi-square variables

A computable expression is derived for the raw moments of the random variableZ=N/D whereN= ₁ ⁿ m _iX_i+ _n ^+1s m _iX_i,D= _n ^+1s l _iX_i+ _s ^+1r n _iX_i, and theX _i's are independently distributed central chi-square variables. The first four moments are required for approximating the distribution ofZ by means of Pearson curves. The exact density function ofZ is obtained in terms of sums of generalized hypergeometric functions by taking the inverse Mellin transform of theh-th moment of the ratioN/D whereh is a complex number. The casen=1,s=2 andr=3 is discussed in detail and a general technique which applies to any ratio having the structure ofZ is also described. A theoretical example shows that the inverse Mellin transform technique yields the exact density function of a ratio whose density can be obtained by means of the transformation of variables technique. In the second example, the exact density function of a ratio of dependent quardratic forms is evaluated at various points and then compared with simulated values.     

Cyclic homology and the Macdonald conjectures

Summary LetA+(k) denote the ring [t]/t ^k+1 and letG be a reductive complex Lie algebra with exponentsm ₁, ...,m n. This paper concerns the Lie algebra cohomology ofGA ₊(k) considered as a bigraded algebra (here one of the gradings is homological degree and the other, which we callweight, is inherited from the obvious grading ofGA ₊(k)). We conjecture that this Lie algebra cohomology is an exterior algebra withk+1 generators of homological degree 2m _s +1 fors=1,2, ...,n. Of thesek+1 generators of degree 2m _s +1, one has weight 0 and the others have weights (k+1)m _s +t fort=1,2, ...,k.It is shown that this conjecture about the Lie algebra cohomology of A ₊(k) implies the Macdonald root system conjectures. Next we consider the case thatG is a classical Lie algebra with root systemA _n ,B _n ,C _n , orD _n. It is shown that our conjecture holds in the limit onn asn approaches infinity which amounts to the computation of the cyclic and dihedral cohomologies ofA+(k). Lastly we discuss the relevance of this limiting case to the case of finiten in this situation.Partially supported by NSF grant number MCS-8401718 and a Bantrell Fellowship     

Rates in the empirical bayes estimation problem with non-identical components

This paper considers empirical Bayes estimation of the mean θ of the univariate normal densityf ₀ with known variance where the sample sizesm(n) may vary with the component problems but remain bounded by <∞. Let {(θ _n ,X _n =(X _n,1,...,X _{n, m(n)} ))} be a sequence of independent random vectors where theθ _n are unobservable and iidG and, givenθ _n =θ has densityf _θ ^m(n) . The first part of the paper exhibits estimators for the density of and its derivative whose mean-squared errors go to zero with rates and respectively. LetR ^m(n+1)(G) denote the Bayes risk in the squared-error loss estimation ofθ _n+1 usingX _n+1. For given 0<a<1, we exhibitt _n (X₁,...,X _n ;X _n+1) such that . forn>1 under the assumption that the support ofG is in [0, 1]. Under the weaker condition that E[|θ|^2+γ]<∞ for some γ>0, we exhibitt _n ^* (X ₁,...,X _n ;X _n+1) such that forn>1.     

The strong approximation of extremal processes

Summary If X ₁, X ₂, ..., are i.i.d. random variables and Y _n =Max(X ₁, ..., X _n ); if for some sequences A _n , B_n, n=1, 2, ..., E _n (t)=A_nY_[nt]+B_n is such that E _n (1) weakly converges to a non degenerate limit distribution, then we prove that it is possible to construct a sequence of replicates of extremal processes E ⁽ⁿ⁾(t) on the same probability space, such that d(E _n (.), E ⁽ⁿ⁾(.))0 a.s., with the Levy metric. We give the rates of consistency of the approximations.     

Sample-path analysis of general arrival queueing systems with constant amount of work for all customers

We consider a discrete-time queueing system where the arrival process is general and each arriving customer brings in a constant amount of work which is processed at a deterministic rate. We carry out a sample-path analysis to derive an exact relation between the set of system size values and the set of waiting time values over a busy period of a given sample path. This sample-path relation is then applied to a discrete-time $G/D/c$ queue with constant service times of one slot, yielding a sample-path version of the steady-state distributional relation between system size and waiting time as derived earlier in the literature. The sample-path analysis of the discrete-time system is further extended to the continuous-time counterpart, resulting in a similar sample-path relation in continuous time.     

A Geometric Problem and the Hopf Lemma. Ⅱ

Abstract A classical result of A. D. Alexandrov states that a connected compact smooth n-dimensional manifold without boundary, embedded in ℝⁿ⁺¹, and such that its mean curvature is constant, is a sphere. Here we study the problem of symmetry of M in a hyperplane X_n+1 =constant in case M satisfies: for any two points (X′,X_n+1), on M, with , the mean curvature at the first is not greater than that at the second. Symmetry need not always hold, but in this paper, we establish it under some additional conditions. Some variations of the Hopf Lemma are also presented. Several open problems are described. Part I dealt with corresponding one dimensional problems. (Dedicated to the memory of Shiing-Shen Chern) * Partially supported by NSF grant DMS-0401118.     

Stability of Earliest-Due-Date,First-Served Queueing Networks

We study multiclass queueing networks with the earliest-due-date, first-served (EDDFS) discipline. For these networks, the service priority of a customer is determined, upon its arrival in the network, by an assigned random due date. First-in-system, first-out queueing networks, where a customer's priority is given by its arrival time in the network, are a special case. Using fluid models, we show that EDDFS queueing networks, without preemption, are stable whenever the traffic intensity satisfies _j <1 for each station j.     

具有可变到达率的多重休假Geo~(λ_1,λ_2)/G/1排队分析

本文考虑顾客到达与服务员休假相关的多重休假离散时间排队系统,用更新过程及u-变换分析了系统的队长性质.分别得到系统在三种时点(n~-,n~+,n)处的队长分布的递推解,进而揭示了在不同到达率条件下系统队长分布不再具有随机分解特性,得到了系统在四种时点(n~-,n~+,n,离去时点D_n)处稳态队长分布的重要关系(不同于连续时间排队系统).     

An explicit calculation of the mean of the perimeter of the convex hull of a plane random walk

If (X _n ) _n ⁼¹ is a sequence of i.i.d. random variables in the Euclidean plane such that we compute the mean of the perimeter of theconvex hull ofX ₁++X _k; 0kn}.     

Theorems of the Alternative for Cones and Lyapunov Regularity of Matrices

Standard facts about separating linear functionals will be used to determine how two cones C and D and their duals C* and D* may overlap. When T: V W is linear and K V and D W are cones, these results will be applied to C = T(K) and D, giving a unified treatment of several theorems of the alternate which explain when C contains an interior point of D. The case when V = W is the space H of n × n Hermitian matrices, D is the n × n positive semidefinite matrices, and T(X) = AX + X* A yields new and known results about the existence of block diagonal X's satisfying the Lyapunov condition: T(X) is an interior point of D. For the same V, W and D, T(X) = X – B* XB will be studied for certain cones K of entry-wise nonnegative X's.     

Augmentation quotients for burnside rings of generalized dihedral groups

Let H be a finite abelian group of odd order, D be its generalized dihedral group, i.e., the semidirect product of C₂ acting on H by inverting elements, where C₂ is the cyclic group of order two. Let Ω (D) be the Burnside ring of D, Δ(D) be the augmentation ideal of Ω (D). Denote by Δⁿ(D) and Q_n(D) the nth power of Δ(D) and the nth consecutive quotient group Δⁿ(D)/Δⁿ⁺¹(D), respectively. This paper provides an explicit Z-basis for Δⁿ(D) and determines the isomorphism class of Q_n(D) for each positive integer n.     

An extremal problem related to probability

Summary We consider a walk from a stateA ₁ to a stateA _n+1 in which the probability of remaining atA _i isp _i , and the probability of progressing fromA _i toA _i+1 is 1 –p _i . The probabilityW _nk of reachingA _n+1 fromA ₁ in exactlyn + k steps can then be expressed as a polynomial of degreen + k in then variablesp ₁,,p _n . We determine the maximum value ofW _nk and the (unique) choice (p ₁,,p _n ) for which this extremum occurs.Dedicated to Professor Otto Haupt with best wishes on his 100th birthday     

Geometry of \mathbb{Z}^d and the Central Limit Theorem for Weakly Dependent Random Fields

We study the asymptotic distribution of where A is a subset of , A _N = A[–N, N] ^d , v(A) = lim _N card(A _N) (2N+1) ^–d (0, 1) and X is a stationary weakly dependent random field. We show that the geometry of A has a relevant influence on the problem. More specifically, S _N(A, X) is asymptotically normal for each X that satisfies certain mixting hypotheses if and only if has a limit F(n; A) as N for each . We also study the class of sets A that satisfy this condition.