bluuebunny/crossref_metadata_2025 huggingface dataset:
Le problème de Buffon–Synge pour une corde
Authors: Donati-Martin C.
Published: April 2006

This paper deals with the thrown string problem posed by Synge [12]. The models studied are those of Willenborg [14] and Kingman [7]. The convergence results obtained are complementary to those of Kingman, although they are derived by quite different methods involving the use of martingales.
Limit theorems for threshold-stopped random variables with applications to optimal stopping
Authors: Kennedy Douglas P. , Kertz Robert P.
Published: April 2006

The extremal types theorem identifies asymptotic behaviour for the maxima of sequences of i.i.d. random variables. A parallel theorem is given which identifies the asymptotic behaviour of sequences of threshold-stopped random variables. Three new types of limit distributions arise, but normalizing constants remain the same as in the maxima case. Limiting joint distributions are also given for maxima and threshold-stopped random variables. Applications to the optimal stopping of i.i.d. random variables are given.
Spatial birth-death processes with multiple changes and applications to batch service networks and clustering processes
Authors: Boucherie Richard J. , Van Dijk Nico M.
Published: April 2006

Reversible spatial birth-death processes are studied with simultaneous jumps of multi-components. A relationship is established between (i) a product-form solution, (ii) a partial symmetry condition on the jump rates and (iii) a solution of a deterministic concentration equation. Applications studied are reversible networks of queues with batch services and blocking and clustering processes such as those found in polymerization chemistry. As illustrated by examples, known results are hereby unified and extended. An expectation interpretation of the transition rates is included.
Lattice points in a random parallelogram
Authors: Holgate Philip
Published: April 2006

A Fourier series is obtained for the variance of the number of points lying in a parallelogram thrown randomly on to a square lattice at a fixed angle.
Limit distribution for a consecuttve-k-out-of-n:Fsystem
Authors: Chryssaphinou Ourania , Papastavridis Stavros G.
Published: April 2006

A consecutive-k-out-of-n:Fsystem consists ofncomponents ordered on a line. Each component, and the system as a whole, has two states: it is either functional or failed. The system will fail if and only if at leastkconsecutive components fail. The components are not necessarily equal and we assume that components' failures are stochastically independent. Using a result of Barbour and Eagleson (1984) we find a bound for the distance of the distribution of system's lifetime from the Weibull distribution. Subsequently, using this bound limit theorems are derived under quite general conditions.
Aggregated Markov processes with negative exponential time interval omission
Authors: Ball Frank
Published: April 2006

We consider a time reversible, continuous time Markov chain on a finite state space. The state space is partitioned into two sets, termed open and closed, and it is only possible to observe whether the process is in an open or a closed state. Further, short sojourns in either the open or closed states fail to be detected. We consider the situation when the length of minimal detectable sojourns follows a negative exponential distribution with mean μ–1. We show that the probability density function of observed open sojourns takes the form, wherenis the size of the state space. We present a thorough asymptotic analysis offO(t) as μ tends to infinity. We discuss the relevance of our results to the modelling of single channel records. We illustrate the theory with a numerical example.
On the asymptotic behaviour of first-passage-time densities for one-dimensional diffusion processes and varying boundaries
Authors: Giorno V. , Nobile A. G. , Ricciardi L. M.
Published: April 2006

Making use of the integral equations given in [1], [2] and [3], the asymptotic behaviour of the first-passage time (FPT) p.d.f.'s through certain time-varying boundaries, including periodic boundaries, is determined for a class of one-dimensional diffusion processes with steady-state density. Sufficient conditions are given for the cases both of single and of pairs of asymptotically constant and asymptotically periodic boundaries, under which the FPT densities asymptotically exhibit an exponential behaviour. Explicit expressions are then worked out for the processes that can be obtained from the Ornstein–Uhlenbeck process by spatial transformations. Some new asymptotic results for the FPT density of the Wiener process are finally proved, together with a few miscellaneous results.
Random motions governed by third-order equations
Authors: Orsingher Enzo
Published: April 2006

In this paper we analyse the motion of a particle P whose velocity is represented by a three-valued telegraph process. We prove that the probability law of the process describing the position of P is a solution of a third-order, linear, partial differential equation.

We obtain probability distributions of some generalised versions of the process of random signals, as well as other probabilistic features of the related process.

Finally, accelerated motions of P (where acceleration follows the classical telegraph process) are also analysed.
Optimal Multiserver Stochastic Scheduling of two Interconnected Priority Queues
Authors: Pandelis Dimitrios G. , Teneketzis Demosthenis
Published: April 2006

