bluuebunny/crossref_metadata_2025 huggingface dataset:
On the optimal composition of electricity grids with unreliable units: solvable models
Authors: Gates D. J.
Published: April 2006

For a large electricity grid comprising many units (plants) of various types, such as coal, oil, nuclear, hydro, etc., with known unreliabilities (outage rates) we study the optimal (i.e. the cheapest) total capacity, or numbers, of each type of unit. Existing treatments of the problem involve numerical methods and approximations of unknown accuracy. For a range of cases, we find explicit solutions. This extends the known explicit solutions, which are confined to completely reliable units. The cases we analyse are (I) a demand (load) which has a shifted Rayleigh distribution—a good approximation to the real load-duration curve—with some restriction on reliability (big units are more reliable) and (II) an exponential load distribution—which is unrealistic—with no restrictions on reliability. In both cases, the solutions reduce to transformed versions of the exact solutions for totally reliable units and, like the latter, can be exhibited by means of a cost polygon.
Computing optimal (s, S) policies in inventory models with continuous demands
Authors: Federgruen A. , Zipkin P.
Published: April 2006

Special algorithms have been developed to compute an optimal (s, S) policy for an inventory model with discrete demand and under standard assumptions (stationary data, a well-behaved one-period cost function, full backlogging and the average cost criterion). We present here an iterative algorithm for continuous demand distributions which avoids any form of prior discretization. The method can be viewed as a modified form of policy iteration applied to a Markov decision process with continuous state space. For phase-type distributions, the calculations can be done in closed form.
A note on Markov branching processes
Authors: Hoppe Fred M.
Published: April 2006

We present a simple proof of Zolotarev’s representation for the Laplace transform of the normalized limit of a Markov branching process and relate it to the Harris representation.
Asymptotic results for the extinction time of Markov branching processes allowing emigration, I. Random walk decrements
Authors: Pakes Anthony G.
Published: April 2006

The mathematical model is a Markov branching process which is subjected to catastrophes or large-scale emigration. Catastrophes reduce the population size by independent and identically distributed decrements, and two mechanisms for generating catastrophe epochs are given separate consideration. These are that catastrophes occur at a rate proportional to population size, and as an independent Poisson process.

The paper studies some properties of the time to extinction of the modified process in those cases where extinction occurs almost surely. Particular attention is given to limit theorems and the behaviour of the expected extinction time as the initial population size grows. These properties are contrasted with known properties for the case when there is no catastrophe component.
Bellman-Harris branching processes with a special type of state-dependent immigration
Authors: Mitov K. V. , Yanev N. M.
Published: April 2006

We investigate critical Bellman-Harris processes which allow immigration of new particles whenever the population size is 0. Under some special conditions on the immigration component the asymptotic behaviour of the probability of extinction is obtained and limit theorems are also proved.
Optimal time to repair a broken server
Authors: Federgruen Awi , So Kut C.
Published: April 2006

We consider a single-server queueing system with Poisson arrivals and general service times. While the server is up, it is subject to breakdowns according to a Poisson process. When the server breaks down, we may either repair the server immediately or postpone the repair until some future point in time. The operating costs of the system include customer holding costs, repair costs and running costs. The objective is to find a corrective maintenance policy which minimizes the long-run average operating costs of the system. The problem is formulated as a semi-Markov decision process. Under some mild conditions on the repair time and service time distributions and the customer holding cost rate function, we prove that there exists an optimal stationary policy which is characterized by a single threshold parameter: a repair is initiated if and only if the number of customers in the system exceeds this threshold. We also show how the average cost under such policies may be computed and how an optimal policy may efficiently be determined.
Constrained admission control to a queueing system
Authors: Hordijk Arie , Spieksma Flos
Published: April 2006

We consider an exponential queue with arrival and service rates depending on the number of jobs present in the queue. The queueing system is controlled by restricting arrivals. Typically, a good policy should provide a proper balance between throughput and congestion. A mathematical model for computing such a policy is a Markov decision chain with rewards and a constrained cost function. We give general conditions on the reward and cost function which guarantee the existence of an optimal threshold or thinning policy. An efficient algorithm for computing an optimal policy is constructed.
A limit theorem for spatial point processes
Authors: Ellis Steven P.
Published: April 2006

Spatial point processes are considered whose points are subjected to certain classes of affine transformations indexed by some variable,T.Under some hypotheses, for largeTintegrals with respect to such a point process behave approximately as if the process were Poisson. Under stronger hypotheses, the transformed process converges as a process to a Poisson process. The result gives the asymptotic distribution of certain density estimates.
Autoregressive moving-average processes with negative-binomial and geometric marginal distributions
Authors: McKenzie Ed
Published: April 2006

