bluuebunny/crossref_metadata_2025 huggingface dataset:
The single-server queue with independent GI/G and M/G input streams
Authors: Ott Teunis J.
Published: April 2006

This paper studies the single-server queueing system with two independent input streams: a GI/G and an M/G stream. A new proof is given of an old result which shows how this system can be transformed into an equivalent ‘single input stream’ GI/G/1 queue, and methods to study that equivalent system numerically are given. As part of the numerical analysis, algorithms are given to compute the moments and the distribution function of busy periods in the M/G/1 queue, and of other related busy periods. Special attention is given to the single-server queue with independent D/G and M/G input streams.

This work is to be used in the modeling of real-time computer systems, which can often be described as a single-server queueing system with independent D/G and M/G input streams, see for example Ott (1984b).
A non-renewal process with renewal counting distributions
Authors: Neuts Marcel F.
Published: April 2006

A simple example is given of a point process with dependent inter-event intervals for which the distributions of the counting random variables Nt are given by the same formulas as for a renewal process. This example shows the care needed in establishing that a given point process has the renewal property, but also raises interesting questions about the class of point processes with given counting distributions.
On the winding number problem with finite steps
Authors: Berger M. A. , Roberts P. H.
Published: April 2006

The winding number problem (Lévy (1940)) concerns the net angle through which the route of a random walk winds about the origin. We consider the problem of finding the winding number for a walk with finite step sizes; the eigenfunction method (Roberts and Ursell (1960)) is shown to be inapplicable because the probability distribution for a sequence of steps of different length depends on the order in which those steps are taken. In the diffusion limit, however, commutivity is restored. We derive the winding number distribution for a diffusion process, starting from a point displaced from the origin, and consider its asymptotic form. An important difference between the finite step and diffusion distributions is that the former possesses finite moments while the latter does not. We compute numerically the finite step distributions for 20000 particles undergoingN =100000 steps, and compare the results with the diffusion distribution. Even for small winding numbers, perceptible differences between the two distributions appear even forNas large as 100000.
Random filters which preserve the stability of random inputs
Authors: Cambanis Stamatis
Published: April 2006

A stationary stable random processes goes through an independently distributed random linear filter. It is shown that when the input is Gaussian or harmonizable stable, then the output is also stable provided the filter&s transfer function has non-random gain. In contrast, when the input is a non-Gaussian stable moving average, then the output is stable provided the filter&s randomness is due only to a random global sign and time shift.
Consistent estimates for hidden frequencies in a linear process
Authors: Zhao-Guo Chen
Published: April 2006

Traditional methods for detecting the hidden frequencies in white or coloured noise is based on the distribution of periodogram ordinatesΙ(2πj/N) and hypothesis testing. The power is low when a hidden frequency falls midway between two2nj/Nand it is difficult to discuss the consistency of the procedures. Using theorems on almost sure convergence of the periodogram, this paper offers a procedure for detecting and estimating the hidden frequencies, and discusses the consistency and the rates of convergence. Simulation shows very good results, when the spectrum of the noise is not too steep.
Limit behaviour for stochastic monotonicity and applications
Authors: Cohn Harry
Published: April 2006

A transition probability kernel P(·,·) is said to be stochastically monotone if P(x, (–∞, y]) is non-increasing in x for every fixed y. A Markov chain is said to be stochastically monotone (SMMC) if its transition probability kernels are stochastically monotone. A new method for tackling the asymptotics of SMMC is given in terms of some limit variables {Wq}. In the temporally homogeneous case a cyclic pattern for {Wq} will describe the limit behaviour of suitably normed and centred processes. As a consequence, geometrically growing constants turn out to pertain to almost sure convergence. Some convergence criteria are given and applications to branching processes and diffusions are outlined.
Open bandit processes and optimal scheduling of queueing networks
Authors: Lai Tze Leung , Ying Zhiliang
Published: April 2006

Asymptotic approximations are developed herein for the optimal policies in discounted multi-armed bandit problems in which new projects are continually appearing, commonly known as ‘open bandit problems’ or ‘arm-acquiring bandits’. It is shown that under certain stability assumptions the open bandit problem is asymptotically equivalent to a closed bandit problem in which there is no arrival of new projects, as the discount factor approaches 1. Applications of these results to optimal scheduling of queueing networks are given. In particular, Klimov&s priority indices for scheduling queueing networks are shown to be limits of the Gittins indices for the associated closed bandit problem, and extensions of Klimov&s results to preemptive policies and to unstable queueing systems are given.
On a multiclass batch arrival retrial queue
Authors: Falin G. I.
Published: April 2006

Kulkarni (1986) derived expressions for the expected waiting times for customers of two types who arrive in batches at a single-channel repeated orders queueing system. We propose another method of solving this problem and extend Kulkarni&s result to the case of N≧2 classes of customers.
Stochastic models for fatigue damage of materials
Authors: Sobczyk K.
Published: April 2006