A number of jobs on two interconnected queues are to be processed bymidentical servers. The servers operate in parallel, so that every server can process any job. Jobs in queuei, i= 1, 2, incur an instantaneous holding costCiduring the time they remain in the system. The service time for jobs in queuei,denoted byXi, is a random variable with a general distribution. The interconnection process is independent of the service process. We establish sufficient conditions on the service times, the holding costs and the interconnection process under which the non-preemptive scheduling strategy that gives priority to queue 1 minimizes the total expectedα-discounted cost. We call this strategy P1. We present counterexamples showing that if any of the sufficient conditions is not satisfied P1 may not be optimal, and that the optimal policy for the single-server problem is not necessarily optimal for the multiserver problem.
Central limit theorems for a class of polynomial hypergroups
Authors: Voit Michael
Published: April 2006

Central limit theorems are proved for random walks on the non-negative integers where the transition probabilities are homogeneous with respect to a sequence of orthogonal polynomials. Assuming some restrictions concerning the three-term recursion formula of these polynomials, one gets a Rayleigh distribution as limit distribution where bounds of the order of convergence can be computed explicitly. These central limit theorems are applied to generalized birth and death random walks and random walks on polynomial hypergroups. Finally some examples of polynomial hypergroups are discussed in view of the limit theorems above.
Convexity of a set of stochastically ordered random variables
Authors: Shaked Moshe , Shanthikumar J. George
Published: April 2006

It is shown that a set of random variables with increasing and convex (concave) survival functions are stochastically increasing and convex (concave) in the sample path sense. This stochastic convexity (concavity) result is then used to establish convexity (concavity) results for (i) a single-server queueing system with a time-out control policy, (ii) residual life, (iii) stationary renewal excess life and (iv)M/G/1 queues. These results are new and could not be derived without the direct or indirect aid of the above stochastic convexity (concavity) result. Furthermore, we illustrate that the above stochastic convexity (concavity) result can be applied to obtain new bounds for queueing systems. Specifically, letbe the waiting time of thenth customer in aGI/G/1 queue with inter-arrival time survival functionand service time survival function. Using the above convexity result it is shown that ifand for somesuch thatthenfor all increasing convex functionsφ, whenever the expectations exist. A similar result forandis also obtained. Other examples are also included.
Perturbation theory approach for a class of hybrid switching networks with small transit flows
Authors: Kelbert M. Ya. , Kopeika R. P. , Shamsiev R. N. , Sukhov Yu. M.
Published: April 2006

A method originating from statistical mechanics (low-density and high-temperature expansions) is used to prove the existence and uniqueness of a stationary regime for switching networks on finite or infinite graphs. The main assumption is that the message (customer) flows circulating through the network are ‘localized' in the sense that, for any message, the probability of having a long path is rapidly decreasing (and, moreover, a path of a ‘typical' message consists of one line). The switching rule combines message-switching and circuit-switching principles. The stationary regime for the network under consideration may be treated as a ‘small perturbation' of the ‘idealized' regime in the totally decoupled network where all the messages have single line paths.
On the ergodicity of networks of ·/GI/1/N queues
Authors: Konstantopoulos Panagiotis , Walrand Jean
Published: April 2006

In this paper we consider a network of ·/GI/1/N queues with finite-length buffers. A suitable Markov process for the time-evolution of this system is defined. This process is subsequently shown to be ergodic under the conditions of Borovkov (1987).
Estimating the frequency of the oldest allele: a bayesian approach
Authors: Joyce Paul
Published: April 2006

In this paper we calculate posterior distributions associated with a version of the Poisson–Dirichlet distribution called the GEM. The GEM has been shown (by several authors) to be the limiting stationary distribution for allele frequencies listed in age order associated with the neutral infinite alleles model. In view of this result, we use our posterior distributions to calculate Bayes estimators for the frequency of the oldest allele given a sample.
On estimation of noise variance in two-dimensional signal processing
Authors: Hall Peter , Kay J. W. , Titterington D. M.
Published: April 2006

Estimation of noise variance is an important component of digital signal processing, in particular of image processing. In this paper we develop methods for estimating the variance of white noise in a two-dimensional degraded signal. We discuss optimal configurations of pixels for difference-based estimation, and describe asymptotically optimal selection of weights for the component pixels. After extensive analysis of possible configurations we recommend averaging linear configurations over a variety of different orientations (usually two or four). This approach produces estimators with properties of both statistical and numerical efficiency.
On a problem of ammunition rationing
Authors: Shepp Lawrence A. , Simons Gordon , Yao Yi-Ching
Published: April 2006

Suppose you have u units of ammunition and want to destroy as many as possible of a sequence of attacking enemy aircraft. If you fire v = v(u), 0 , units of your ammunition at the first enemy, it survives with probability qv, where 0 < q < 1 is given, and then kills you. With the complementary probability, 1 – qv, you destroy the aircraft and you live to face the next enemy with only u – v units of ammunition remaining. It seems almost obvious that any strategy which maximizes the expected number of enemies destroyed before you die will fire more units at the first enemy as u increases, i.e., it seems obvious that v′(u) 0 under optimal play. We show this to be false, thereby disproving an appealing conjecture proposed by Weber. We also consider a variant of this problem and find that the counterpart of Weber's conjecture holds in some cases.
Bivariate characterization of some stochastic order relations
Authors: Shanthikumar J. George , Yao David D.
Published: April 2006