Some simple models are described which may be used for the modelling or generation of sequences of dependent discrete random variates with negative binomial and geometric univariate marginal distributions. The models are developed as analogues of well-known continuous variate models for gamma and negative exponential variates. The analogy arises naturally from a consideration of self-decomposability for discrete random variables. An alternative derivation is also given wherein both the continuous and the discrete variate processes arise simultaneously as measures on a process of overlapping intervals. The former is the process of interval lengths and the latter is a process of counts on these intervals.
Continuous-time allocation indices and their discrete-time approximation
Authors: Eplett W. J. R.
Published: April 2006

The theory of allocation indices for defining the optimal policy in multi-armed bandit problems developed by Gittins is presented in the continuous-time case where the projects (or ‘arms’) are strong Markov processes. Complications peculiar to the continuous-time case are discussed. This motivates investigation of whether approximation of the continuous-time problems by discrete-time versions provides a valid technique with convergent allocation indices and optimal expected rewards. Conditions are presented under which the convergence holds.
An inequality from genetics
Authors: Seneta E.
Published: April 2006

A class of fitness matrices whose parameters may be varied to give differing stability structure is shown by Chebyshev&s covariance inequality to possess a variance lower bound for the change in mean fitness.
Approximate exit probabilities for a Brownian bridge on a short time interval, and applications
Authors: Lerche H. R. , Siegmund D.
Published: April 2006

Let T be the first exit time of Brownian motion W(t) from a region ℛ in d-dimensional Euclidean space having a smooth boundary. Given points ξ0 and ξ1 in ℛ, ordinary and large-deviation approximations are given for Pr{T < ε |W(0) = ξ0, W(ε) = ξ 1} as ε → 0. Applications are given to hearing the shape of a drum and approximating the second virial coefficient.
On the evaluation of first-passage-time probability densities via non-singular integral equations
Authors: Giorno V. , Nobile A. G. , Ricciardi L. M. , Sato S.
Published: April 2006

The algorithm given by Buonocore et al. [1] to evaluate first-passage-time p.d.f.’s for Wiener and Ornstein–Uhlenbeck processes through a time-dependent boundary is extended to a wide class of time-homogeneous one-dimensional diffusion processes. Several examples are thoroughly discussed along with some computational results.
Random tessellations in ℝd
Authors: Møller J.
Published: April 2006

This paper presents a general theory of random tessellations (i.e. stochastic aggregates of disjoint and space-filling cells) ind-dimensional Euclidean space. Some particular models of random tessellations are discussed in detail.
Continuous production/inventory model with analogy to certain queueing and dam models
Authors: Perry David , Levikson Benny
Published: April 2006

We consider two storage/production systems in which items are produced continuously over time with fixed rate. In the first system items have infinite lifetime, while in the second system the lifetime of the items are finite and fixed. The inventory level distributions and other important functionals associated with these storage systems are derived. This derivation is accomplished by an analogy existing between the storage systems and certain queueing systems and a finite dam model. Optimization problems connected with these systems are also considered.
The ages of alleles and a coalescent
Authors: Donnelly Peter , Tavaré Simon
Published: April 2006

A new coalescent is introduced to study the genealogy of a sample from the infinite-alleles model of population genetics. This coalescent also records the age ordering of alleles in the sample. The distribution of this process is found explicitly for the Moran model, and is shown to be robust for a wide class of reproductive schemes.

Properties of the ages themselves and the relationship between ages and class sizes then follow readily.
Weak convergence of sequences of semimartingales with applications to multitype branching processes
Authors: Joffe A. , Metivier M.
Published: April 2006

The paper is devoted to a systematic discussion of recently developed techniques for the study of weak convergence of sequences of stochastic processes. The methods described make essential use of the semimartingale structure of the processes. Sufficient conditions for tightness including the results of Rebolledo are derived. The techniques are applied to a special class of processes, namely theD-semimartingales. Applications to multitype branching processes are given.
Connecting reversible Markov processes
Authors: Pollett P. K.
Published: April 2006

We provide a framework for interconnecting a collection of reversible Markov processes in such a way that the resulting process has a product-form invariant measure with respect to which the process is reversible. A number of examples are discussed including Kingman&s reversible migration process, interconnected random walks and stratified clustering processes.
Extrema and level crossings of χ2 processes
Authors: Aronowich Michael , Adler Robert J.
Published: April 2006

We study the sample path behaviour of χ2 processes in the neighbourhood of their level crossings and extrema via the development of Slepian model processes. The results, aside from being of particular interest in the study of χ2 processes, have a general interest insofar as they indicate which properties of Gaussian processes (which have been heavily researched in this regard) are mirrored or lost when the assumption of normality is not made. We place particular emphasis on the behaviour of χ2 processes at both high and low levels, these being of considerable practical importance. We also extend previous results on the asymptotic Poisson form of the point process of high maxima to include also low minima (which are in a different domain of attraction) thus closing a gap in the theory of χ2 processes.
An infinite dam with random withdrawal policy
Authors: Khan M. S. Ali
Published: April 2006