The paper presents problems, methods and results concerned with the stochastic modelling of fatigue damage of materials. First, the physical and engineering origins of the fatigue phenomenon are briefly outlined. After that, the main existing approaches to random fatigue problems and the models proposed are described in such a way as to show their mathematical structure and usefulness for engineering practice.
Realization probability in closed Jackson queueing networks and its application
Authors: Cao X. R.
Published: April 2006

Perturbation analysis is a new technique which yields the sensitivities of system performance measures with respect to parameters based on one sample path of a system. This paper provides some theoretical analysis for this method. A new notion, the realization probability of a perturbation in a closed queueing network, is studied. The elasticity of the expected throughput in a closed Jackson network with respect to the mean service times can be expressed in terms of the steady-state probabilities and realization probabilities in a very simple way. The elasticity of the throughput with respect to the mean service times when the service distributions are perturbed to non-exponential distributions can also be obtained using these realization probabilities. It is proved that the sample elasticity of the throughput obtained by perturbation analysis converges to the elasticity of the expected throughput in steady-state both in mean and with probability 1 as the number of customers served goes to This justifies the existing algorithms based on perturbation analysis which efficiently provide the estimates of elasticities in practice.
Regression approximations of wavelength and amplitude distributions
Authors: Rychlik Igor
Published: April 2006

A regression approximation of wavelength and amplitude distribution in an almost surely continuous process η (t), is based on a successively more detailed decomposition, η (t) = η n(t) + Δn(t), into one regression term η n on n suitably chosen random quantities, and one residual process Δn. The distances between crossings, maxima, etc., are then approximated by the corresponding quantities in the regression term, and explicit expressions given for the densities of these quantities.
On the interchangeability and stochastic ordering of ·/M/1 queues in tandem
Authors: Tsoucas Pantelis , Walrand Jean
Published: April 2006

A probabilistic proof is given of the fact that the departure process from two initially empty. ·/M/1 queues in tandem is unaffected when the service rates are interchanged. As a consequence of this, we show that when the sum of the service rates at the two queues is held constant the departure process stochastically increases as the service rates become equal. The proofs are based on coupling of reflected random walks.
Asymptotic properties of estimators for parameters of the Boolean model
Authors: Molchanov Ilya , Stoyan Dietrich
Published: April 2006

This paper considers estimators of parameters of the Boolean model which are obtained by means of the method of intensities. For an estimator of the intensity of the point process of germ points the asymptotic normality is proved and the corresponding variance is given. The theory is based on a study of second-order characteristics of the point process of lower-positive tangent points of the Boolean model. An estimator of the distribution of a typical grain is also discussed.
Optimal stochastic scheduling of forest networks with switching penalties
Authors: Van Oyen Mark P. , Teneketzis Demosthenis
Published: April 2006

We present structural properties of optimal policies for the problem of scheduling a single server in a forest network ofNqueues (without arrivals) subject to switching penalties. In addition to linear holding costs, we impose either lump sum switching costs or batch set-up delays which are incurred at each instant the server processes a job in a queue different from the previous one. We use reward rate notions to unearth conditions on the holding costs and service distributions for which an exhaustive policy is optimal. For the case of two nodes connected probabilistically in tandem, we explicitly define an optimal policy under similar conditions.
The higher moments of the number of returns of a simple random walk
Authors: Kirschenhofer Peter , Prodinger Helmut
Published: April 2006

We consider a simple random walk starting at 0 and leading to 0 after 2n steps. By a generating functions approach we achieve closed formulae for the moments of the random variables ‘number of visits to the origin'.
The distribution of the frequencies of age-ordered alleles in a diffusion model
Authors: Ethier S. N.
Published: April 2006

We prove that the frequencies of the oldest, second-oldest, third-oldest, … alleles in the stationary infinitely-many-neutral-alleles diffusion model are distributed asX1, (1 −X1)X2, (1 −X1)(1 −X2)X3, …, whereX1,X2,X3, … are independent beta (1,θ) random variables,θbeing twice the mutation intensity; that is, the frequencies of age-ordered alleles have the so-called Griffiths–Engen–McCloskey, or GEM, distribution. In fact, two proofs are given, the first involving reversibility and the size-biased Poisson–Dirichlet distribution, and the second relying on a result of Donnelly and Tavaré relating their age-ordered sampling formula to the GEM distribution.
A diffusion model with loss of particles
Authors: Papież Lech S. , Sandison George A.
Published: April 2006

The dynamical behaviour of particles which undergo diffusion with annihilation is modelled by a parabolic (Fokker–Planck) equation. Fundamental, closed-form solutions of this equation, identified with transition densities of the underlying stochastic process, are calculated by utilizing specific methods of probability measures on functional spaces and evolution semigroups.
A jump-driven Markovian electric load model
Authors: Malhamé Roland
Published: April 2006