Bivariate (and multivariate) functional representations for the following stochastic order relations are established: the likelihood ratio ordering, hazard rate ordering, and the usual stochastic ordering. The motivation of the study is (i) to provide a general approach that supports the ‘pairwise interchange' arguments widely used in various settings, and (ii) to develop new notions of stochastic order relations so that dependent random variables can be meaningfully compared. Applications are illustrated through problems in stochastic scheduling, closed queueing network and reliability.
Random spherical triangles II: Shape densities
Authors: Le Huiling
Published: April 2006

This paper gives the exact evaluation of the shape density on the shape space Σ(S2, 3) for a labelled random spherical triangle whose vertices are i.i.d.-uniform in a ‘cap' ofS2bounded by a ‘small' circle of angular radiusρ0.
On stability of state-dependent queues and acyclic queueing networks
Authors: Bambos Nicholas , Walrand Jean
Published: April 2006

We consider a single server first-come-first-served queue with a stationary and ergodic input. The service rate is a general function of the workload in the queue. We provide the necessary and sufficient conditions for the stability of the system and the asymptotic convergence of the workload process to a finite stationary process at large times. Then, we consider acyclic networks of queues in which the service rate of any queue is a function of the workloads of this and of all the preceding queues. The stability problem is again studied. The results are then extended to analogous systems with periodic inputs.
The asymptotic behaviour of extinction probability in the Smith–Wilkinson branching process
Authors: Grey D. R. , Zhunwei Lu
Published: April 2006

Under some regularity conditions, in the supercritical Smith–Wilkinson branching process it is shown that as k, the starting population size, tends to infinity, the rate of convergence of qk, the corresponding extinction probability, to zero is similar to that of:

k–θ, if there exists at least one subcritical state in the random environment space; xkk–α, if there exist only supercritical states in the random environment space; exp , if there exists at least one critical state and the others are supercritical in the random environment space.

Here θ, x, α and c are positive constants determined by the process.
The empirical discovery of phylogenetic invariants
Authors: Ferretti V. , Sankoff D.
Published: April 2006

An invariant Φ of a tree T under a k-state Markov model, where the time parameter is identified with the edges of T, allows us to recognize whether data on N observed species can be associated with the N terminal vertices of T in the sense of having been generated on T rather than on any other tree with N terminals. The invariance is with respect to the (time) lengths associated with the edges of the tree. We propose a general method of finding invariants of a parametrized functional form. It involves calculating the probability f of all kN data possibilities for each of m edge-length configurations of T, then solving for the parameters using the m equations of form Φ (f) = 0. We apply this to the case of quadratic invariants for unrooted binary trees with four terminals, for all k, using the Jukes–Cantor type of Markov matrix. We report partial results on finding the smallest algebraically independent set of invariants.
Point-based polygonal models for random graphs
Authors: Arak T. , Clifford P. , Surgailis D.
Published: April 2006

We define a class of two-dimensional Markov random graphs with I, V, T and Y-shaped nodes (vertices). These are termed polygonal models. The construction extends our earlier work [1]– [5]. Most of the paper is concerned with consistent polygonal models which are both stationary and isotropic and which admit an alternative description in terms of the trajectories in space and time of a one-dimensional particle system with motion, birth, death and branching. Examples of computer simulations based on this description are given.
The matrix M/M/∞ system: retrial models and Markov Modulated sources
Authors: Keilson J. , Servi L. D.
Published: April 2006

The matrix-geometric work of Neuts could be viewed as a matrix variant of M/M/1. A 2 × 2 matrix counterpart of Neuts for M/M/∞ is introduced, the stability conditions are identified, and the ergodic solution is solved analytically in terms of the ten parameters that define it. For several cases of interest, system properties can be found from simple analytical expressions or after easy numerical evaluation of Kummer functions. When the matrix of service rates is singular, a qualitatively different solution is derived. Applications to telecommunications include some retrial models and an M/M/∞ queue with Markov-modulated input.
Fluctuations of spatial branching processes with mean-field interaction
Authors: Chauvin B. , Olivares-Rieumont P. , Rouault A.
Published: April 2006

We consider a branching Brownian motion on starting with n particles of mass 1/n, with interactive branching dynamics. The parameters are unsealed, but depend on the present state of the measure-valued process. For this mean-field model, which is a generalization of Chauvin and Rouault (1990) and Nappo and Orlandi (1988), we prove a propagation of chaos and a fluctuation theorem in ([0, T]; W–5).
The reliability of a large series system under Markov structure
Authors: Chao M. T. , Fu James C.
Published: April 2006

