Busy period analysis for <Emphasis Type="Italic">M</Emphasis>/<Emphasis Type="Italic">PH</Emphasis>/1 queues with workload dependent balking

We consider an M/PH/1 queue with workload-dependent balking. An arriving customer joins the queue and stays until served if and only if the system workload is no more than a fixed level at the time of his arrival. We begin by considering a fluid model where the buffer content changes at a rate determined by an external stochastic process with finite state space. We derive systems of first-order linear differential equations for the mean and LST (Laplace-Stieltjes Transform) of the busy period in this model and solve them explicitly. We obtain the mean and LST of the busy period in the M/PH/1 queue with workload-dependent balking as a special limiting case of this fluid model. We illustrate the results with numerical examples.      

The advantage of small machines in a stochastic fluid production process

We consider a stochastic fluid production model, where m machines which are subject to breakdown and repair, produce a fluid at ratep > 0 per machine if it is working. This fluid is fed into an infinite buffer with stochastic output rate. Under the assumption that the machine processes are independent and identically distributed, we prove that the buffer content at timet is less or equal in the increasing convex ordering to the buffer content at time t of a model withm m machines and production ratep =m/m p. This formulation includes a conjecture posed by Mitra [6]. More-over, it is shown how to extend this result to Brownian flow systems, systems obtained by diffusion approximation and simple stochastic flow networks like tandem buffer and assembly systems.     

M-Estimation for Discretely Observed Ergodic Diffusion Processes with Infinitely Many Jumps

We study parametric inference for multidimensional stochastic differential equations with jumps from some discrete observations. We consider a case where the structure of jumps is mainly controlled by a random measure which is generated by a Lévy process with a Lévy measure f_θ(z)dz, and we admit the case ∫ f_θ(z)dz = ∞ in which infinitely many small jumps occur even in any finite time intervals. We propose an estimating function under this complicated situation and show the consistency and the asymptotic normality. Although the estimators in this paper are not completely efficient, the method can be applied to comparatively wide class of stochastic differential equations, and it is easy to compute the estimating equations. Therefore, it may be useful in applications. We also present some simulation results for some simple models. Final version 25 December 2004     

Steady State Analysis of Finite Fluid Flow Models Using Finite QBDs

The Markov modulated fluid model with finite buffer of size β is analyzed using a stochastic discretization yielding a sequence of finite waiting room queueing models with iid amounts of work distributed as exp (nλ). The n-th approximating queue’s system size is bounded at a value q_n such that the corresponding expected amount of work q_n/(nλ) → β as n → ∞. We demonstrate that as n → ∞, we obtain the exact performance results for the finite buffer fluid model from the processes of work in the system for these queues. The necessary (strong) limit theorems are proven for both transient and steady state results. Algorithms for steady state results are developed fully and illustrated with numerical examples.AMS subject classification: 60J25, 60K25, 60K15, 60K37This revised version was published online in June 2005 with corrected coverdate     

Queueing at large resources driven by long-tailed M/G/∞-modulated processes

We analyze the queue at a buffer with input comprising sessions whose arrival is Poissonian, whose duration is long-tailed, and for which individual session detail is modeled as a stochastic fluid process. We obtain a large deviation result for the buffer occupation in an asymptotic regime in which the arrival rate nr, service rate ns, and buffer level nb are scaled to infinity with a parameter n. This can be used to approximate resources which multiplex many sources, each of which only uses a small proportion of the whole capacity, albeit for long-tailed durations. We show that the probability of overflow in such systems is exponentially small in n, although the decay in b is slower, reflecting the long tailed session durations. The requirements on the session detail process are, roughly speaking, that it self-averages faster than the cumulative session duration. This does not preclude the possibility that the session detail itself has a long-range dependent behavior, such as fractional Brownian motion, or another long-tailed M/G/∞ process. We show how the method can be used to determine the multiplexing gain available under the constraint of small delays (and hence short buffers) for multiplexers of large aggregates, and to compare the differential performance impact of increased buffering as opposed to load reduction. This revised version was published online in June 2006 with corrections to the Cover Date.     

Optimal buffer size for a stochastic processing network in heavy traffic