Electric water heating loads, in power systems, can be adequately modeled by Markov processes comprising a mix of continuous and discrete states. A physically-based characterization of the dynamic behavior of large aggregates of electric water heating loads is obtained by deriving the forward Kolmogorov equations associated with the individual hybrid-state processes. In addition, by focusing on the discrete part of the state, a Markov renewal viewpoint of the processes is developed. Both viewpoints are used to analyze and predict the transient and steady-state behavior of these loads, of great importance in load management applications.
Optimal strategies for some repair replacement models
Authors: Stadje Wolfgang , Zuckerman Dror
Published: April 2006

The problem of finding optimal replacement strategies for certain classes of failure systems is considered. These systems can be repaired upon failure, but are stochastically deteriorating, i.e., the lengths of the operating intervals decrease in some sense, whereas the durations of the repairs increase. For several models of this type optimal replacement strategies are derived under natural assumptions on the reward and the cost structure.
Teletraffic engineering for product-form circuit-switched networks
Authors: Ross Keith W. , Tsang Danny
Published: April 2006

We develop a performance modeling methodology for product-form circuit-switched networks. These networks allow for: arbitrary topology and link capacities; Poisson and finite population arrivals; multiple classes of calls, each class with a different route and bandwidth requirement; conference as well as point-to-point calls. The methodology is first applied togeneralized tree networks, which consist of multiple access links feeding into a common link. Each access link may support multiple ‘long-distance' classes (requiring circuits only on the access link and on the common link) and multiple ‘local' classes (requiring circuits only on the access link). For generalized tree networks an efficient algorithm is given to determine the blocking probabilities. The methodology is then applied tohierarchical tree networks, where traffic is repeatedly merged in the direction of a root node.

We also establish a ‘Norton' theorem for product-form circuit-switched networks. This theorem implies that for any given calling class, the entire network can be replaced by an Erlang loss system with a state-dependent arrival rate, without modifying the equilibrium probabilities for the particular calling class.
Vacation queues with Markov schedules
Authors: Wortman M. A. , Disney Ralph L.
Published: April 2006

This paper identifies a probability structure for queues that belong to the class of vacation systems operating according to Markov schedules, admitting a wide variety of server scheduling disciplines including most disciplines associated with those M/GI/1/L vacation systems reported in the literature. The conditions that define these schedules are identified, and it is shown that when these conditions are satisfied, queueing behavior is governed by an underlying Markov renewal/semi-regenerative structure. A simple example is examined (the M/GI/1 vacation system with limited batch service) to demonstrate the usefulness and generality of the underlying probability structure.
Distributions with complete monotone derivative and geometric infinite divisibility
Authors: Pillai R. N. , Sandhya E.
Published: April 2006

It is shown that a distribution with complete monotone derivative is geometrically infinitely divisible and that the class of distributions with complete monotone derivative is a proper subclass of the class of geometrically infinitely divisible distributions.
A generalization of a waiting time problem
Authors: El-Desouky B. S. , Hussen S. A.
Published: April 2006

An urn contains m types of balls of unequal numbers. Let ni be the number of balls of type i, i = 1, 2, …, m. Balls are drawn with replacement until first duplication. In the case of finite memory of order k, the distribution of Ym,k, the number of drawings required, is discussed. Special cases are obtained.
Single-machine stochastic scheduling with dependent processing times
Authors: Glazebrook K. D. , Whitaker Lyn R.
Published: April 2006

A single machine is available to process a collection of stochastic jobs preemptively. Rewards are received at job completions. We seek policies for machine allocation which maximize the total reward. Application areas point to the need to study such models for resource allocation when job processing requirements are dependent. To this end, models are developed in which the nature of such dependence is derived from various notions of positive and negative dependence in common usage in reliability. Optimal policies for resource allocation of simple structure are obtained for a variety of such models.
H = λGand the Palm transformation
Authors: Whitt Ward
Published: April 2006

We show that the stationary version of the queueing relationH=λGis equivalent to the basic Palm transformation for stationary marked point processes.
On the optimal control of cancer radiotherapy for non-homogeneous cell populations
Authors: Hanin L. G. , Rachev S. T. , Yakovlev A. Yu.
Published: April 2006

Optimization problems in cancer radiation therapy are considered, with the efficiency functional defined as the difference between expected survival probabilities for normal and neoplastic tissues. Precise upper bounds of the efficiency functional over natural classes of cellular response functions are found. The ‘Lipschitz' upper bound gives rise to a new family of probability metrics. In the framework of the ‘mhit-one target' model of irradiated cell survival the problem of optimal fractionation of the given total dose intonfractions is treated. Form =1,narbitrary, andn =1, 2,marbitrary, complete solution is obtained. In other cases an approximation procedure is constructed. Stability of extremal values and upper bounds of the efficiency functional with respect to perturbation of radiosensitivity distributions for normal and tumor tissues is demonstrated.
Scheduling and stability aspects of a general class of parallel processing systems
Authors: Bambos Nicholas , Walrand Jean
Published: April 2006