Let Y1, · ··, Yn be a finite Markov chain and let f be a binary value function defined over the state space of the Y's. We study the reliability of general series system having the structure function φ (Y) = min {f(Y1), · ··, f(Yn)} and show that, under certain regularity conditions, the reliability of the system tends to a constant c (1 ≥ c ≥ 0), where c often has the form c = exp {–λ}.
Random set and coverage measure
Authors: Ayala Guillermo , Ferrandiz Juan , Montes Francisco
Published: April 2006

It is well known that a random set determines its random coverage measure. The paper gives a necessary and sufficient condition for the reverse implication. An equivalent formulation of the condition constitutes a first step in the search for a way to recognize a random measure as being the random coverage measure of a random set.
Limit theorems for suprema, threshold-stopped random variables and last exits of i.i.d. random variables with costs and discounting, with applications to optimal stopping
Authors: Kennedy Douglas P. , Kertz Robert P.
Published: April 2006

For linear-cost-adjusted and geometric-discounted infinite sequences of i.i.d. random variables, point process convergence results are proved as the cost or discounting effect diminishes. These process convergence results are combined with continuous-mapping principles to obtain results on joint convergence of suprema and threshold-stopped random variables, and last-exit times and locations. Applications are made to several classical optimal stopping problems in these settings.
Asymptotic properties of the least-squares method for estimating transfer functions and disturbance spectra
Authors: Ljung Lennart , Wahlberg Bo
Published: April 2006

The problem of estimating the transfer function of a linear system, together with the spectral density of an additive disturbance, is considered. The set of models used consists of linear rational transfer functions and the spectral densities are estimated from a finite-order autoregressive disturbance description. The true system and disturbance spectrum are, however, not necessarily of finite order. We investigate the properties of the estimates obtained as the number of observations tends to ∞ at the same time as the model order employed tends to ∞. It is shown that the estimates are strongly consistent and asymptotically normal, and an expression for the asymptotic variances is also given. The variance of the transfer function estimate at a certain frequency is related to the signal/noise ratio at that frequency and the model orders used, as well as the number of observations. The variance of the noise spectral estimate relates in a similar way to the squared value of the true spectrum.
The optimality of fixed channel assignment policies for cellular radio systems
Authors: Robinson Derek
Published: April 2006

In a cellular radio system a limited number of channels are available and neighbouring cells may not be allocated the same channel simultaneously because of the possibility of interference. Under heavy traffic, therefore, the average rate of losing calls may be reduced if certain calls are rejected as a matter of policy because of the potential inference they may cause. A fixed channel assignment policy is one in which each cell is allocated a fixed set of channels, this set typically being made smaller for cells likely to cause most interference. Sufficient conditions are found for the optimality of fixed channel assignment policies for a variety of layouts, and optimal and ‘good' policies are found in a number of other cases.
A simple proof of Pitman's 2M–X theorem
Authors: Imhof J. P.
Published: April 2006

Pitman has shown that if X is Brownian motion with maximum process M, then 2M – X is a BES0(3) process. We show that this can be seen by looking at finite-dimensional densities.
Optimal allocation of resources to nodes of parallel and series systems
Authors: Shaked Moshe , Shanthikumar J. George
Published: April 2006

In this paper we consider parallel and series systems, the components of which can be ‘improved'. The ‘improvement' consists of supplying the components with cold or hot standby spares or by allotting to them fixed budgets for minimal repairs. A fixed total resource of spares or minimal repairs is available. We find the optimal allocation of the resource items in several commonly encountered settings.
Two parallel processors with coupled inputs
Authors: Wright Paul E.
Published: April 2006

We consider the double queue arising from a system consisting of two processors serving three job streams generated by independent Poisson sources. The central job stream of rate v consists of jobs which place resource demands on both processors, which are handled separately by each processor once the request is made. In addition, the first processor receives background work at a rate of λwhile the second receives similar tasks at a rate η. Each processor has exponentially distributed service times with rates α and β respectively. A functional equation is found for P(z, w), the generating function of the joint queue-length distribution, which leads to a relation between P(z, 0) and P(0, w) in the region |z|, |w| < 1 of a complex algebraic curve associated with the problem. The curve is parametrized by elliptic functions z(ξ) and w(ξ) and the relation between Ρ (z(ξ), 0) and P(0, w(ξ)) persists on their analytic continuation as elliptic functions in the ξ-plane. This leads to their eventual determination by an appeal to the theory of elliptic functions. From this determination we obtain asymptotic limit laws for the expectations of the mean number of jobs in each queue conditioned on the other, as the number of jobs in both processors tends to∞. Transitions are observed in the asymptotic behavior of these quantities as one crosses various boundaries in the parameter space. An interpretation of these results via the theory of large deviations is presented.
The expected value of the one-sided cusum stopping time
Authors: Stadje Wolfgang
Published: April 2006

We derive an asymptotic relation for the expected value of the stopping time , where Sk is a random walk with negative drift.
The mean number of alleles in multigene families
Authors: Watterson G. A.
Published: April 2006