Most work in the theory of dams has dealt with deterministic withdrawals. Some more recent work, begun by Moran (1969), has been devoted to conditionally deterministic withdrawals which depend on the content of the dam, or in some cases on the last input. We consider in this paper an infinite dam fed by discrete additive inputs, under a totally random withdrawal policy. Explicit expressions are obtained for the time-dependent content distributions. Probabilities of emptiness are computed and stationary results are derived.
Utilisation de densites des premier passage en commande optimale stochastique
Authors: Lefebvre Mario
Published: April 2006

A theorem that gives the optimal control of Gaussian processes using the mathematical expectation of a function of the time and the place where the uncontrolled processes hit the boundary of the stopping region for the first time is proved. The result obtained in this note is an extension of a theorem due to Whittle.
The new better than used failure rate class of life distribution
Authors: Abouammoh A. M. , Ahmed A. N.
Published: April 2006

A new concept of ageing distribution, namely new better than used in failure rate (NBUFR), is introduced. Different properties of the NBUFR class and its dual class are presented. Its relations to other classes of life distributions are investigated. Finally, NBUFR survival under shock models is discussed.
Recent investigations involving stochastic population models
Authors: Bartlett M. S.
Published: April 2006

After some introductory general remarks on recent investigations involving population models, two broad classes of stochastic model are discussed further, viz. spatial nearest-neighbour lattice models and doubly stochastic models.

In Section 1 of the paper, the first type of model is considered primarily for its relevance to recent work by the author and others affecting the practical design and analysis of replicated field experiments.

In Section 2, doubly stochastic processes are discussed more theoretically, particularly models investigated recently by the author involving infinitesimal transition operators in continuous time linear in the (variable) parameters.

Some new numerical results on extinction and other ‘absorption' probabilities are presented; these are intended to throw further light on the extent to which the assumption of ‘white-noise' variability of the parameters can be a useful approximation to more realistic models.
System parameters governed by jump processes: a model for removal of air pollutants
Authors: Stein Michael
Published: April 2006

The asymptotic moments of the concentration of a pollutant subject to rainout and dry removal are given. Both the lengths of the wet and dry periods and the wet and dry removal rates are allowed to be random, although the removal rate is assumed to be fixed within any one wet or dry period. The results hold in a more general setting than removal processes, so its is hoped that they will be applicable to other problems.
Random flights on regular graphs
Authors: Takács Lajos
Published: April 2006

Let K be a finite graph with vertex set V = {x0, x1, …, xσ–1} and automorphism group G. It is assumed that G acts transitively on V. We can imagine that the vertices of K represent σ cities and a traveler visits the cities in a series of random flights. The traveler starts at a given city and in each flight, independently of the past journey, chooses a city at random as the destination. Denote by vn (n = 1, 2, …) the location of the traveler at the end of the nth flight, and by v0 the initial location. It is assumed that the transition probabilities P{vn = xj | vn–1 = xi}, xi ϵ V, xj ϵ V, do not depend on n and are invariant under the action of G on V. The main result of this paper consists in determining p(n), the probability that the traveler returns to the initial position at the end of the nth flight.
Immigration in the two-sex population process
Authors: Gani J. , Tin Pyke
Published: April 2006

Known results for the two-sex birth-death population process are extended to the case where immigration of females is allowed. It is shown that the methods used follow those for the standard birth, death and immigration process.
A unified approach to the distribution of total size and total area under the trajectory of infectives in epidemic models
Authors: Ball Frank
Published: April 2006

We provide a unified probabilistic approach to the distribution of total size and total area under the trajectory of infectives for a general stochastic epidemic with any specified distribution of the infectious period. The key tool is a Wald&s identity for the epidemic process. The generalisation of our results to epidemics spreading amongst a heterogeneous population is straightforward.
Inference for stationary random fields given Poisson samples
Authors: Karr Alan F.
Published: April 2006

Given ad-dimensional random field and a Poisson process independent of it, suppose that it is possible to observe only the location of each point of the Poisson process and the value of the random field at that (randomly located) point. Non-parametric estimators of the mean and covariance function of the random field—based on observation over compact sets of single realizations of the Poisson samples—are constructed. Under fairly mild conditions these estimators are consistent (in various senses) as the set of observation becomes unbounded in a suitable manner. The state estimation problem of minimum mean-squared error reconstruction of unobserved values of the random field is also examined.
Pure jump shock models in reliability
Authors: Drosen James W.
Published: April 2006

There are many examples of a device suffering damage from random environmental shocks. We model the damage level of such a device as a pure jump Markov process, where the incremental damage caused by a shock depends both on the magnitude of the shock and on the damage level just before the shock. We also look at the time until failure of the device, which occurs when the damage level exceeds a random threshold. The distribution of the failure time and the failure rate are examined, and conditions for the failure rate to be increasing or to have an increasing average are found.
The virtual waiting-time and related processes
Authors: Cox D. R. , Isham Valerie
Published: April 2006