In this paper we study the following general class of concurrent processing systems. There are several different classes of processors (servers) and many identical processors within each class. There is also a continuous random flow of jobs, arriving for processing at the system. Each job needs to engage concurrently several processors from various classes in order to be processed. After acquiring the needed processors the job begins to be executed. Processing is done non-preemptively, lasts for a random amount of time, and then all the processors are released simultaneously. Each job is specified by its arrival time, its processing time, and the list of processors that it needs to access simultaneously. The random flow (sequence) of jobs has a stationary and ergodic structure. There are several possible policies for scheduling the jobs on the processors for execution; it is up to the system designer to choose the scheduling policy to achieve certain objectives.

We focus on the effect that the choice of scheduling policy has on the asymptotic behavior of the system at large times and especially on its stability, under general stationary and ergocic input flows.
Virtual customers in sensitivity and light traffic analysis via Campbell's formula for point processes
Authors: Baccelli F. , Brémaud P.
Published: April 2006

This article provides the theoretical basis of the virtual customer method or positive rare perturbation (RPA) method of sensitivity analysis, and in particular gives a short proof of the light traffic derivative result of Reiman and Simon [5] based on Campbell's formula. As a by-product, we obtain the archetypal H = λG formula associated with a stationary quantity of a queueing system.
A new view of the heavy-traffic limit theorem for infinite-server queues
Authors: Glynn Peter W. , Whitt Ward
Published: April 2006

This paper presents a new approach for obtaining heavy-traffic limits for infinite-server queues and open networks of infinite-server queues. The key observation is that infinite-server queues having deterministic service times can easily be analyzed in terms of the arrival counting process. A variant of the same idea applies when the service times take values in a finite set, so this is the key assumption. In addition to new proofs of established results, the paper contains several new results, including limits for the work-in-system process, limits for steady-state distributions, limits for open networks with general customer routes, and rates of convergence. The relatively tractable Gaussian limits are promising approximations for many-server queues and open networks of such queues, possibly with finite waiting rooms.
Monotonicity results for queues with doubly stochastic Poisson arrivals: Ross's conjecture
Authors: Chang Cheng-Shang , Chao Xiu Li , Pinedo Michael
Published: April 2006

In this paper, we compare queueing systems that differ only in their arrival processes, which are special forms of doubly stochastic Poisson (DSP) processes. We define a special form of stochastic dominance for DSP processes which is based on the well-known variability or convex ordering for random variables. For two DSP processes that satisfy our comparability condition in such a way that the first process is more ‘regular' than the second process, we show the following three results: (i) If the two systems are DSP/GI/1 queues, then for all f increasing convex, with V(i), i = 1 and 2, representing the workload (virtual waiting time) in system. (ii) If the two systems are DSP/M(k)/1→ /M(k)/l ∞ ·· ·∞ /M(k)/1 tandem systems, with M(k) representing an exponential service time distribution with a rate that is increasing concave in the number of customers, k, present at the station, then for all f increasing convex, with Q(i), i = 1 and 2, being the total number of customers in the two systems. (iii) If the two systems are DSP/M(k)/1/N systems, with N being the size of the buffer, then where denotes the blocking (loss) probability of the two systems. A model considered before by Ross (1978) satisfies our comparability condition; a conjecture stated by him is shown to be true.
Superposition of Markov renewal processes and applications
Authors: Lam C. Teresa
Published: April 2006

In this paper, we study the superposition of finitely many Markov renewal processes with countable state spaces. We define the S-Markov renewal equations associated with the superposed process. The solutions of the S-Markov renewal equations are derived and the asymptotic behaviors of these solutions are studied. These results are applied to calculate various characteristics of queueing systems with superposition semi-Markovian arrivals, queueing networks with bulk service, system availability, and continuous superposition remaining and current life processes.
A bivariate random environmental stress model
Authors: Gupta Pushpa L. , Gupta R. D.
Published: April 2006

We study the relative errors in reliability measures for the series system, under the wrong assumption of independence incorporating environmental effects, when the Marshall and Olkin model with environmental effects should be used.
Extended and conditional versions of the PASTA property
Authors: König Dieter , Schmidt Volker
Published: April 2006

Two types of conditions are discussed ensuring the equality between long-run time fractions and long-run event fractions of stochastic processes with embedded point processes. Modifications of this equality statement are considered.
A note on M/G/1 vacation systems with waiting time limits
Authors: Takine T. , Hasegawa T.
Published: April 2006

We consider two variants of M/G/1 queues with exhaustive service and multiple vacations; (1) customers cannot wait for their services longer than an interval of length T, and (2) customers cannot stay in the system longer than an interval of length T. We show that the probability distribution functions of the waiting times for the two systems are given in terms of those for the corresponding M/G/1 vacation systems without any residence-time limits.
Anisotropic Growth of Voronoi Cells
Authors: Scheike Thomas H.
Published: April 2006