The paper considers a random sample of r chromosomes, each having n genes subject to intrachromosomal gene conversion, and mutation. The probability distribution and moments for the number of alleles present is investigated, when the number, k, of possible alleles at each locus, is either finite or infinite. Explicit formulas are given for the mean numbers of alleles on r = 1, 2, or 3 chromosomes, which simplify previously known results. For fixed r, in the infinitely-many-alleles case, the mean number increases asymptotically like r θ log (n) as n→∞, where θ is a mutation parameter. But results for large samples remain elusive.
The two-barrier problem for continuously differentiable processes
Authors: Rychlik Igor
Published: April 2006

An efficient algorithm to compute upper and lower bounds for the first-passage time in the presence of a second absorbing barrier by means of a continuously differentiable decomposable process, e.g. a smooth function of a continuously differentiable Gaussian vector field, is given. The method is used to obtain accurate approximations for the joint density of the zero-crossing wavelength and amplitude and the distribution of the rainflow cycle amplitude. Numerical examples illustrating the results are also given.
Unilateral Gaussian fields
Authors: Tory E. M. , Pickard D. K.
Published: April 2006

The necessary and sufficient condition for unilateral characterization of Gaussian Markov fields and the Besag-Moran positivity condition for second-order autonormal bilateral models define the same tetrahedral domain of achievable regression parameters. A bijective function maps this domain to a different tetrahedral domain of parameters in the Pickard model. These two domains are identical to the corresponding ones in the Welberry-Carroll model. We obtain series solutions for correlation coefficients and study their limits near the boundaries of the first domain.
Limit distributions of maximal segmental score among Markov-dependent partial sums
Authors: Karlin Samuel , Dembo Amir
Published: April 2006

Let s1, …, sn be generated governed by an r-state irreducible aperiodic Markov chain. The partial sum process is determined by a realization of states with s0 = α and the real-valued i.i.d. bounded variables Xαß associated with the transitions si = α, si+1 = β. Assume Χ αβ has negative stationary mean. The explicit limit distribution of the maximal segmental sum is derived. Computational methods with potential applications to the analysis of random Markov-dependent letter sequences (e.g. DNA and protein sequences) are presented.
Stochastic order for redundancy allocations in series and parallel systems
Authors: Boland Philip J. , El-Neweihi Emad , Proschan Frank
Published: April 2006

The problem of where to allocate a redundant component in a system in order to optimize the lifetime of a system is an important problem in reliability theory which also poses many interesting questions in mathematical statistics. We consider both active redundancy and standby redundancy, and investigate the problem of where to allocate a spare in a system in order to stochastically optimize the lifetime of the resulting system. Extensive results are obtained in particular for series and parallel systems.
The efficiency and heavy traffic properties of the score function method in sensitivity analysis of queueing models
Authors: Asmussen Søren , Rubinstein Reuven Y.
Published: April 2006

This paper studies computer simulation methods for estimating the sensitivities (gradient, Hessian etc.) of the expected steady-state performance of a queueing model with respect to the vector of parameters of the underlying distribution (an example is the gradient of the expected steady-state waiting time of a customer at a particular node in a queueing network with respect to its service rate). It is shown that such a sensitivity can be represented as the covariance between two processes, the standard output process (say the waiting time process) and what we call the score function process which is based on the score function. Simulation procedures based upon such representations are discussed, and in particular a control variate method is presented. The estimators and the score function process are then studied under heavy traffic conditions. The score function process, when properly normalized, is shown to have a heavy traffic limit involving a certain variant of two-dimensional Brownian motion for which we describe the stationary distribution. From this, heavy traffic (diffusion) approximations for the variance constants in the large sample theory can be computed and are used as a basis for comparing different simulation estimators. Finally, the theory is supported by numerical results.
Light traffic approximations in many-server queues
Authors: Daley D. J. , Rolski T.
Published: April 2006

This paper complements two previous studies (Daley and Rolski (1984), (1991)) by investigating limit properties of the waiting time ink-server queues with renewal arrival process under ‘light traffic' conditions. Formulae for the limits of the probability of waiting and the waiting time moments are derived for the two approaches of dilation and thinning of the arrival process. Asmussen's (1991) approach to light traffic limits applies to the cases considered, of which the Poisson arrival process (i.e.M/G/k) is a special case and for which formulae are given.
A note on one-dimensional chaotic maps under time reversal
Authors: Tong H. , Cheng B.
Published: April 2006

We have furnished further examples on the connection between some standard one-dimensional chaotic deterministic models and stochastic time series models via time reversal.
On the probability that the kth customer finds an M/M/1 queue empty
Authors: Singh Harshinder , Gupta Rameshwar D.
Published: April 2006

A result relating the probability that kth customer finds the system empty to the distribution of the number of customers served in a busy period, for an M/M/1 queue, has been obtained. This relationship is similar to the relationship between the probability that the queue is empty at time t and the distribution of the length of the busy period.
On blocking in loss networks
Authors: Zachary S.
Published: April 2006