We consider a one-dimensional stochastic control problem that arises from queueing network applications. The state process corresponding to the queue-length process is given by a stochastic differential equation which reflects at the origin. The controller can choose the drift coefficient which represents the service rate and the buffer size b>0. When the queue length reaches b, the new customers are rejected and this incurs a penalty. There are three types of costs involved: A “control cost” related to the dynamically controlled service rate, a “congestion cost” which depends on the queue length and a “rejection penalty” for the rejection of the customers. We consider the problem of minimizing long-term average cost, which is also known as the ergodic cost criterion. We obtain an optimal drift rate (i.e. an optimal service rate) as well as the optimal buffer size b ^*>0. When the buffer size b>0 is fixed and where there is no congestion cost, this problem is similar to the work in Ata, Harrison and Shepp (Ann. Appl. Probab. 15, 1145–1160, 2005). Our method is quite different from that of (Ata, Harrison and Shepp (Ann. Appl. Probab. 15, 1145–1160, 2005)). To obtain a solution to the corresponding Hamilton–Jacobi–Bellman (HJB) equation, we analyze a family of ordinary differential equations. We make use of some specific characteristics of this family of solutions to obtain the optimal buffer size b ^*>0. A.P. Weerasinghe’s research supported by US Army Research Office grant W911NF0510032.     

On bulk-service MAP/PH L,N /1/N G-Queues with repeated attempts

We consider a retrial queue with a finite buffer of size N, with arrivals of ordinary units and of negative units (which cancel one ordinary unit), both assumed to be Markovian arrival processes. The service requirements are of phase type. In addition, a PH^L,N bulk service discipline is assumed. This means that the units are served in groups of size at least L, where 1≤ L≤ N. If at the completion of a service fewer than L units are present at the buffer, the server switches off and waits until the buffer length reaches the threshold L. Then it switches on and initiates service for such a group of units. On the contrary, if at the completion of a service L or more units are present at the buffer, all units enter service as a group. Units arriving when the buffer is full are not lost, but they join a group of unsatisfied units called “orbit”. Our interest is in the continuous-time Markov chain describing the state of the queue at arbitrary times, which constitutes a level dependent quasi-birth-and-death process. We start by analyzing a simplified version of our queueing model, which is amenable to numerical calculation and is based on spatially homogeneous quasi-birth-and-death processes. This leads to modified matrix-geometric formulas that reveal the basic qualitative properties of our algorithmic approach for computing performance measures. AMS Subject Classification: Primary 60K25 Secondary 68M20 90B22.     

General Linear Quadratic Optimal Stochastic Control Problem Driven by a Brownian Motion and a Poisson Random Martingale Measure with Random Coefficients

In this article, we consider a linear-quadratic optimal control problem (LQ problem) for a controlled linear stochastic differential equation driven by a multidimensional Browinan motion and a Poisson random martingale measure in the general case, where the coefficients are allowed to be predictable processes or random matrices. By the duality technique, the dual characterization of the optimal control is derived by the optimality system (so-called stochastic Hamilton system), which turns out to be a linear fully coupled forward-backward stochastic differential equation with jumps. Using a decoupling technique, the connection between the stochastic Hamilton system and the associated Riccati equation is established. As a result, the state feedback representation is obtained for the optimal control. As the coefficients for the LQ problem are random, here, the associated Riccati equation is a highly nonlinear backward stochastic differential equation (BSDE) with jumps, where the generator depends on the unknown variables K, L, and H in a quadratic way (see (5.9) herein). For the case where the generator is bounded and is linearly dependent on the unknown martingale terms L and H, the existence and uniqueness of the solution for the associated Riccati equation are established by Bellman's principle of quasi-linearization.     

Stochastic integration with respect to q Brownian motion

 We develop a stochastic integration with respect to a q-Brownian motion (for ), i.e. a non commutative process where the operator a _t and its adjoint fulfill the q commutation relation ; under the vacuum state expectation. We show that this process enjoys a predictable representation type property. Received: 15 February 2002 / Revised version: 25 May 2002 / Published online: 30 September 2002 Mathematics Subject Classification (2000): 60H05, 46L50, 81S25     

Production-inventory systems in stochastic environment and stochastic lead times