This paper discusses a simple extension of the classical Voronoi tessellation. Instead of using the Euclidean distance to decide the domains corresponding to the cell centers, another translation-invariant distance is used. The resulting tessellation is a scaled version of the usual Voronoi tessellation. Formulas for the mean characteristics (e.g. mean perimeter, surface and volume) of the cells are provided in the case of cell centers from a homogeneous Poisson process. The resulting tessellation is stationary and ergodic but not isotropic.
The Falling-Leaves Mosaic and its Equilibrium Properties
Authors: Cowan Richard , Tsang Albert K. L.
Published: April 2006

Consider a forest of maple trees in autumn, with leaves falling on the ground. Those coming late cover the others below, so eventually the fallen leaves form a statistically homogeneous spatial pattern. In particular, the uncovered leaf boundaries form a mosaic. We formulate a mathematical model to describe this mosaic, firstly in the case where the leaves are polygonal and later for leaves with curved boundaries. Mean values of certain statistics of the mosaic are derived.
An Efficient Procedure for Computing Quasi-Stationary Distributions of Markov Chains by Sparse Transition Structure
Authors: Pollett P. K. , Stewart D. E.
Published: April 2006

We describe a computational procedure for evaluating the quasi-stationary distributions of a continuous-time Markov chain. Our method, which is an ‘iterative version' of Arnoldi's algorithm, is appropriate for dealing with cases where the matrix of transition rates is large and sparse, but does not exhibit a banded structure which might otherwise be usefully exploited. We illustrate the method with reference to an epidemic model and we compare the computed quasi-stationary distribution with an appropriate diffusion approximation.
Sample Path Criteria for Weak Majorization
Authors: Sparaggis Panayotis D. , Towsley Don , Cassandras Christos G.
Published: April 2006

We present two forms of weak majorization, namely, very weak majorization and p-weak majorization that can be used as sample path criteria in the analysis of queueing systems. We demonstrate how these two criteria can be used in making comparisons among the joint queue lengths of queueing systems with blocking and/or multiple classes, by capturing an interesting interaction between state and performance descriptors. As a result, stochastic orderings on performance measures such as the cumulative number of losses can be derived. We describe applications that involve the determination of optimal policies in the context of load-balancing and scheduling.
Burn-in and Maintenance Policies
Authors: Mi Jie
Published: April 2006

Burn-in is a widely used method to improve quality of products after they have been produced. For a repairable component there are two common types of repair, complete repair and minimal repair. Preventive maintenance policies such as age replacement and block replacement are often employed in field operation. The present paper takes burn-in, maintenance and repair into consideration at the same time and considers related cost structures. The properties of the corresponding optimal burn-in times and optimal maintenance policies are discussed.
Realization factors and sensitivity analysis of queueing networks with state-dependent service rates
Authors: Cao Xi-Ren
Published: April 2006

The paper studies the sensitivity of the throughput with respect to a mean service rate in a closed queueing network with exponentially distributed service requirements and state-dependent service rates. The study is based on perturbation analysis of queueing networks. A new concept, the realization factor of a perturbation, is introduced. The properties of realization factors are discussed, and a set of equations specifying the realization factors are derived. The elasticity of the steady state throughput with respect to a mean service rate equals the product of the steady state probability and the corresponding realization factor. This elasticity can be estimated by applying a perturbation analysis algorithm to a sample path of the system. The sample path elasticity of the throughput with respect to a mean service rate converges with probability 1 to the elasticity of the steady state throughput. The theory provides an analytical method of calculating the throughput sensitivity and justifies the application of perturbation analysis.
Bonferroni-type inequalities and the methods of indicators and polynomials
Authors: Hoppe Fred M. , Seneta Eugene
Published: April 2006

A difficulty in the application [5] of the method of polynomials as exposited by Galambos is investigated. The method, recast as the method of indicators, in a form due originally to Rényi [6], is applied to the situation of non-constant coefficients.
The equality of the virtual delay and attained waiting time distributions
Authors: Sakasegawa Hirotaka , Wolff Ronald W.
Published: April 2006

It has recently been shown that for the G/G/1 queue, virtual delay and attained waiting time have the same stationary distribution. We present a sample-path derivation of this result.
Functionals of random mappings: exact and asymptotic results
Authors: Donnelly P. J. , Ewens W. J. , Padmadisastra S.
Published: April 2006

A random mapping partitions the set {1, 2, ···,m} into components, whereiandjare in the same component if some functional iterate ofiequals some functional iterate ofj. We consider various functionals of these partitions and of samples from it, including the number of components of ‘small' size and of sizeO(m) asm→ ∞the size of the largest component, the number of components, and various symmetric functionals of the normalized component sizes. In many cases exact results, while available, are uniformative, and we consider various approximations. Numerical and simulation results are also presented. A central tool for many calculations is the ‘frequency spectrum', both exact and asymptotic.
On a continuum percolation model
Authors: Penrose Mathew D.
Published: April 2006