The virtual waiting-time process of Takács is one of the simplest examples of a stochastic process with a continuous state space in continuous time in which jump transitions interrupt periods of deterministic decay. Properties of the process are reviewed, and the transient behaviour examined in detail. Several generalizations of the process are studied. These include two-sided jumps, periodically varying ‘arrival’ rate and the presence of a state-dependent decay rate; the last case is motivated by the properties of soil moisture in hydrology. Throughout, the emphasis is on the derivation of simple interpretable results.
Limit theorems for first-passage times in linear and non-linear renewal theory
Authors: Lalley S. P.
Published: April 2006

A local limit theorem foris obtained, whereτais the first time a random walkSnwith positive drift exceedsa.Applications to large-deviation probabilities and to the crossing of a non-linear boundary are given.
Symbolic computation and the diffusion of shapes of triads
Authors: Kendall Wilfrid S.
Published: April 2006

This paper introduces the use of symbolic computation (also known as computer algebra) in stochastic analysis and particularly in the Itô calculus. Two related examples are considered: the Clifford-Green theorem on random Gaussian triangles, and a generalization of the D. G. Kendall theorem on the kinematics of shape.

The Clifford–Green theorem gives a remarkable characterization of the joint distribution of the squared-side-lengths ofnindependent Gaussian points inn-space, namely that this distribution is that ofnindependent exponential random variablesconditionedto satisfy all the inequalities requisite if they are to arise as squared-side-lengths from a point-set inn-space. The D. G. Kendall theorem on the diffusion of shape identifies the statistics of the diffusion arising (under a time-change) as the shape of a triangle whose vertices diffuse by Brownian motion in 2-space or 3-space.

Symbolic Itô calculus is used to give a new proof of the Clifford-Green theorem, and to generalize the D. G. Kendall theorem to the case of triangles in higher-dimensional space whose vertices diffuse either according to Brownian motion or according to an Ornstein–Uhlenbeck process.
Bivariate exponential and geometric autoregressive and autoregressive moving average models
Authors: Block H. W. , Langberg N. A. , Stoffer D. S.
Published: April 2006

We present autoregressive (AR) and autoregressive moving average (ARMA) processes with bivariate exponential (BE) and bivariate geometric (BG) distributions. The theory of positive dependence is used to show that in various cases, the BEAR, BGAR, BEARMA, and BGARMA models consist of associated random variables. We discuss special cases of the BEAR and BGAR processes in which the bivariate processes are stationary and have well-known bivariate exponential and geometric distributions. Finally, we fit a BEAR model to a real data set.
Some ARMA models for dependent sequences of poisson counts
Authors: Mckenzie Ed
Published: April 2006

A family of models for discrete-time processes with Poisson marginal distributions is developed and investigated. They have the same correlation structure as the linear ARMA processes. The joint distribution ofnconsecutive observations in such a process is derived and its properties discussed. In particular, time-reversibility and asymptotic behaviour are considered in detail. A vector autoregressive process is constructed and the behaviour of its components, which are Poisson ARMA processes, is considered. In particular, the two-dimensional case is discussed in detail.
On a reduction principle in dynamic programming
Authors: Glazebrook K. D.
Published: April 2006

Whittle enunciated an important reduction principle in dynamic programming when he showed that under certain conditions optimal strategies for Markov decision processes (MDPs) placed in parallel to one another take actions in a way which is consistent with the optimal strategies for the individual MDPs. However, the necessary and sufficient conditions given by Whittle are by no means always satisfied. We explore the status of this computationally attractive reduction principle when these conditions fail.
A nucleation–growth process on the integers
Authors: Mellein Bernhard
Published: April 2006

We consider a Markov process with state space {0, 1}Zwhere Os become 1s irreversibly at rates which depend on whether none of a 0&s nearest neighbours (nucleation), its left-hand neighbour (right-hand growth), or its right-hand neighbour (left-hand growth) is in the 1-state. Furthermore, we assume that Os with both nearest neighbours in the 1-state remain in the 0-state forever and that at time 0 only the origin is in the 1-state. We determine the size distribution of the cluster (maximal sequence of 1s uninterrupted by Os) at the origin and the distribution of the time when its growth is stopped (by birth (nucleation) or competitive growth of neighbouring clusters). In the final state of the process, the spatial distribution of the (trapped) sites in the 0-state is considered. Some information on the size distribution of clusters well away from the cluster at the origin is obtained.
Poisson and extreme value limit theorems for Markov random fields
Authors: Berman Simeon M.
Published: April 2006

LetXt,be a Markov random field assuming values inRM.LetInbe a rectangular box inZmwith its center at 0 and corner points with coordinates±n.Let (An) be a sequence of measurable subsets ofRMsuch thatneighborhood oft) → 0, forn → ∞; and letfn(x) be the indicator ofAn.Under appropriate conditions on the nearest-neighbor distributions of (Xt), the conditional distribution ofgiven the values ofXs, forson the boundary ofIn, converges to the Poisson distribution. An immediate application is an extreme value limit theorem for a real-valued Markov random field.
Asymptotic analysis and computational methods for a class of simple, circuit-switched networks with blocking
Authors: Mitra Debasis
Published: April 2006