We consider a production-inventory system where the production and demand rates are modulated by a finite state Continuous Time Markov Chain (CTMC). When the inventory position (inventory on hand – backorders+inventory on order) falls to a reorder point r, we place an order of size q from an external supplier. We consider the case of stochastic leadtimes, where the leadtimes are i.i.d. exponential(μ) random variables, and orders may or may not be allowed to cross. We derive the distribution of the inventory level, and analyze the long run holding, backlogging, and ordering cost rate per unit time. We use simulation to study the sensitivity of the system to the distribution of the lead times.     

A queueing system with linear repeated attempts,bernoulli schedule and feedback

We analyse a single-server retrial queueing system with infinite buffer, Poisson arrivals, general distribution of service time and linear retrial policy. If an arriving customer finds the server occupied, he joins with probabilityp a retrial group (called orbit) and with complementary probabilityq a priority queue in order to be served. After the customer is served completely, he will decide either to return to the priority queue for another service with probability ϑ or to leave the system forever with probability =1−ϑ, where 0≤ϑ<1. We study the ergodicity of the embedded Markov chain, its stationary distribution function and the joint generating function of the number of customers in both groups in the steady-state regime. Moreover, we obtain the generating function of system size distribution, which generalizes the well-knownPollaczek-Khinchin formula. Also we obtain a stochastic decomposition law for our queueing system and as an application we study the asymptotic behaviour under high rate of retrials. The results agree with known special cases. Finally, we give numerical examples to illustrate the effect of the parameters on several performance characteristics.     

Modelling the dynamics of stochastic local search on <Emphasis Type="Italic">k</Emphasis>-<Emphasis Type="SmallCaps">sat</Emphasis>

A new analytical tool is presented to provide a better understanding of the search space of k-sat. This tool, termed the local value distribution , describes the probability of finding assignments of any value q′ in the neighbourhood of assignments of value q. The local value distribution is then used to define a Markov model to model the dynamics of a corresponding stochastic local search algorithm for k-sat. The model is evaluated by comparing the predicted algorithm dynamics to experimental results. In most cases the fit of the model to the experimental results is very good, but limitations are also recognised.     

Discrete and Continuous Time Modulated Random Walks with Heavy-Tailed Increments

We consider a modulated process S which, conditional on a background process X, has independent increments. Assuming that S drifts to −∞ and that its increments (jumps) are heavy-tailed (in a sense made precise in the paper), we exhibit natural conditions under which the asymptotics of the tail distribution of the overall maximum of S can be computed. We present results in discrete and in continuous time. In particular, in the absence of modulation, the process S in continuous time reduces to a Lévy process with heavy-tailed Lévy measure. A central point of the paper is that we make full use of the so-called “principle of a single big jump” in order to obtain both upper and lower bounds. Thus, the proofs are entirely probabilistic. The paper is motivated by queueing and Lévy stochastic networks.     

On Hitting Times and Fastest Strong Stationary Times for Skip-Free and More General Chains

An (upward) skip-free Markov chain with the set of nonnegative integers as state space is a chain for which upward jumps may be only of unit size; there is no restriction on downward jumps. In a 1987 paper, Brown and Shao determined, for an irreducible continuous-time skip-free chain and any d, the passage time distribution from state 0 to state d. When the nonzero eigenvalues ν _j of the generator on {0,…,d}, with d made absorbing, are all real, their result states that the passage time is distributed as the sum of d independent exponential random variables with rates ν _j . We give another proof of their theorem. In the case of birth-and-death chains, our proof leads to an explicit representation of the passage time as a sum of independent exponential random variables. Diaconis and Miclo recently obtained the first such representation, but our construction is much simpler. We obtain similar (and new) results for a fastest strong stationary time T of an ergodic continuous-time skip-free chain with stochastically monotone time-reversal started in state 0, and we also obtain discrete-time analogs of all our results. In the paper’s final section we present extensions of our results to more general chains. Research supported by NSF grant DMS–0406104, and by The Johns Hopkins University’s Acheson J. Duncan Fund for the Advancement of Research in Statistics.     

A two-stage stochastic integer programming approach as a mixture of Branch-and-Fix Coordination and Benders Decomposition schemes