We consider a ‘reduced state space' approach to the analysis of blocking in stochastic loss networks. We show how this approach provides insight into the approximations currently used in large networks and enables improved approximations to be deduced. We further give some ‘heavy traffic' asymptotic results for the limiting scheme of Kelly (1986).
Optimality of threshold policies in single-server queueing systems with server vacations
Authors: Federgruen Awi , So Kut C.
Published: April 2006

In this paper we consider a class of single-server queueing systems with compound Poisson arrivals, in which, at service completion epochs, the server has the option of taking off for one or several vacations of random length. The cost structure consists of a holding cost rate specified by a general non-decreasing function of the queue size, fixed costs for initiating and terminating service, and a variable operating cost incurred for each unit of time that the system is in operation. We show under some weak conditions with respect to the holding cost rate function and the service time, vacation time and arrival batch size distributions that it is either optimal among all feasible (stationary and non-stationary) policies never to take a vacation, or it is optimal to take a vacation when the system empties out and to resume work when, upon completion of a vacation, the queue size is equal to or in excess of a critical threshold. These optimality results are generalized for several variants of this model.
The mean waiting time in aG/G/m/∞queue with the LCFS-P service discipline
Authors: Ritter Gunter , Wacker Ulrich
Published: April 2006

A single- or multiserver queue with work-conserving service discipline and a stationary and ergodic input stream with bounded service times and arbitrarily light traffic intensity may have infinite mean waiting time. We give an example of this paradox and we also give a mixing condition which, in the case of the preemptive-resume LCFS discipline, excludes this phenomenon. Furthermore, the same methods allow to estimate the durations of the first busy period and cycle and the number of customers served in the first busy cycle of a work-conserving queue.
On the starshapeness of G/G/c queueing systems
Authors: Shanthikumar J. George , Wu Couchen
Published: April 2006

In this paper we show that the waiting and the sojourn times of a customer in a single-stage, multiple-server, G/G/c queueing system are increasing and starshaped with respect to the mean service time. Usefulness of this result in the design of the optimal service speed in the G/G/c queueing system is also demonstrated.
Limit theorems for loss networks with diverse routing
Authors: Ziedins I. B. , Kelly F.P.
Published: April 2006

Loss networks have long been of interest to telephone engineers, and are becoming increasingly important as models of computer and information systems. In this paper we present an asymptotic analysis of loss networks exhibiting various forms of symmetry. Our aim is to better understand the behaviour of networks involving very large numbers of links and routes, where an exact analysis is not possible and approximations are required.
Customer routing to different servers with complete information
Authors: Rosberg Zvi , Kermani Parviz
Published: April 2006

In this paper we consider a queueing system having n exponential servers, each with its own queue and service rate. Customers arrive according to a Poisson process with rate λ, and upon arrival each customer must be routed to some server's queue. No jockeying amongst the queues is allowed and each server serves its queue according to a first-come-first-served discipline.

Each server i, 1 ≦ i ≦ n, provides service with a state-dependent rate μ(i)(k), k = 0, 1, …. In addition, at every queue i, there is a deterministic holding cost which occurs at rate h(i)(k) while there are k customers at the queue.

An admissible routing policy is a policy that assigns each arriving customer to one of the queues. A decision at time t may be randomized and dependent on the queue lengths and decisions till time t. An optimal routing policy is an admissible policy that minimizes the long-run average holding cost.

In this study, we bound the optimal cost from below, by considering an ideal system, where each server optimally selects a given proportion of customers, irrespective of other servers' selections. From this ideal system we construct a class of admissible routing policies, the overflow routing class, that approximates the ideal situation for each server. Finally, we evaluate the policies and compare them to the lower bound.
Exact analysis for a class of simple, circuit-switched networks with blocking
Authors: Kogan Yaakov
Published: April 2006

We consider the same circuit switching problem as in Mitra [1]. The calculation of the blocking probabilities is reduced to finding the partition function for a closed exponential pseudo-network with L−1 customers. This pseudo-network differs from that in [1] in one respect only: service rates at nodes 1, 2, …, p depend on the queue length. The asymptotic expansion developed in [1] follows from our exact expression for the partition function.
An invariance relationship for the G/G/1 queue
Authors: Sengupta Bhaskar
Published: April 2006

In this note, we show that for a stationary FCFS G/G/1 queue, the virtual waiting time and the time spent in the system by the customer in service have the same distribution. We assume that the latter is zero if the queue is empty.
The final size and severity of a generalised stochastic multitype epidemic model
Authors: Ball Frank , Clancy Damian
Published: April 2006

We consider a stochastic model for the spread of an epidemic amongst a population split intomgroups, in which infectives move among the groups and contact susceptibles at a rate which depends upon the infective's original group, its current group, and the group of the susceptible. The distributions of total size and total area under the trajectory of infectives for such epidemics are analysed. We derive exact results in terms of multivariate Gontcharoff polynomials by treating our model as a multitype collective Reed–Frost process and slightly adapting the results of Picard and Lefèvre (1990). We also derive asymptotic results, as each of the group sizes becomes large, by generalising the method of Scalia-Tomba (1985), (1990).
Explosive Markov branching processes: entrance laws and limiting behaviour
Authors: Pakes Anthony G.
Published: April 2006