We consider the following circuit-switching problem which is one of the simplest possible extensions of the classical M/M/K/K model: there are p source centers connected to a hub by channels of various line-capacities and the hub is connected to a destination center by a common channel with its own line-capacity. A circuit requires a line from its source to the hub and another line from the hub to the destination. The holding times of circuits are independent, arbitrarily distributed random variables with means which depend on their source, and requests for circuits arrive in Poisson streams. Blocked calls are cleared. The problem is to calculate the blocking probabilities at each of the sources. The formal solution is well known but its calculation is exponentially hard in p.

We have developed a technique which extends recent results on integral representations and their asymptotic expansions to obtain the full expansion for the blocking probabilities in inverse powers of a large parameter N. The power of the method derives from two sources: first, an efficient recursive formula for calculating the general term of the expansion; second, tight upper and lower bounds which accompany the estimates. The computational complexity is polynomial in p. We report on computations.
On the stationary waiting-time distribution in theGI/G/1 queue, I: Transform methods and almost-phase-type distributions
Authors: Ott Teunis J.
Published: April 2006

This paper establishes a link between the Wiener–Hopf factorization and the phase-type method for studying theGI/G/1 queue. Using the Wiener–Hopf factorization, infinite-matrix type results are established for theGI/G/1 queue. An iterative numerical procedure (‘Levinson&s method’) based on these results is described. This method does not always converge. For the situation where either the interarrival times or the service times are of the so-called almost phase type (APH) an alternative, probabilistic derivation of the same results is given. This alternative derivation shows that in the APH situation Levinson&s method converges, converges essentially monotonically, and converges to the correct values.

The algorithm has been coded and examples of numerical results are included.
Asymptotic Poisson distributions with applications to statistical analysis of graphs
Authors: Nowicki Krzysztof
Published: April 2006

Various types of graph statistics for graphs and digraphs are presented as numerators of incompleteU-statistics, with symmetric and asymmetric kernels, respectively. Thus, asymptotic Poisson limits of these statistics are provided by using limit theorems for the sums of dissociated random variables. Several applications to statistical analysis of graphs are given.
Second-order approximations for certain stopped sums in extended renewal theory
Authors: Alsmeyer Gerold
Published: April 2006

Let (X0, Y0), (X1, Y1), · ·· be a sequence of independent two-dimensional random vectors such that (X1, Y1), (X2, Y2), · ·· are i.i.d. Let {(Sn, Un)}n≧0 be the associated sum process, and define for t ≧ 0

Under suitable conditions on (X0, Y0) and (X1, Y1) we derive expansions up to vanishing terms, as t→∞, for EUT(t), Var UT(t) and Cov (UT(t), T(t)). Corresponding results will be obtained for EUN(t), Var UN(t) and Cov (UN(t), N(t)) when X0, Χ1 are both almost surely non-negative and
Stochastic convexity and its applications
Authors: Shaked Moshe , Shanthikumar J. George
Published: April 2006

Several notions of stochastic convexity and concavity and their properties are studied in this paper. Efficient sample path approaches are developed in order to verify the occurrence of these notions in various applications. Numerous examples are given. The use of these notions in several areas of probability and statistics is demonstrated. In queueing theory, the convexity (as a function of c) of the steady-state waiting time in a GI/D/c queue, and (as a function of the arrival or service rates) in a GI/G/1 queue, is established. Also the convexity of the queue length in the M/M/c case (as a function of the arrival rate) is shown, thus strengthening previous results while simplifying their derivation. In reliability theory, the convexity of the payoff in the success rate of an imperfect repair is obtained and used to find an optimal repair probability. Also the convexity of the damage as a function of time in a cumulative damage shock model is shown. In branching processes, the convexity of the population size as a function of a parameter of the offspring distribution is proved. In non-parametric statistics, the stochastic concavity (or convexity) of the empirical distribution function is established. And, for applications in the theory of probability inequalities, we identify several families of distributions which are convexly parametrized.
A note on stochastic search methods for global optimization
Authors: Kennedy D. P.
Published: April 2006

Let [An, Bn] be random subintervals of [0, 1] defined recursively as follows. Let A1 = 0, B1 = 1 and take Cn, Dn to be the minimum and maximum of k, i.i.d. random points uniformly distributed on [An, Bn]. Choose [An+1, Bn+1] to be [Cn, Bn], [Any Dn] or [Cn, Dn] with probabilities p, q, r respectively, p + q + r = 1. It is shown that the limiting distribution of [Any Bn] has the beta distribution on [0,1] with parameters k(p + r) and k(q + r). The result is used to consider a randomized version of Golden Section search.
Approximation of periodic queues
Authors: Rolski Tomasz
Published: April 2006