We present an algorithmic approach for solving two-stage stochastic mixed 0–1 problems. The first stage constraints of the Deterministic Equivalent Model have 0–1 variables and continuous variables. The approach uses the Twin Node Family (TNF) concept within the so-called Branch-and-Fix Coordination algorithmic framework to satisfy the nonanticipativity constraints, jointly with a Benders Decomposition scheme to solve a given LP model at each TNF integer set. As a pilot case, the structuring of a portfolio of Mortgage-Backed Securities under uncertainty in the interest rate path on a given time horizon is used. Some computational experience is reported.     

Block-Structured Fluid Queues Driven by QBD Processes

Abstract

In this paper, a unified approach for studying block-structured fluid models is proposed by means of the RG-factorization. When the stochastic environment (or background) is assumed to be a quasi-birth-and death (QBD) process, with either infinitely many levels or finitely many levels, the Laplace transform for the stationary probability distribution of the buffer content is expressed in terms of the R-measure. At the same time, the Laplace-Stieltjes transforms for both the conditional distribution and the conditional mean of a first passage time in such a fluid queue are derived by the same approach.     

Complete classification of the positive solutions of −Δ<Emphasis Type="Italic">u</Emphasis> + <Emphasis Type="Italic">u</Emphasis><Superscript><Emphasis Type="Italic">q</Emphasis></Superscript>

We study the equation −Δu + u ^q = 0, q > 1, in a bounded C ² domain Ω ⊂ ℝ ^N . A positive solution of the equation is moderate if it is dominated by a harmonic function and σ-moderate if it is the limit of an increasing sequence of moderate solutions. It is known that in the subcritical case, 1 < q <, q _c = (N + 1)/(N − 1), every positive solution is σ-moderate [32]. More recently, Dynkin proved, by probabilistic methods, that this remains valid in the supercritical case for q ≤ 2, [15]. The question remained open for q > 2. In this paper, we prove that for all q ≥ q _c , every positive solution is σ-moderate. We use purely analytic techniques, which apply to the full supercritical range. The main tools come from linear and non-linear potential theory. Combined with previous results, our result establishes a one-to-one correspondence between positive solutions and their boundary traces in the sense of [36].     

On the size of the Jacobians of curves over finite fields

Abdract  Given a smooth curve of genus g ≥ 1 which admits a smooth projective embedding of dimension m over the ground field of q elements, we obtain the asymptotic formula q ^g+o(g) for the size of set of the -rational points on its Jacobian in the case when m and q are bounded and g → ∞. We also obtain a similar result for curves of bounded gonality. For example, this applies to the Jacobian of a hyperelliptic curve of genus g → ∞.      

Stochastic games on a product state space: the periodic case

We examine so-called product-games. These are n-player stochastic games played on a product state space S ¹ × ... × S ⁿ , in which player i controls the transitions on S ⁱ . For the general n-player case, we establish the existence of 0-equilibria. In addition, for the case of two-player zero-sum games of this type, we show that both players have stationary 0-optimal strategies. In the analysis of product-games, interestingly, a central role is played by the periodic features of the transition structure. Flesch et al. (Math Oper Res 33, 403–420, 2008) showed the existence of 0-equilibria under the assumption that, for every player i, the transition structure on S ⁱ is aperiodic. In this article, we examine product-games with periodic transition structures. Even though a large part of the approach in Flesch et al. (Math Oper Res 33, 403–420, 2008) remains applicable, we encounter a number of tricky problems that we have to address. We provide illustrative examples to clarify the essence of the difference between the aperiodic and periodic cases.     

Estimation of Parameters for Diffusion Processes with Jumps from Discrete Observations

In this paper, we consider a multidimensional diffusion process with jumps whose jump term is driven by a compound Poisson process. Let a(x,θ) be a drift coefficient, b(x,σ) be a diffusion coefficient respectively, and the jump term is driven by a Poisson random measure p. We assume that its intensity measure q^θ has a finite total mass. The aim of this paper is estimating the parameter α = (θ,σ) from some discrete data. We can observe n + 1 data at t_iⁿ = ih_n, . We suppose h_n → 0, nh_n → ∞, nh_n² → 0. Final version 20 December 2004