The supercritical Markov branching process is examined in the case where the minimal version of the process has strictly substochastic transition laws. This provides a nice example of the general construction theory for discrete-state Markov processes.

Entrance laws corresponding to the minimal process are characterised. Limit properties of the processes constructed from these entrance laws are examined. All such processes which are honest and cannot hit zero are ergodic. Otherwise these processes are λ-positive and limit theorems conditional on not having left the positive states are given.

A connection is made with recent work on the general construction problem when a λ-subinvariant measure is given. The case where immigration is allowed is mentioned.
General optimal stopping theorems for semi-Markov processes
Authors: Boshuizen Frans A. , Gouweleeuw José M.
Published: April 2006

In this paper, optimal stopping problems for semi-Markov processes are studied in a fairly general setting. In such a process transitions are made from state to state in accordance with a Markov chain, but the amount of time spent in each state is random. The times spent in each state follow a general renewal process. They may depend on the present state as well as on the state into which the next transition is made.

Our goal is to maximize the expected net return, which is given as a function of the state at time t minus some cost function. Discounting may or may not be considered. The main theorems (Theorems 3.5 and 3.11) are expressions for the optimal stopping time in the undiscounted and discounted case. These theorems generalize results of Zuckerman [16] and Boshuizen and Gouweleeuw [3]. Applications are given in various special cases.

The results developed in this paper can also be applied to semi-Markov shock models, as considered in Taylor [13], Feldman [6] and Zuckerman [15].
Optimal allocation under partial ordering of lifetimes of components
Authors: El-Neweihi Emad , Sethuraman Jayaram
Published: April 2006

Assembly of systems to maximize reliability when certain components of the systems can be bolstered in different ways is an important theme in reliability theory. This is done under assumptions of various stochastic orderings among the lifetimes of the components and the spares used to bolster them. The powerful techniques of Schur and arrangement increasing functions are used in this paper to pinpoint optimal allocation results in different settings involving active and standby redundancy allocation, minimal repair and shock-threshold models.
Partial orderings under cumulative damage shock models
Authors: Pellerey Franco
Published: April 2006

Two devices are subjected to common shocks arriving according to two identical counting processes. Let and denote the probability of surviving k shocks for the first and the second device, respectively. We find conditions on the discrete distributions and in order to obtain the failure rate order (FR), the likelihood ratio order (LR) and the mean residual order (MR) between the random lifetimes of the two devices. We also obtain sufficient conditions under which the above mentioned relations between the discrete distributions are verified in some cumulative damage shock models.
On the optimality of LEPT and μc rules for parallel processors and dependent arrival processes
Authors: Hordijk Arie , Koole Ger
Published: April 2006

In this paper we study scheduling problems of multiclass customers on identical parallel processors. A new type of arrival process, called a Markov decision arrival process, is introduced. This arrival process can be controlled and allows for an indirect dependence on the numbers of customers in the queues. As a special case we show the optimality of LEPT and the µc-rule in the last node of a controlled tandem network for various cost structures. A unifying proof using dynamic programming is given.
The survival of various interacting particle systems
Authors: Sudbury Aidan
Published: April 2006

Particles may be removed from a lattice by murder, coalescence, mutual annihilation and simple death. If the particle system is not to die out, the removed particles must be replaced by births. This letter shows that coalescence can be counteracted by arbitrarily small birth-rates and contrasts this with the situations for annihilation and pure death where there are critical phenomena. The problem is unresolved for murder.
An Iterative Monte Carlo Scheme for Generating Lie Group-Valued Random Variables
Authors: Piccioni Mauro , Scarlatti Sergio
Published: April 2006

In this paper a simple approximation scheme is proposed for the problem of generating and computing expectations of functionals of a wide class of random variables with values in a compact Lie group. The algorithm is suggested by the time-discretization of an ergodic diffusion leaving invariant the distribution of interest. It is shown to converge as the discretization step goes to zero with the iterations in a natural way.
The Final State of an Epidemic in a Large Heterogeneous Population with a Large Initial Number of Infectives
Authors: Butler Steven M.
Published: April 2006

We describe some asymptotic properties of a general S–I–R epidemic process in a large heterogeneous population. We assume that the infectives behave independently, that each infective has a generally distributed random number of contacts with the others in the population, and that among the initial susceptibles there is an arbitrary initial distribution of susceptibility. For the case of a large number of initial infectives, we demonstrate the asymptotic normality of the final size distribution as well as convergence of the final distribution of susceptibility as the population size approaches infinity. The relationship between the mean of the limiting final size distribution and the initial heterogeneity of susceptibility is explored, for a parametric example.
Approach to Stationarity of the Bernoulli–Laplace Diffusion Model
Authors: Donnelly Peter , Lloyd Peter , Sudbury Aidan
Published: April 2006