In this paper we demonstrate how some characteristics of queues with the periodic Poisson arrivals can be approximated by the respective characteristics in queues with Markov modulated input. These Markov modulated queues were recently studied by Regterschot and de Smit (1984). The approximation theorems are given in terms of the weak convergence of some characteristics and their uniform integrability. The approximations are applicable for the following characteristics: mean workload, mean workload at the time of day, mean delay, mean queue size.
On joint queue-length characteristics in infinite-server tandem queues with heavy traffic
Authors: Schmidt Volker
Published: April 2006

Forminfinite-server queues with Poisson input which are connected in a series, a simple proof is given of a formula derived in [3] for the generating function of the joint customer-stationary distribution of the successive numbers of customers a randomly chosen customer finds at his arrival epochs at two queues of the system. In this connection, a shot-noise representation of the queue-length characteristics under consideration is used. Moreover, using this representation, corresonding asymptotic formulas are derived for infinite-server tandem queues with general high-density renewal input.
One-node closed multichannel service system: several types of customers and service rates, and random pick-up from the waiting line
Authors: Bronshtein O. , Gertsbakh I. , Pittel B. , Shahaf S.
Published: April 2006

A closed queueing system has Q service channels and a waiting line. There are Ni customers of type i in the system, i = 1, ···, m, ∑mi=1Ni = N > Q. Q customers are served and Q0 = N – Q stay in the waiting line. Q channels are partitioned into n groups with Qj channels in the jth group, j = 1, ···, n. The service time of the ith type customer by a channel of the jth group is τij ~ Exp (λij). When a customer leaves the channel, it is immediately replaced by another one picked up randomly from the waiting time. The customer which has cleared service joins the waiting line without delay. Let Xij be the number of ith type customers served by jth group channels in equilibrium. An explicit formula for P(Xij = kij, i = 1, ···, m; j = 1, ···, n) is found. It is shown in a form of a local limit theorem that the asymptotic distribution of {Xij} is a multidimensional normal, if Qj/N and Qj/N have positive limits as N → ∞. Formulas for mean values and covariances are given. It turns out that the means of Xij and covariances between Xij and Xrk can be found, using an efficient iterative algorithm, from the deterministic version of the system. A numerical example demonstrates that the normal approximation is rather accurate.
Ruin estimation for a general insurance risk model
Authors: Embrechts Paul , Schmidli Hanspeter
Published: April 2006

The theory of piecewise-deterministic Markov processes is used in order to investigate insurance risk models where borrowing, investment and inflation are present.
Loss probabilities in a simple circuit-switched network
Authors: Morrison J. A.
Published: April 2006

In this paper a particular loss network consisting of two links with C1 and C2 circuits, respectively, and two fixed routes, is investigated. A call on route 1 uses a circuit from both links, and a call on route 2 uses a circuit from only the second link. Calls requesting routes 1 and 2 arrive as independent Poisson streams. A call requesting route 1 is blocked and lost if there are no free circuits on either link, and a call requesting route 2 is blocked and lost if there is no free circuit on the second link. Otherwise the call is connected and holds a circuit from each link on its route for the holding period of the call.

The case in which the capacities C1, and C2, and the traffic intensities v1, and v2, all become large of O(N) where N » 1, but with their ratios fixed, is considered. The loss probabilities L1 and L2 for calls requesting routes 1 and 2, respectively, are investigated. The asymptotic behavior of L1 and L2 as N→ ∞ is determined with the help of double contour integral representations and saddlepoint approximations. The results differ in various regions of the parameter space (C1, C2, v1, v2). In some of these results the loss probabilities are given in terms of the Erlang loss function, with appropriate arguments, to within an exponentially small relative error. The results provide new information when the loss probabilities are exponentially small in N. This situation is of practical interest, e.g. in cellular systems, and in asynchronous transfer mode networks, where very small loss probabilities are desired.

The accuracy of the Erlang fixed-point approximations to the loss probabilities is also investigated. In particular, it is shown that the fixed-point approximation E2 to L2 is inaccurate in a certain region of the parameter space, since L2 « E2 there. On the other hand, in some regions of the parameter space the fixed-point approximations to both L1 and L2 are accurate to within an exponentially small relative error.
GI/G/1 processor sharing queue in heavy traffic
Authors: Grishechkin Sergei
Published: April 2006

ConsiderGI/G/1 processor sharing queues with traffic intensity tending to 1. Using the theory of random measures and the theory of branching processes we investigate the limiting behaviour of the queue length, sojourn time and random measures describing attained and residual processing times of customers present.
Binary structure functions with dependent components
Authors: Ebrahimi Nader
Published: April 2006

In this paper we attempt to develop an axiomatic theory of binary structure functions with dependent components. This is an important problem, hitherto largely ignored. The concept ofcoherent structure in probabilityis introduced and studied. The relationship to the classicalcoherent structureis discussed. In the new concept the relevancy is defined through reliability of the system, while in the classical concept it is defined through the structure function.
A single-server queue with server vacations and a class of non-renewal arrival processes
Authors: Lucantoni David M. , Meier-Hellstern Kathleen S. , Neuts Marcel F.
Published: April 2006