Consider particles placed in space by a Poisson process. Pairs of particles are bonded together, independently of other pairs, with a probability that depends on their separation, leading to the formation of clusters of particles. We prove the existence of a non-trivial critical intensity at which percolation occurs (that is, an infinite cluster forms). We then prove the continuity of the cluster density, or free energy. Also, we derive a formula for the probability that an arbitrary Poisson particle lies in a cluster consisting ofkparticles (or equivalently, a formula for the density of such clusters), and show that at high Poisson intensity, the probability that an arbitrary Poisson particle is isolated, given that it lies in a finite cluster, approaches 1.
On the attained waiting time
Authors: Cohen J. W.
Published: April 2006

By using properties of up- and downcrossings of the sample functions of the workload process and of the attained waiting-time process for a G/G/1 queueing model, a direct proof of a theorem proved by Sakasegawa and Wolff is given.
Implied costs in loss networks
Authors: Hunt P. J.
Published: April 2006

Implied costs in loss networks are measures of the rate of change of an objective function with respect to the parameters of the network. This paper considers these costs and the costs predicted by the Erlang fixed-point approximation. We derive exact expressions for the implied costs and consider the asymptotic accuracy of the approximation. We show that the approximation is asymptotically valid in some cases but is not valid in one important limiting regime. We also show that a linearity approximation for the implied costs is asymptotically correct when taken over suitable subsets of links.
Product-form distributions for an M/G/k group-arrival group-departure loss system
Authors: Fakinos D. , Sirakoulis K.
Published: April 2006

In this work we investigate under what circumstances the equilibrium distribution of the numbers of groups of various sizes in a certain M/G/k group-arrival group-departure loss system can be obtained in a closed product form.
Scheduling jobs on non-identical IFR processors to minimize general cost functions
Authors: Righter Rhonda , Xu Susan H.
Published: April 2006

We consider the problem of scheduling n jobs non-preemptively on m parallel, non-identical processors to minimize a weighted expected cost function of job completion times, where the weights are associated with the jobs. The cost function is assumed to be increasing and concave but otherwise arbitrary. Processing times are IFR with different distributions for different processors. Jobs may be processed on any processor and there are no precedences. We show that the optimal policy orders the jobs in decreasing order of their weights and then uses the individually optimal policy for each job. In other words, processors are offered to jobs in order, and each job considers its own expected cost function for its completion time to decide whether to accept or reject a processor. Therefore, the optimal policy does not depend on the weights of the jobs except through their order. Special cases of our objective function are weighted expected flowtime, weighted discounted expected flowtime, and weighted expected number of tardy jobs.
Transient phenomena for Markov chains and applications
Authors: Borovkov A. A. , Fayolle G. , Korshunov D. A.
Published: April 2006