Two urns initially containrred balls andn – rblack balls respectively. At each time epoch a ball is chosen randomly from each urn and the balls are switched. Effectively the same process arises in many other contexts, notably for a symmetric exclusion process and random walk on the Johnson graph. IfY(·) counts the number of black balls in the first urn then we give a direct asymptotic analysis of its transition probabilities to show that (when run at rate (n – r)/nin continuous time) forasn→∞, whereπndenotes the equilibrium distribution ofY(·) andγα= 1 –α/β(1 –β). Thus for largenthe transient probabilities approach their equilibrium values at time logn+ log|γα| (≦logn) in a particularly sharp manner. The same is true of the separation distance between the transient distribution and the equilibrium distribution. This is an explicit analysis of the so-called cut-off phenomenon associated with a wide variety of Markov chains.
Semi-Markov Replacement Chains
Authors: Gerontidis Ioannis I.
Published: April 2006

We consider an absorbing semi-Markov chain for which each time absorption occurs there is a resetting of the chain according to some initial (replacement) distribution. The new process is a semi-Markov replacement chain and we study its properties in terms of those of the imbedded Markov replacement chain. A time-dependent version of the model is also defined and analysed asymptotically for two types of environmental behaviour, i.e. either convergent or cyclic. The results contribute to the control theory of semi-Markov chains and extend in a natural manner a wide variety of applied probability models. An application to the modelling of populations with semi-Markovian replacements is also presented.
A heuristic proof of a long-standing conjecture of D. G. Kendall concerning the shapes of certain large random polygons
Authors: Miles R. E.
Published: April 2006

In the early 1940s David Kendall conjectured that the shapes of the ‘large' (i.e. large areaA)convex polygons determined by a standard Poisson line process in the plane tend to circularity (asAincreases). Subject only to one heuristic argument, this conjecture and the corresponding two results withAreplaced in turn by number of sidesNand perimeterS,are proved. Two further similar limiting distributions are considered and, finally, corresponding limiting non-deterministic shape distributions for the small polygons are determined.
The genealogy of branching processes and the age of our most recent common ancestor
Authors: O'Connell Neil
Published: April 2006

We obtain a weak approximation for the reduced family tree in a near-critical Markov branching process when the time interval considered is long; we also extend Yaglom's theorem and the exponential law to this case. These results are then applied to the problem of estimating the age of our most recent common female ancestor, using mitochondrial DNA sequences taken from a sample of contemporary humans.
A functional central limit theorem for the jump counts of Markov processes with an application to Jackson networks
Authors: Anantharam Venkat , Konstantopoulos Takis
Published: April 2006

Each feasible transition between two distinct statesiandjof a continuous-time, uniform, ergodic, countable-state Markov process gives a counting process counting the number of such transitions executed by the process. Traffic processes in Markovian queueing networks can, for instance, be represented as sums of such counting processes. We prove joint functional central limit theorems for the family of counting processes generated by all feasible transitions. We characterize which weighted sums of counts have zero covariance in the limit in terms of balance equations in the transition diagram of the process. Finally, we apply our results to traffic processes in a Jackson network. In particular, we derive simple formulas for the asymptotic covariances between the processes counting the number of customers moving between pairs of nodes in such a network.
The probability of large queue lengths and waiting times in a heterogeneous multiserver queue II: Positive recurrence and logarithmic limits
Authors: Sadowsky John S.
Published: April 2006

We continue our investigation of the batch arrival-heterogeneous multiserver queue begun in Part I. In a general setting we prove the positive Harris recurrence of the system, and with no additional conditions we prove logarithmic tail limits for the stationary queue length and waiting time distributions.
Co-Existence of the occupied and vacant phase in boolean models in three or more dimensions
Authors: Sarkar Anish
Published: April 2006

Consider a continuum percolation model in which, at each point of ad-dimensional Poisson process of rate λ, a ball of radius 1 is centred. We show that, for anyd≧ 3, there exists a phase where both the regions, occupied and vacant, contain unbounded components. The proof uses the concept of enhancement for the Boolean model, and along the way we prove that the critical intensity of a Boolean model defined on a slab is strictly larger than the critical intensity of a Boolean model defined on the whole space.
Extreme Value Theory for a Class of Markov Chains with Values in ℝd
Authors: Perfekt Roland
Published: April 2006

We consider extreme value theory for a class of stationary Markov chains with values in ℝd. The asymptotic distribution of Mn, the vector of componentwise maxima, is determined under mild dependence restrictions and suitable assumptions on the marginal distribution and the transition probabilities of the chain. This is achieved through computation of a multivariate extremal index of the sequence, extending results of Smith [26] and Perfekt [21] to a multivariate setting. As a by-product, we obtain results on extremes of higher-order, real-valued Markov chains. The results are applied to a frequently studied random difference equation.