We study a single-server queue in which the server takes a vacation whenever the system becomes empty. The service and vacation times and the arrival process are all assumed to be mutually independent. The successive service times and the vacation times each form independent, identically distributed sequences with general distributions. A new class of non-renewal arrival processes is introduced. As special cases, it includes the Markov-modulated Poisson process and the superposition of phase-type renewal processes.

Algorithmically tractable equations for the distributions of the waiting times at an arbitrary time and at arrivals, as well as for the queue length at an arbitrary time, at arrivals, and at departures are established. Some factorizations, which are known for the case of renewal input, are generalized to this new framework and new factorizations are obtained. The algorithmic implementation of these results is discussed.
Diffusion approximations for queues with server vacations
Authors: Kella Offer , Whitt Ward
Published: April 2006

This paper studies the standard single-server queue with unlimited waiting space and the first-in first-out service discipline, modified by having the server take random vacations. In the first model, there is a vacation each time the queue becomes empty, as occurs for high-priority customers with a non-preemptive priority service discipline. Approximations for both the transient and steady-state behavior are developed for the case of relatively long vacations by proving a heavy-traffic limit theorem. If the vacation times increase appropriately as the traffic intensity increases, the workload and queue-length processes converge in distribution to Brownian motion with a negative drift, modified to have a random jump up whenever it hits the origin. In the second model, vacations are generated exogenously. In this case, if both the vacation times and the times between vacations increase appropriately as the traffic intensity increases, then the limit process is reflecting Brownian motion, modified by the addition of an exogenous jump process. The steady-state distributions of these two limiting jump-diffusion processes have decomposition properties previously established for vacation queueing models, i.e., in each case the steady-state distribution is the convolution of two distributions, one of which is the exponential steady-state distribution of the reflecting Brownian motion obtained as the heavy-traffic limit without vacations.
Concavity of the throughput of tandem queueing systems with finite buffer storage space
Authors: Meester Ludolf E. , Shanthikumar J. George
Published: April 2006

We consider a tandem queueing system with m stages and finite intermediate buffer storage spaces. Each stage has a single server and the service times are independent and exponentially distributed. There is an unlimited supply of customers in front of the first stage. For this system we show that the number of customers departing from each of the m stages during the time interval [0, t] for any t ≧ 0 is strongly stochastically increasing and concave in the buffer storage capacities. Consequently the throughput of this tandem queueing system is an increasing and concave function of the buffer storage capacities. We establish this result using a sample path recursion for the departure processes from the m stages of the tandem queueing system, that may be of independent interest. The concavity of the throughput is used along with the reversibility property of tandem queues to obtain the optimal buffer space allocation that maximizes the throughput for a three-stage tandem queue.
Networks and dynamical systems
Authors: Malyshev V. A.
Published: April 2006

A new approach to the problem of classification of (deflected) random walks in or Markovian models for queueing networks with identical customers is introduced. It is based on the analysis of the intrinsic dynamical system associated with the random walk. Earlier results for small dimensions are presented from this novel point of view. We give proofs of new results for higher dimensions related to the existence of a continuous invariant measure for the underlying dynamical system. Two constants are shown to be important: the free energy M < 0 corresponds to ergodicity, the Lyapounov exponent L < 0 defines recurrence. General conjectures, examples, unsolved problems and surprising connections with ergodic theory, classical dynamical systems and their random perturbations are largely presented. A useful notion naturally arises, the so-called scaled random perturbation of a dynamical system.
The BMAP/GI/1 queue with server set-up times and server vacations
Authors: Ferrandiz Josep M.
Published: April 2006

Using Palm-martingale calculus, we derive the workload characteristic function and queue length moment generating function for the BMAP/GI/1 queue with server vacations. In the queueing system under study, the server may start a vacation at the completion of a service or at the arrival of a customer finding an empty system. In the latter case we will talk of a server set-up time. The distribution of a set-up time or of a vacation period after a departure leaving a non-empty system behind is conditionally independent of the queue length and workload. Furthermore, the distribution of the server set-up times may be different from the distribution of vacations at service completion times. The results are particularized to the M/GI/1 queue and to the BMAP/GI/1 queue (without vacations).
On conditional stochastic ordering of distributions
Authors: Rüschendorf Ludger
Published: April 2006

Conditional stochastic ordering is concerned with the stochastic ordering of a pair of probability measures conditional on certain subsets or sub-σ -algebras. Some basic results of conditional stochastic ordering were proved by Whitt. We extend some of Whitt's results and prove a basic relation between stochastic ordering conditional on subsets and stochastic ordering conditional on σ -algebras. In the second part of the paper we consider the ordering of conditional expectations. There are several different formulations of this problem motivated by different types of applications.
Strategy evaluation for stochastic scheduling problems with order constraints
Authors: Glazebrook K. D.
Published: April 2006