We consider a family of irreducible, ergodic and aperiodic Markov chains X(ε)= {X(ε)n, n ≧0} depending on a parameterε> 0, so that the local drifts have a critical behaviour (in terms of Pakes' lemma). The purpose is to analyse the steady-state distributions of these chains (in the sense of weak convergence), when ε↓ 0. Under assumptions involving at most the existence of moments of order 2 + γ for the jumps, we show that, wheneverX(0)is not ergodic, it is possible to characterize accurately these limit distributions. Connections with the gamma and uniform distributions are revealed. An application to the well-known ALOHA network is given.
On some first-crossing-time probabilities for a two-dimensional random walk with correlated components
Authors: Di Crescenzo A. , Giorno V. , Nobile A. G.
Published: April 2006

For a two-dimensional random walk {X (n) = (X(n)1, X(n)2)T, n ∈ ℕ0} with correlated components the first-crossing-time probability problem through unit-slope straight lines x2 = x1 - r(r = 0,1) is analysed. The p.g.f.'s for the first-crossing-time probabilities are expressed as solutions of a fourth-degree algebraic equation and are then exploited to obtain the first-crossing-time probabilities. Several additional results, including the mean first-crossing time and the probability of ultimate crossing, are also given.
Random fields on random graphs
Authors: Whittle P.
Published: April 2006

The distribution (1) used previously by the author to represent polymerisation of several types of unit also prescribes quite general statistics for a random field on a random graph. One has the integral expression (3) for its partition function, but the multiple complex form of the integral makes the nature of the expected saddlepoint evaluation in the thermodynamic limit unclear. It is shown in Section 4 that such an evaluation at a real positive saddlepoint holds, and subsidiary conditions narrowing down the choice of saddlepoint are deduced in Section 6. The analysis simplifies greatly in what is termed the semi-coupled case; see Sections 3, 5 and 7. In Section 8 the analysis is applied to an Ising model on a random graph of fixed degreer+ 1. The Curie point of this model is found to agree with that deduced by Spitzer for an Ising model on an r-branching tree. This agreement strengthens the conclusion of ‘locally tree-like' behaviour of the graph, seen as an important property in a number of contexts.
A unified model for Kakutani's interval splitting and Rényi's random packing
Authors: Komaki Fumiyasu , Itoh Yoshiaki
Published: April 2006

One-dimensional random packing, known as the car-parking problem, was first analyzed by Rényi (1958). A stochastic version of Kakutani's (1975) interval splitting is another typical model on a one-dimensional interval. We consider a generalized car-parking problem which contains the above two models as special cases. In the generalized model, one can park a car of length l, if there is a space not less than 1. We give the limiting packing density and the limiting distribution of the length of randomly selected gaps between cars. Our results bridge the two models of Rényi and Kakutani.
Random Johnson-Mehl tessellations
Authors: Møller Jesper
Published: April 2006

A unified exposition of random Johnson–Mehl tessellations ind-dimensional Euclidean space is presented. In particular, Johnson-Mehl tessellations generated by time-inhomogeneous Poisson processes and nucleation-exclusion models are studied. The ‘practical' casesd= 2 andd =3 are discussed in detail. Several new results are established, including first- and second-order moments of various characteristics for both Johnson–Mehl tesselations and sectional Johnson–Mehl tessellations.
Exact distribution theory for some point process record models
Authors: Bunge J. A. , Nagaraja H. N.
Published: April 2006

LetY0, Y1, Y2, … be an i.i.d. sequence of random variables with continuous distribution function, and letPbe a simple point process on 0≦t≦∞, independent of theYj's.We assume thatPhas a point att= 0; we associateYjwith thejth point ofj≧0, and we say that theYj'soccur at the arrival times ofP. Y0is considered a ‘reference value'. The firstYj(j≧1) to exceed all previous ones is called the first ‘record value', and the time of its occurrence is the first ‘record time'. Subsequent record values and times are defined analogously. We give an infinite series representation for the joint characteristic function of the firstnrecord times, for generalP; in some cases the series can be summed. We find the intensity of the record process whenPis a general birth process, and whenPis a linear birth process withmimmigration sources we find the distribution of the number of records in (0,t]. Form =0 (the Yule process) we give moments of record times and a compact form for the record process intensity. We show that the records occur according to a homogeneous Poisson process whenm =1, and we display a different model with the same behavior, leading to statistical non-identifiability if only the record times are observed. Form =2, the records occur according to a semi-Markov process; again we display a different model with the same behavior. Finally we give a new derivation of the joint distribution of the interrecord times whenPis an arbitrary Poisson process. We relate this result to existing work and to the classical record model. We also obtain a new characterization of the exponential distribution.
Asymptotic behavior of velocity process in the Smoluchowski–Kramers approximation for stochastic differential equations
Authors: Narita Kiyomasa
Published: April 2006

Here a response of a non-linear oscillator of the Liénard type with a large parameter α ≥ 0 is formulated as a solution of a two-dimensional stochastic differential equation with mean-field of the McKean type. This solution is governed by a special form of the Fokker–Planck equation such as the Smoluchowski–Kramers equation, which is an equation of motion for distribution functions in position and velocity space describing the Brownian motion of particles in an external field. By a change of time and displacement we find that the velocity process converges to a one-dimensional Ornstein–Uhlenbeck process as α →∞.
Bounding functions of Markov processes and the shortest queue problem
Authors: Gubner John A. , Gopinath B. , Varadhan S. R. S.
Published: April 2006

We prove a theorem which can be used to show that the expectation of a non-negative function of the state of a time-homogeneous Markov process is uniformly bounded in time. This is reminiscent of the classical theory of non-negative supermartingales, except that our analog of the supermartingale inequality need not hold almost surely. Consequently, the theorem is suitable for establishing the stability of systems that evolve in a stabilizing mode in most states, though from certain states they may jump to a less stable state. We use this theorem to show that ‘joining the shortest queue' can bound the expected sum of the squares of the differences between all pairs among N queues, even under arbitrarily heavy traffic.
Some properties of similar pairs
Authors: Blom Gunnar , Holst Lars
Published: April 2006

In a given set, the elements are compared pairwise. The numberWof similar pairs is studied, that is, the number of pairs with a certain property in common. Under certain conditions,Whas, approximately, a Poisson distribution. Examples are considered connected with the birthday problem and with a circle problem involving DNA breakages.
A compensation approach for two-dimensional Markov processes
Authors: Adan I. J. B. F. , Wessels J. , Zijm W. H. M.
Published: April 2006

Several queueing processes may be modeled as random walks on a multidimensional grid. In this paper the equilibrium distribution for the case of a two-dimensional grid is considered. In previous research it has been shown that for some two-dimensional random walks the equilibrium distribution has the form of an infinite series of products of powers which can be constructed with a compensation procedure. The object of the present paper is to investigate under which conditions such an elegant solution exists and may be found with a compensation approach. The conditions can be easily formulated in terms of the random behaviour in the inner area and the drift on the boundaries.
Extremal large deviations in controlled i.i.d. processes with applications to hypothesis testing
Authors: Shimkin Nahum
Published: April 2006

We consider a controlled i.i.d. process, where several i.i.d. sources are sampled sequentially. At each time instant, a controller determines from which source to obtain the next sample. Any causal sampling policy, possibly history-dependent, may be employed. The purpose is to characterize the extremal large deviations of the sample mean, namely to obtain asymptotic rate bounds (similar to and extending Cramér's theorem) which hold uniformly over all sampling policies. Lower and upper bounds are obtained, and it is shown that in many (but not all) cases stationary sampling policies are sufficient to obtain the extremal large deviations rates. These results are applied to a hypothesis testing problem, where data samples may be sequentially chosen from several i.i.d. sources (representing different types of experiments). The analysis provides asymptotic estimates for the error probabilities, corresponding both to optimal and to worst-case sampling policies.
Stochastic majorization of stochastically monotone families of random variables
Authors: Li Haijun , Shaked Moshe
Published: April 2006

Stochastic majorization is a tool that has been used in many areas of probability and statistics (such as multivariate statistical analysis, queueing theory and reliability theory) in order to obtain useful bounds and inequalities. In this paper we study the relations among several notions of stochastic majorization and stochastic convexity and obtain sufficient (and sometimes necessary) conditions which imply some of these notions. Extensions and generalizations of several results in the literature are obtained. Some examples and applications regarding stochastic comparisons of order statistics are also presented in order to illustrate the results of the paper.
The Rates of Growth of the Galton–Watson Process in Varying Environments
Authors: D'Souza J. C.
Published: April 2006

Let {Zn} be a supercritical Galton–Watson process in varying environments, and W be the limit of the non-negative martingale {Zn/EZn}. Under a condition which ensures that W is not identically equal to zero we give an upper bound on the possible rates of growth of the process on the set {W = 0}, and find a sufficient condition for the process to have only one rate of growth. We also give an example of a process whose offspring distributions have bounded pth moments, for some p > 1, and which has an infinite number of rates of growth.
Subgeometric Rates of Convergence of f-Ergodic Markov Chains
Authors: Tuominen Pekka , Tweedie Richard L.
Published: April 2006

Let Φ = {Φ n} be an aperiodic, positive recurrent Markov chain on a general state space, π its invariant probability measure and f ≧ 1. We consider the rate of (uniform) convergence of Ex[g(Φ n)] to the stationary limit π (g) for |g| ≦ f: specifically, we find conditions under which

as n →∞, for suitable subgeometric rate functions r. We give sufficient conditions for this convergence to hold in terms of

(i) the existence of suitably regular sets, i.e. sets on which (f, r)-modulated hitting time moments are bounded, and

(ii) the existence of (f, r)-modulated drift conditions (Foster–Lyapunov conditions).

The results are illustrated for random walks and for more general state space models.
The Integrated Cauchy Functional Equation: Some Comments on Recent Papers
Authors: Rao C. R. , Sapatinas T. , Shanbhag D. N.
Published: April 2006

We make some comments on recent papers involving the integrated Cauchy functional equation or specialized versions of it, and reveal in particular that these papers give an inaccurate picture of the current state of the literature on the topic.
On statistical inference for random closed sets in compact subsets of ℝd
Authors: Ferrándiz J. , Montes F.
Published: April 2006

Quite often in the statistical analysis of medical and biological problems, data are images corresponding to entire objects that include smaller objects within them. In these cases, we need models of random closed sets (RACS) confined to compact subsets of the plane. There is no room for stationarity hypotheses and the increase of statistical information comes from independent replicates of the same phenomena rather than increasing our sample window. We investigate practical methods of modelling RACS by means of circumscribed balls, leading to a natural definition of location, size and shape. We discuss the possibilities of using these random variables in order to define statistical spaces of RACS that will allow us to use maximum likelihood methods.
Stereological estimation of particle size distributions
Authors: Mase Shigeru
Published: April 2006

The corpuscle problem of Wicksell is discussed. We give a numerical quadrature of Gauss–Chebyshev type for Wicksell's integral equation which combines a size distribution of discs on a sectional plane with that of spheres. We also give an estimation procedure of three-dimensional size distributions based on this quadrature and examine its theoretical properties. In practice, we need a smoothing technique for empirical distribution functions before applying this estimator. Simulation results are given. Our idea also is applied to the thick section case and an analysis of microscopic data is given.
Generation of Johnson-Mehl crystals and comparative analysis of models for random nucleation
Authors: Møller Jesper
Published: April 2006

Simulation procedures for typical Johnson-Mehl crystals generated under various models for random nucleation are proposed. These procedures include algorithms for simulating spatio-time-inhomogeneous Poisson processes. Empirical results for a particular class of Johnson-Mehl tessellations in two and three dimensions show remarkably different crystals.
OnM/G/1 queues with exhaustive service and generalized vacations
Authors: Li Huan , Zhu Yixin
Published: April 2006

We considerM/G/1 queues with exhaustive service and generalized vacations, where at the end of every busy period the server either follows a mixed vacation policy from a given vacation policy set or stays idle. A simple recursive formula for the moments of the stationary waiting time is provided. This formula results in the decomposition property for our model immediately. It also enables us to derive many existing results for theM/G/1 queues with various vacation policies.