A single machine is available to process a collectionJof jobs. The machine is free to switch between jobs at any time, but processing must respect a set Γof precedence constraints. Jobs evolve stochastically and earn rewards as they are processed, not otherwise. The theoretical framework of forwards induction/Gittins indexation is used to develop approaches to strategy evaluation for quite general (J,Γ). The performance of both forwards induction strategies and a class of quasi-myopic heuristics is assessed.
Stability of Markovian processes II: continuous-time processes and sampled chains
Authors: Meyn Sean P. , Tweedie R. L.
Published: April 2006

In this paper we extend the results of Meyn and Tweedie (1992b) from discrete-time parameter to continuous-parameter Markovian processes Φ evolving on a topological space.

We consider a number of stability concepts for such processes in terms of the topology of the space, and prove connections between these and standard probabilistic recurrence concepts. We show that these structural results hold for a major class of processes (processes with continuous components) in a manner analogous to discrete-time results, and that complex operations research models such as storage models with state-dependent release rules, or diffusion models such as those with hypoelliptic generators, have this property. Also analogous to discrete time, ‘petite sets', which are known to provide test sets for stability, are here also shown to provide conditions for continuous components to exist.

New ergodic theorems for processes with irreducible and countably reducible skeleton chains are derived, and we show that when these conditions do not hold, then the process may be decomposed into an uncountable orbit of skeleton chains.
Stability of Markovian processes III: Foster–Lyapunov criteria for continuous-time processes
Authors: Meyn Sean P. , Tweedie R. L.
Published: April 2006

In Part I we developed stability concepts for discrete chains, together with Foster–Lyapunov criteria for them to hold. Part II was devoted to developing related stability concepts for continuous-time processes. In this paper we develop criteria for these forms of stability for continuous-parameter Markovian processes on general state spaces, based on Foster-Lyapunov inequalities for the extended generator.

Such test function criteria are found for non-explosivity, non-evanescence, Harris recurrence, and positive Harris recurrence. These results are proved by systematic application of Dynkin's formula.

We also strengthen known ergodic theorems, and especially exponential ergodic results, for continuous-time processes. In particular we are able to show that the test function approach provides a criterion forf-norm convergence, and bounding constants for such convergence in the exponential ergodic case.

We apply the criteria to several specific processes, including linear stochastic systems under non-linear feedback, work-modulated queues, general release storage processes and risk processes.
A Multilevel birth-death particle system and its continuous diffusion
Authors: Wu Yadong
Published: April 2006

In this paper we introduce a multilevel birth-death particle system and consider its diffusion approximation which can be characterized as aM([R+)-valued process. The tightness of rescaled processes is proved and we show that the limitingM(R+)-valued process is the unique solution of theM([R+)-valued martingale problem for the limiting generator. We also study the moment structures of the limiting diffusion process.
Transient analysis of the M/M/1 queue
Authors: Leguesdron P. , Pellaumail J. , Rubino G. , Sericola B.
Published: April 2006

A new approach is used to obtain the transient probabilities of the M/M/1 queueing system. The first step of this approach deals with the generating function of the transient probabilities of the uniformized Markov chain associated with this queue. The second step consists of the inversion of this generating function. A new analytical expression of the transient probabilities of the M/M/1 queue is then obtained.
Multivariate extremal processes, leader processes and dynamic choice models
Authors: Resnick Sidney , Roy Rishin
Published: April 2006

Let (Y(t),t> 0) be ad-dimensional non-homogeneous multivariate extremal process. We suppose the ith component ofYdescribes time-dependent behaviour of random utilities associated with theith choice. At timetwe choose theithalternative if the ith component ofY(t) is the largest of all the components. LetJ(t) be the index of the largest component at timet so Jhas range {1, …,d} and call {J(t)} the leader process. LetZ(t) be the value of the largest component at timet.Then the bivariate process (J(t),Z(t)} is Markov. We discuss whenJ(t) andZ(t) are independent, when {J(s), 0<s≦t} andZ(t) are independent and whenJ(t) and {Z(s), 0<s≦t} are independent. In usual circumstances, {J(t)} is Markov and particular properties are given when the underlying distribution is max-stable. In the max-stable time-homogeneous case, {J(et)} is a stationary Markov chain with stationary transition probabilities.
Approximation of sums by compound Poisson distributions with respect to stop-loss distances
Authors: Rachev S. T. , Rüschendorf L.
Published: April 2006

The approximation of sums of independent random variables by compound Poisson distributions with respect to stop-loss distances is investigated. These distances are motivated by risk-theoretic considerations. In contrast to the usual construction of approximating compound Poisson distributions, the method suggested in this paper is to fit several moments. For two moments, this can be achieved by scale transformations. It is shown that the new approximations are more stable and improve the usual approximations by accompanying laws in examples where the probability 1 – pi that the ith summand is zero is not too large.