bluuebunny/crossref_metadata_2025 huggingface dataset:
The shapes of a random sequence of triangles
Authors: Watson G. S.
Published: April 2006

A triangle with vertices z1, z2, z3 in the complex plane may be denoted by a vector Z, Z = [z1, z2, z3]t. From a sequence of independent and identically distributed 3×3 circulants {Cj}∞1, we may generate from Z1 the sequence of vectors or triangles {Zj}∞1, by the rule Zj = CjZj–1 (j> 1), Z1=Z. The ‘shape’ of a set of points, the simplest case being three points in the plane has been defined by Kendall (1984). We give several alternative, ab initio discussions of the shape of a triangle, and proofs of a limit theorem for shape of the triangles in the sequence {Zj}∞1. In Appendix A, the shape concept is applied to the zeros of a cubic polynomial. Appendix B contains some further remarks about shape. Appendix C uses the methods of this paper to give proofs of generalizations of two old theorems on triangles.
The caudal characteristic curve of queues
Authors: Neuts Marcel F.
Published: April 2006

Many queues and related stochastic models, and in particular those that have a matrix-geometric stationary probability vector, have steady-state queue-length densities that are asymptotically geometric. The graph of the asymptotic rate η of these densities as a function of the traffic intensity ρ is the caudal characteristic curve. This is an informative graph from which a number of qualitative inferences about the behavior of the queue may be drawn.

The caudal characteristic curve may be computed (by elementary algorithms) for several useful models for which a complete exact numerical solution is not practically feasible. These include queues with certain types of superimposed arrival processes and/or multiple non-exponential servers. The necessary theorems which lead to the algorithmic procedures as well as the interpretation of several numerical examples are discussed.
On the time spent above a level by Brownian motion with negative drift
Authors: Imhof J.-P.
Published: April 2006

Limit theorems of Berman involve the total time spent by Brownian motion with negative drift above a fixed or exponentially distributed negative level. We give explicitly the probability densities and distribution functions, obtained via an equivalence of laws.
Perturbation theory for Markov reward processes with applications to queueing systems
Authors: Van Dijk Nico M. , Puterman Martin L.
Published: April 2006

We study the effect of perturbations in the data of a discrete-time Markov reward process on the finite-horizon total expected reward, the infinite-horizon expected discounted and average reward and the total expected reward up to a first-passage time. Bounds for the absolute errors of these reward functions are obtained. The results are illustrated for a finite as well as infinite queueing systems (M/M/1/S and ). Extensions to Markov decision processes and other settings are discussed.
Transient behavior of theM/M/1 queue via Laplace transforms
Authors: Abate Joseph , Whitt Ward
Published: April 2006

This paper shows how the Laplace transform analysis of Bailey (1954), (1957) can be continued to yield additional insights about the time-dependent behavior of the queue-length process in theM/M/1 model. A transform factorization is established that leads to a decomposition of the first moment as a function of time into two monotone components. This factorization facilitates developing approximations for the moments and determining their asymptotic behavior as. All descriptions of the transient behavior are expressed in terms of basic building blocks such as the first-passage-time distributions. The analysis is facilitated by appropriate scaling of space and time so that regulated or reflected Brownian motion (RBM) appears as the special case in which the traffic intensity ρ equals the critical value 1. An operational calculus is developed for obtainingM/M/1 results directly from corresponding RBM results as well as vice versa. The analysis thus provides useful insight about RBM approximations for queues.
Characterizations of a multivariate extreme value distribution
Authors: Takahashi Rinya
Published: April 2006

Characterizations of a multivariate extreme value distribution in terms of its marginals are established.
On the genealogy of nested subsamples from a haploid population
Authors: Saunders Ian W. , Tavaré Simon , Watterson G. A.
Published: April 2006

For the haploid genetic model of Moran, the joint distribution of the numbers of distinct ancestors of a collection of nested subsamples is derived. These results are shown to apply to the diffusion approximations of a wide variety of other genetic models, including the Wright–Fisher process. The results allow us to relate the ancestries of populations sampled at different times. Analogous results for a line-of-descent process that incorporates the effect of mutation are given. Some results about the ages of alleles in an infinite-alleles model are described.
Damped vibrations excited by white noise
Authors: Orsingher Enzo
Published: April 2006

Let v(x, t) denote the displacement of an infinitely long, idealized string performing damped vibrations caused by white noise.

Upper and lower bounds for the distribution of maxsv(x, s) and maxxv(x, t) are presented. The results are obtained by adapting Lévy-type inequalities and exploiting a connection of v(x, t) with the Ornstein-Uhlenbeck process through Slepian's theorem.

The case of forced-damped vibrations is also analysed. Finally, a section is devoted to the case of a semi-infinite string performing damped vibrations.
A new informative embedded Markov renewal process for the PH/G/1 queue
Authors: Neuts Marcel F.
Published: April 2006

We consider a new embedded Markov chain for the PH/G/1 queue by recording the queue length, the phase of the arrival process and the number of services completed during the current busy period at the successive departure epochs. Algorithmically tractable matrix formulas are obtained which permit the analysis of the fluctuations of the queue length and waiting times during a typical busy cycle. These are useful in the computation of certain profile curves arising in the statistical analysis of queues. In addition, informative expressions for the mean waiting times in the stable GI/G/1 queue and a simple new algorithm to evaluate the waiting-time distributions for the stationary PH/PH/1 queue are obtained.
Improved upper bounds for the availabilities in a fixed time interval for multistate monotone systems
Authors: Natvig Bent
Published: April 2006

It is here shown how the upper bounds given in Funnemark and Natvig (1985) can easily be improved.
On the ferromagnetic and the percolative region of random spin systems
Authors: Georgii Hans-Otto
Published: April 2006

We consider d-dimensional lattice systems of bounded real-valued spins with ferromagnetic random interaction between nearest neighbours. We establish an outer and, in two dimensions, an inner bound of the parameter region where spontaneous magnetization occurs. These bounds provide an estimate of the singularity of the critical temperature at the threshold for percolation through active bonds. We derive a relationship between the ferromagnetic region and the percolative region for a correlated site–bond percolation problem, and we investigate the latter. Bounds for the level sets of the expected magnetization are also obtained.
Distributions that are both subexponential and in the domain of attraction of an extreme-value distribution
Authors: Goldie Charles M. , Resnick Sidney
Published: April 2006

When does a distributionFhave the property of both being in the domain of attraction of exp {–e–x} and having a second convolution-power tail equivalent to the first:Sufficient conditions and examples are given.
The analysis of finite security markets using martingales
Authors: Taqqu Murad S. , Willinger Walter
Published: April 2006

The theory of finite security markets developed by Harrison and Pliska [1] used the separating hyperplane theorem to establish the relationship between the lack of arbitrage opportunities and the existence of a certain martingale measure. In this paper we treat this theory by examining certain geometric properties of the sample paths of the price process, that is, we focus on the price increments of the stocks between one time period to the next and convert them to martingale differences through an equivalent change of measure. Thus, in contrast to Harrison and Pliska&s functional analytic derivation, our approach is based on probabilistic methods and allows a geometric interpretation which not only provides a connection to linear programming but also yields an algorithm for analyzing finite security markets. Moreover, we can make precise the connection between diverse expressions of economic equilibrium such as ‘absence of arbitrage’, ‘martingale property, and ‘complementary slackness property’.
On the first hitting time and the last exit time for a Brownian motion to/from a moving boundary
Authors: Salminen Paavo
Published: April 2006

Let t → h(t) be a smooth function on ℝ+, and B = {Bs; s ≥ 0} a standard Brownian motion. In this paper we derive expressions for the distributions of the variables Th: = inf {S; Bs = h(s)} and λth: = sup {s ≦ t; Bs = h(s)}, where t> 0 is given. Our formulas contain an expected value of a Brownian functional. It is seen that this can be computed, principally, using Feynman–Kac&s formula. Further, we discuss in our framework the familiar examples with linear and square root boundaries. Moreover our approach provides in some extent explicit solutions for the second-order boundaries.
On the weak convergence of stochastic processes with embedded point processes
Authors: Konstantopoulos Panagiotis , Walrand Jean
Published: April 2006

We consider a stochastic process in continuous time and two point processes on the real line, all jointly stationary. We show that under a certain mixing condition the values of the process at the points of the second point process converge weakly under the Palm distribution with respect to the first point process, and we identify the limit. This result is a supplement to two other known results which are mentioned below.
An approximation of stopped sums with applications in queueing theory
Authors: Csörgő Miklós , Deheuvels Paul , Horváth Lajos
Published: April 2006

We prove strong approximations for partial sums indexed by a renewal process. The obtained results are optimal. The established probability inequalities are also used to get bounds for the rate of convergence of some limit theorems in queueing theory.
A note on repeated sequences in Markov chains
Authors: Biggins J. D.
Published: April 2006

If (non-overlapping) repeats of specified sequences of states in a Markov chain are considered, the result is a Markov renewal process. Formulae somewhat simpler than those given in Biggins and Cannings (1987) are derived which can be used to obtain the transition matrix and conditional mean sojourn times in this process.
On the amount of detail that can be recovered from a degraded signal
Authors: Hall Peter
Published: April 2006

Motivated by applications in digital image processing, we discuss information-theoretic bounds to the amount of detail that can be recovered from a defocused, noisy signal. Mathematical models are constructed for test-pattern, defocusing and noise. Using these models, upper bounds are derived for the amount of detail that can be recovered from the degraded signal, using any method of image restoration. The bounds are used to assess the performance of the class of linear restorative procedures. Certain members of the class are shown to be optimal, in the sense that they attain the bounds, while others are shown to be sub-optimal. The effect of smoothness of point-spread function on the amount of resolvable detail is discussed concisely.
Preserving partial balance in continuous-time Markov chains
Authors: Pollett P. K.
Published: April 2006

Recently a number of authors have considered general procedures for coupling stochastic systems. If the individual components of a system, when considered in isolation, are found to possess the simplifying feature of either reversibility, quasireversibility or partial balance they can be coupled in such a way that the equilibrium analysis of the system is considerably simpler than one might expect in advance. In particular the system usually exhibits a product-form equilibrium distribution and this is often insensitive to the precise specification of the individual components. It is true, however, that certain kinds of components lose their simplifying feature if the specification of the coupling procedure changes. From a practical point of view it is important, therefore, to determine if, and then under what conditions, the revelant feature is preserved.

In this paper we obtain conditions under which partial balance in a component is preserved and these often amount to the requirement that there exists a quantity which is unaffected by the internal workings of the component in question. We give particular attention to the components of a stratified clustering process as these most often suffer from loss of partial balance.
Optimal selection of stochastic intervals under a sum constraint
Authors: Coffman E. G. , Flatto L. , Weber R. R.
Published: April 2006

We model a selection process arising in certain storage problems. A sequence (X1, · ··, Xn) of non-negative, independent and identically distributed random variables is given. F(x) denotes the common distribution of the Xi′s. With F(x) given we seek a decision rule for selecting a maximum number of the Xi′s subject to the following constraints: (1) the sum of the elements selected must not exceed a given constant c > 0, and (2) the Xi′s must be inspected in strict sequence with the decision to accept or reject an element being final at the time it is inspected.

We prove first that there exists such a rule of threshold type, i.e. the ith element inspected is accepted if and only if it is no larger than a threshold which depends only on i and the sum of the elements already accepted. Next, we prove that if F(x) ~ Axα as x → 0 for some A, α> 0, then for fixed c the expected number, En(c), selected by an optimal threshold is characterized by

Asymptotics as c → ∞and n → ∞with c/n held fixed are derived, and connections with several closely related, well-known problems are brought out and discussed.
The Berry-Esseen bound for the Poisson shot-noise
Authors: Lane John A.
Published: April 2006

This note provides a useful extension of the Berry–Esseen bound on the error in the normal approximation for shot-noise. The special cases treated are of particular interest in the statistical analysis of Poisson processes and cluster point processes.
Stochastic annealing for nearest-neighbour point processes with application to object recognition
Authors: Van Lieshout M. N. M.
Published: April 2006

We study convergence in total variation of non-stationary Markov chains in continuous time and apply the results to the image analysis problem of object recognition. The input is a grey-scale or binary image and the desired output is a graphical pattern in continuous space, such as a list of geometric objects or a line drawing. The natural prior models are Markov point processes found in stochastic geometry. We construct well-defined spatial birth-and-death processes that converge weakly to the posterior distribution. A simulated annealing algorithm involving a sequence of spatial birth-and-death processes is developed and shown to converge in total variation to a uniform distribution on the set of posterior mode solutions. The method is demonstrated on a tame example.
Comparison of sequential and continuous inspection strategies for deteriorating systems
Authors: Lam C. Teresa , Yeh R. H.
Published: April 2006

This paper investigates inspection strategies for a finite-state continuous-time Markovian deteriorating system. Two inspection strategies are considered: sequential inspection and continuous inspection. Unlike many previous efforts, the inspection times for the sequential inspection strategy are assumed to be non-negligible. The replacement times and costs for both strategies are non-negligible and state dependent. Our objective here is to minimize the expected long-run cost rate. Iterative algorithms are provided to derive the optimal policies for both strategies. The structures of these optimal policies and their corresponding optimal cost rates are discussed and compared.
On the representation of symmetric transition functions
Authors: Anderson W. J. , McDunnough P. M.
Published: April 2006

In this paper, we give an alternative derivation of Kendall's representation for symmetric transition functions which relies on the backward and/or forward integral recursions. The proof uses a lemma concerning approximation by finite sections (which is useful in its own right) and is similar to the original proof for birth and death processes by Lederman and Reuter. Finally, we obtain a general result guaranteeing the existence of representations of transition functions such as those obtained by Pruitt and Iglehart.
Expected number of departures in M/M/1 and G/G/1 queues
Authors: Ali Hydar
Published: April 2006

For an initially empty M/M/1 queue, it is shown that the transform of the expectation of the number of departures in the interval (0, t] is invariant under an interchange of arrival and service rates. However, in the GI/G/1 queue with an initial single customer, the corresponding transform does not have this symmetric property.
A bang-bang strategy for a finite fuel stochastic control problem
Authors: Sudderth W. D. , Weerasinghe A. P. N.
Published: April 2006

The problem treated is that of controlling a process

with values in [0, a]. The non-anticipative controls (µ(t), σ(t)) are selected from a set C(x) whenever X(t–) = x and the non-decreasing process A(t) is chosen by the controller subject to the condition where y is a constant representing the initial amount of fuel. The object is to maximize the probability that X(t) reaches a. The optimal process is determined when the function has a unique minimum on [0, a] and satisfies certain regularity conditions. The optimal process is a combination of ‘timid play' in which fuel is used gradually in the form of local time at 0, and ‘bold play' in which all the fuel is used at once.
The biased annihilating branching process
Authors: Neuhauser Claudia , Sudbury Aidan
Published: April 2006

In the biased annihilating branching process, particles place offspring on empty neighboring sites at rate A and destroy neighbors at rate 1. It is conjectured that for any λ ≥ 0 the population will spread to ∞, and this is shown in one dimension for The process on a finite graph when starting with a non-empty configuration has limiting distribution vλ /(λ +1), the product measure with density λ/(1 +λ). It is shown that vλ /(λ +1) and δ Ø are the only stationary distributions on Moreover, if and the initial configuration is non-empty, then the limiting measure is vλ /(λ +1) provided the initial measure converges.
Asymptotic stationarity of multichannel queues
Authors: Szczotka Władysław
Published: April 2006

The paper deals with asymptotic stationarity of the processwhereis a vector inwith non-negative coordinates,is an-valued process,Sis a separable metric space and all operations inare meant in the coordinate-wise sense. It is shown that a type of asymptotic stationarity of (X, Y), together with some conditions, implies the same type of asymptotic stationarity of (w, X, Y). This result is applied to analyze asymptotic stationarity of multichannel queues. It may also be used to analyze asymptotic stationarity of series of multichannel queues.
Product forms for queueing networks with state-dependent multiple job transitions
Authors: Boucherie Richard J. , Van DIJK Nico M.
Published: April 2006

A general framework of continuous-time queueing networks is studied with simultaneous state dependent service completions such as due to concurrent servicing or discrete-time slotting and with state dependent batch routings such as most typically modelling blocking. By using a key notion of group-local-balance, necessary and sufficient conditions are given for the stationary distribution to be of product form. These conditions and a constructive computation of the product form are based upon merely local solutions of the group-local-balance equations which can usually be solved explicitly for concrete networks. Moreover, a decomposition theorem is presented to separate service and routing conditions. General batch service and batch routing examples yielding a product form are hereby concluded. As illustrated by various examples, known results on both discrete- and continuous-time queueing networks are unified and extended.
A two-point Markov chain boundary-value problem
Authors: Daley D. J. , Servi L. D.
Published: April 2006

The two-point Markov chain boundary-value problem discussed in this paper is a finite-time version of the quasi-stationary behaviour of Markov chains. Specifically, for a Markov chain {Xt:t= 0, 1, ·· ·}, given the time interval (0,n), the interest is in describing the chain at some intermediate time point rconditional on knowing boththe behaviour of the chain at the initial time point 0 and that over the interval (0,n) it has avoided some subsetBof the state space. The paper considers both ‘real time' estimates forr=n(i.e. the chain has avoidedBsince 0), anda posterioriestimates forr<nwith at least partial knowledge of the behaviour ofXn.Algorithms to evaluate the distribution ofXrcan be as small asO(n3) (and, for practical purposes, evenO(n2logn)). The estimates may be stochastically ordered, and the process (and hence, the estimates) may be spatially homogeneous in a certain sense. Maximum likelihood estimates of the sample path are furnished, but by example we note that these ML paths may differ markedly from the path consisting of the expected or average states. The scope for two-point boundary-value problems to have solutions in a Markovian setting is noted.

Several examples are given, together with a discussion and examples of the analogous problem in continuous time. These examples include the basicM/G/kqueue and variants that include a finite waiting room, reneging, balking, and Bernoulli feedback, a pure birth process and the Yule process. The queueing examples include Larson's (1990) ‘queue inference engine'.
Properties of the spatial unilateral first-order ARMA model
Authors: Basu Sabyasachi , Reinsel Gregory C.
Published: April 2006

For two-dimensional spatial data, a spatial unilateral autoregressive moving average (ARMA) model of first order is defined and its properties studied. The spatial correlation properties for these models are explicitly obtained, as well as simple conditions for stationarity and conditional expectation (interpolation) properties of the model. The multiplicative or linear-by-linear first-order spatial models are seen to be a special case which have proved to be of practical use in modeling of two-dimensional spatial lattice data, and hence the more general models should prove to be useful in applications. These unilateral models possess a convenient computational form for the exact likelihood function, which gives proper treatment to the border cell values in the lattice that have a substantial effect in estimation of parameters. Some simulation results to examine properties of the maximum likelihood estimator and a numerical example to illustrate the methods are briefly presented.
The steady-state appearance of the M/G/1 queue under the discipline of shortest remaining processing time
Authors: Schassberger R.
Published: April 2006

For the queue M/G/1 under the discipline SRPT (shortest remaining processing time) the system state is taken to be the counting measure N which assigns to each Borel set A of R+ the number N(A) of customers present with residual service times taking values in A. A steady-state analysis is given for the corresponding Laplace functional. As a corollary, the steady-state number in queue is obtained in terms of its generating function.
Rapid variation with remainder and rates of convergence
Authors: Beirlant J. , Willekens E.
Published: April 2006

In this paper, we refine the concept of Γ-variation up to second order, and we give a characterization of this type of asymptotic behaviour. We apply our results to obtain uniform rates of convergence in the weak convergence of renormalised sample maxima to the double exponential distribution. In a second application we derive a rate of convergence result for the Hill estimator.
A star-like circuit-switching network with multistage service
Authors: Khalil Z. , Falin G.
Published: April 2006

A star-like circuit-switching network with multistage service is considered. Likelihood ratio ordering is used to show that there exists an optimal threshold for the mean number of messages processed through the network as a function of the input traffic intensity.
Asymptotic Properties of Estimators for the Parameters of Spatial Inhomogeneous Poisson Point Processes
Authors: Rathbun Stephen L. , Cressie Noel
Published: April 2006

Consider a spatial point pattern realized from an inhomogeneous Poisson process on a bounded Borel set, with intensity functionλ(s;θ),where. In this article, we show that the maximum likelihood estimatorand the Bayes estimatorare consistent, asymptotically normal, and asymptotically efficient as the sample region. These results extend asymptotic results of Kutoyants (1984), proved for an inhomogeneous Poisson process on [0,T], whereT→∞. They also formalize (and extend to the multiparameter case) results announced by Krickeberg (1982), for the spatial domain. Furthermore, a Cramér–Rao lower bound is found for any estimatorofθ.The asymptotic properties ofandare considered for modulated (Cox (1972)), and linear Poisson processes.
Stochastic Scheduling in in-Forest Networks
Authors: Liu Zhen , Towsley Don
Published: April 2006

In this paper we study the extremal properties of several scheduling policies in an in-forest network consisting of multiserver queues. Each customer has a due date, and we assume that service times at the different queues form mutually independent sequences of independent and identically distributed random variables independent of the arrival times and due dates. Furthermore, the network is assumed to consist of a mixture of nodes, some of which permit only non-preemptive service policies whereas the others permit preemptive resume policies. In the case of non-preemptive queues, service times may be generally distributed if there is only one server; otherwise the service times are required to be increasing in likelihood ratio (ILR). In the case of preemptive queues, service times are restricted to exponential distributions. Using stochastic majorizations and partial orders on permutations, we establish that, within the class of work conserving service policies, the stochastically smallest due date (SSDD) and the stochastically largest due date (SLDD) policies minimize and maximize, respectively, the vector of the customer latenesses of the firstncustomers in the sense of the Schur-convex order and some weaker orders, provided the due dates are comparable in some stochastic sense. It then follows that the first come-first served (FCFS) and the last come-first served (LCFS) policies minimize and maximize, respectively, the vector of the response times of the firstncustomers in the sense of the Schur-convex order. We also show that the FCFS and LCFS policies minimize and maximize, respectively, the vector of customer end-to-end delays in the sense of the strong stochastic order. Extensions to the class of non-idling policies and to the stationary regime are also given.
The multitype measure branching process
Authors: Gorostiza Luis G. , Lopez-Mimbela Jose A.
Published: April 2006

The existence of the multitype measure branching process is established as a small particle limit of a system of particles of several types in Rd with immigration undergoing migration, branching and mutation. The process is characterized as a solution of a martingale problem. The single-type case was studied by Dawson (1975), (1977) and Watanabe (1968).
An invariant distribution for the G/G/1 queueing operator
Authors: Bambos Nicholas , Walrand Jean
Published: April 2006

We consider the G/G/1 queue as an operator that maps inter-arrival times to inter-departure times of points, given the service times. For arbitrarily fixed statistics of service times, we are interested in the existence of distributions of inter-arrival times that induce identical distributions on the inter-departure times. In this note we prove, by construction, the existence of one of such distribution.
On the total loss probability of service stages in series
Authors: Courtois P.-J.
Published: April 2006

The problem addressed here is related to the minimization of the total loss probability in series of finite queues at which customers are rejected if the waiting capacity is exceeded. More precisely, one is concerned with the question of determining whether or not there may exist conditions under which an increase of the loss rate at one queue, e.g. at the most upstream one, could result in a decrease of the total loss rate throughout the whole network. The answer obtained in the context of a simple model is negative.
Fluctuation Theory for the Ehrenfest urn
Authors: Bingham N. H.
Published: April 2006

The Ehrenfest urn model withdballs, or alternatively random walk on the unit cube inddimensions, is considered in discrete and continuous time, together with related models. Attention is focused on the fluctuation theory of the model—behaviour on unusual states—and in particular on first passage to the opposite vertex. Applications to statistical mechanics, reliability theory and genetics are surveyed, and some new results are obtained.
Objects arranged randomly in space: an accessible theory
Authors: Cowan Richard
Published: April 2006

This expository paper deals with many problems concerning bounded objects arranged randomly in space. The objects are of rather general shapes and sizes, whilst the random mechanisms for positioning and orienting them are also fairly general. There are no restrictions on the dependence between shapes, sizes, orientations and positions of objects. The only substantive assumption is that the objects are distributed in a ‘statistically uniform' way throughout the whole of the space. We focus on the statistical properties of features seen in an observation window, itself of general size and shape.
Simple proof for goofspiel: the game of pure strategy
Authors: Dror Moshe
Published: April 2006

A simple proof is given for the best strategy when the game of pure strategy is played.
Insensitivity and product-form decomposability of reallocatable GSMP
Authors: Miyazawa Masakiyo
Published: April 2006

A stochastic process, called reallocatable GSMP (RGSMP for short), is introduced in order to study insensitivity of its stationary distribution. RGSMP extends GSMP with interruptions, and is applicable to a wide range of queues, from the standard models such as BCMP and Kelly's network queues to new ones such as their modifications with interruptions and Serfozo's (1989) non-product form network queues, and can be used to study their insensitivity in a unified way. We prove that RGSMP supplemented by the remaining lifetimes is product-form decomposable, i.e. its stationary distribution splits into independent components if and only if a version of the local balance equations hold, which implies insensitivity of the RGSMP scheme in a certain extended sense. Various examples of insensitive queues are given, which include new results. Our proofs are based on the characterization of a stationary distribution for SCJP (self-clocking jump process) of Miyazawa (1991).
Double stopping by two decision-makers
Authors: Szajowski K.
Published: April 2006

A problem of optimal stopping of the discrete-time Markov process by two decision-makers (Player 1 and Player 2) in a competitive situation is considered. The zero-sum game structure is adopted. The gain function depends on states chosen by both decision-makers. When both players want to accept the realization of the Markov process at the same moment, the priority is given to Player 1. The construction of the value function and the optimal strategies for the players are given. The Markov chain case is considered in detail. An example related to the generalized secretary problem is solved.
Fluctuation theory for the Ehrenfest urn via electric networks
Authors: Palacios José Luis
Published: April 2006

Using the electric network approach, we give very simple derivations for the expected first passage from the origin to the opposite vertex in thed-cube (i.e. the Ehrenfest urn model) and the Platonic graphs.
A multilevel branching model
Authors: Dawson D. A. , Hochberg K. J.
Published: April 2006

We consider a dynamic multilevel population or information system. At each level individuals or information units undergo a Galton–Watson-type branching process in which they can be replicated or removed. In addition, a collection of individuals or information units at a given level constitutes an information unit at the next higher level. Each collection of units also undergoes a Galton–Watson branching process, either dying or replicating. In this paper, we represent this multilevel branching model as a measure-valued stochastic process, study its moment structure, identify the limiting continuous-state approximation and analyse the long-time behavior in both non-critical and critical cases. For example, we obtain an asymptotic expression for the extinction probability for the total population mass process and an analogue of Yaglom's conditioned limit theorem in the critical case.
Large-deviation approximations to the distribution of scan statistics
Authors: Loader Clive R.
Published: April 2006

Suppose a Poisson process is observed on the unit interval. The scan statistic is defined as the maximum number of events observed as a window of fixed width is moved across the interval, and the distribution under homogeneity has been widely studied. Frequently, we may not wish to specify the window width in advance but to consider scan statistics with varying window widths. We propose a modification of the scan statistic based on a likelihood ratio criterion. This leads to a boundary-crossing problem for a two-dimensional random field, which we approximate using a large-deviation scaling under homogeneity. Similar results are obtained for Poisson processes observed in two dimensions. Numerical computations and simulations are used to illustrate the accuracy of the approximations.
A stochastic model of an artificial neuron
Authors: Whittle P.
Published: April 2006

A simple model of a neuron is proposed, not intended to be biologically faithful, but to incorporate dynamic and stochastic features which seem to be realistic for both the natural and the artificial case. It is shown that the use of feedback for assemblies of such neurons can produce bistable behaviour and sharpen the discrimination of the assembly to the level of input. Particular attention is paid to bistable devices which are to serve as bit-stores (and so constitute components of a memory) and which suffer a disturbing input due to mutual interference. Approximate expressions are obtained for the equilibrium distribution of the excitation level for such assemblies and for the expected escape time of such an assembly from a metastable excitation level.
Some remarks on nevzorov's record model
Authors: Pfeifer Dietmar
Published: April 2006

We give a simple proof for the independence of record indices in Nevzorov's record model which is based on ranks. An application of these results to a probabilistic analysis of a particular searching algorithm with non-equiprobable orderings is also discussed.
On a random interval graph and the maximum throughput rate in the system GI/G/1/0
Authors: Nawijn Wim M.
Published: April 2006

The paper gives an explicit expression for the expectation of the maximum attainable fraction of served customers in the long run for the single-server loss system GI/G/1/0, under the assumption of perfect information regarding the sequences {Xi, i = 1, 2, ·· ·} and {Yi, i = 1, 2, ·· ·} of interarrival times and service times, respectively. A heavy traffic result for this fraction is obtained for the system GI/M/1/0. The general result is based on an analysis of the random interval graph corresponding to the random intervals {[Ti, Ti + Yi), i = 1, 2, ·· ·}, in which {Ti} denotes the sequence of arrival epochs.
On ergodicity and recurrence properties of a Markov chain by an application to an open jackson network
Authors: Hordijk Arie , Spieksma Flora
Published: April 2006

This paper gives an overview of recurrence and ergodicity properties of a Markov chain. Two new notions for ergodicity and recurrence are introduced. They are called μ -geometric ergodicity and μ -geometric recurrence respectively. The first condition generalises geometric as well as strong ergodicity. Our key theorem shows that μ -geometric ergodicity is equivalent to weak μ -geometric recurrence. The latter condition is verified for the time-discretised two-centre open Jackson network. Hence, the corresponding two-dimensional Markov chain is μ -geometrically and geometrically ergodic, but not strongly ergodic. A consequence of μ -geometric ergodicity with μ of product-form is the convergence of the Laplace-Stieltjes transforms of the marginal distributions. Consequently all moments converge.
Diffusion approximations for some simple chemical reaction schemes
Authors: Pollett P. K. , Vassallo A.
Published: April 2006

We shall establish functional limit laws for the concentration of the various species in simple chemical reactions. These results allow us to conclude that, under quite general conditions, the concentration has an approximate normal distribution. We provide estimates for the mean and the variance which are valid at all stages of the reaction, in particular, the non-equilibrium phase. We also provide a detailed comparison of our results with the earlier work of Dunstan and Reynolds ([7], [8]).
The Smoluchowski–Kramers approximation for the stochastic Liénard equation by mean-field
Authors: Narita Kiyomasa
Published: April 2006

The oscillator of the Liénard type with mean-field containing a large parameter α < 0 is considered. The solution of the two-dimensional stochastic differential equation with mean-field of the McKean type is taken as the response of the oscillator. By a rigorous evaluation of the upper bound of the displacement process depending on the parameter α, a one-dimensional limit diffusion process as α → ∞is derived and identified. Then our result extends the Smoluchowski–Kramers approximation for the Langevin equation without mean-field to the McKean equation with mean-field.
The number of critical connection vectors of L-superadditive structure functions
Authors: El-Neweihi Emad , Meng Fan C.
Published: April 2006

A conjecture due to Block et al. (1989), concerning the number of critical connection vectors to the various performance levels of a discrete L-superadditive structure function, is proved. When the components of the discrete L-superadditive structure function are further assumed to satisfy a certain relevance condition due to Griffith (1980), it is shown that there is exactly one critical connection vector to each performance level.
Limiting behaviour of two-level measure-branching
Authors: Etheridge Alison M.
Published: April 2006

A measure-valued diffusion approximation to a two-level branching structure was introduced in Dawson and Hochberg (1991) where it was shown that conditioned on non-extinction at time t, and appropriately rescaled, the process converges as t → ∞to a non-trivial limiting distribution. Here we discuss a different approach to conditioning on non-extinction (popular in one-level branching) and relate the two limiting distributions.
Stochastic and dynamic vehicle routing with general demand and interarrival time distributions
Authors: Bertsimas Dimitris J. , Van Ryzin Garrett
Published: April 2006

We analyze a class of stochastic and dynamic vehicle routing problems in which demands arrive randomly over time and the objective is minimizing waiting time. In our previous work ([6], [7]), we analyzed this problem for the case of uniformly distributed demand locations and Poisson arrivals. In this paper, using quite different techniques, we are able to extend our results to the more realistic case where demand locations have an arbitrary continuous distribution and arrivals follow only a general renewal process. Further, we improve significantly the best known lower bounds for this class of problems and construct policies that are provably within a small constant factor relative to the optimal solution. We show that the leading behavior of the optimal system time has a particularly simple form that offers important structural insight into the behavior of the system. Moreover, by distinguishing two classes of policies our analysis shows an interesting dependence of the system performance on the demand distribution.
Mean-Value Formulae for the Neighbourhood of the Typical Cell of a Random Tessellation
Authors: Chiu S. N.
Published: April 2006

The mean number of edges of a randomly chosen neighbouring cell of the typical cell in a planar stationary tessellation, under the condition that it hasnedges, has been studied by physicists for more than 20 years. Experiments and simulation studies led empirically to the so-calledAboav's law.This law now plays a central role in Rivier's (1993) maximum entropy theory of statistical crystallography. Using Mecke's (1980) Palm method, an exact form of Aboav's law is derived. Results in higher-dimensional cases are also discussed.
Strong Convergence of Stochastic Epidemics
Authors: Ball Frank , O'Neill Philip
Published: April 2006

This paper is concerned with a model for the spread of an epidemic in a closed, homogeneously mixing population in which new infections occur at ratef(x,y) and removals occur at rateg(x,y), wherexand y are the numbers of susceptible and infective individuals, respectively, andfandgare arbitrary but specified positive real-valued functions. Sequences of such epidemics, indexed by the initial number of susceptiblesn,are considered and conditions are derived under which the epidemic processes converge almost surely to a birth and death process asntends to infinity. Thus a threshold theorem for such an epidemic model is obtained. The results are extended to models which incorporate immigration and emigration of susceptibles. The theory is illustrated by several examples of models taken from the epidemic literature. Generalizations to multipopulation epidemics are discussed briefly.
Perturbation analysis of functionals of random measures
Authors: Baccelli François , Klein Maurice , Zuyev Sergei
Published: April 2006

We use the fact that the Palm measure of a stationary random measure is invariant to phase space change to generalize the light traffic formula initially obtained for stationary processes on a line to general spaces. This formula gives a first-order expansion for the expectation of a functional of the random measure when its intensity vanishes. This generalization leads to new algorithms for estimating gradients of functionals of geometrical random processes.
On second-order formulas in anisotropic stereology
Authors: Beneš Viktor
Published: April 2006

Formulas for anisotropic stereology of fibre and surface processes are presented. They concern the relation between second-order quantities of the original process and its projections and sections. Various mathematical tools for handling these formulas are presented, including stochastic optimization. Finally applications in stereology are discussed, relating to intensity estimators using anisotropic sampling designs. Variances of these estimators are expressed and evaluated for processes with the Poisson property.
Stationary states of a directed planar growth process
Authors: Gates D. J.
Published: April 2006

A new Markov process is introduced, describing growth or spread in two dimensions, via the aggregation of particles or the filling of cells. States of the process are configurations of part of the boundary of the growing aggregate, and transitions are captures or escapes of single particles. For suitably chosen transition rates, the process is dynamically reversible, leading to an explicit stationary distribution and a statistical description of the boundary. The growth rate is calculated and growth behaviour described. Different asymptotic relations between transition rates lead to different growth patterns or regimes. Besides the regimes familiar in polymer crystal growth, several new ones are described. The aggregate can have a porous structure resembling thin solid films deposited from vapour. Two measures of porosity, one for the boundary and one for the bulk, are calculated. The process is relevant to growing colonies of bacteria or the like, to the spread of epidemics and grass or forest fires, and to voter models.
Approximations of general discrete time queues by discrete time queues with arrivals modulated by finite chains
Authors: Sharma Vinod
Published: April 2006

Recently, Asmussen and Koole (Journal of Applied Probability30, pp. 365–372) showed that any discrete or continuous time marked point process can be approximated by a sequence of arrival streams modulated by finite state continuous time Markov chains. If the original process is customer (time) stationary then so are the approximating processes. Also, the moments in the stationary case converge. For discrete marked point processes we construct a sequence ofdiscreteprocesses modulated by discrete time finite state Markov chains. All the above features of approximating sequences of Asmussen and Koole continue to hold. For discrete arrival sequences (to a queue) which are modulated by a countable state Markov chain we form a different sequence of approximating arrival streams by which, unlike in the Asmussen and Koole case, even the stationary moments of waiting times can be approximated. Explicit constructions for the output process of a queue and the total input process of a discrete time Jackson network with these characteristics are obtained.
Brownian Excursions and Parisian Barrier Options
Authors: Chesney Marc , Jeanblanc-Picqué Monique , Yor Marc
Published: April 2006

In this paper we study a new kind of option, called hereinafter a Parisian barrier option. This option is the following variant of the so-called barrier option: a down-and-out barrier option becomes worthless as soon as a barrier is reached, whereas a down-and-out Parisian barrier option is lost by the owner if the underlying asset reaches a prespecified level and remains constantly below this level for a time interval longer than a fixed number, called the window. Properties of durations of Brownian excursions play an essential role. We also study another kind of option, called here a cumulative Parisian option, which becomes worthless if the total time spent below a certain level is too long.
Limiting Conditional Distributions for Birthdeath Processes
Authors: Kijima M. , Nair M. G. , Pollett P. K. , Van Doorn E. A.
Published: April 2006

In a recent paper [16], one of us identified all of the quasi-stationary distributions for a non-explosive, evanescent birth-death process for which absorption is certain, and established conditions for the existence of the corresponding limiting conditional distributions. Our purpose is to extend these results in a number of directions. We shall consider separately two cases depending on whether or not the process is evanescent. In the former case we shall relax the condition that absorption is certain. Furthermore, we shall allow for the possibility that the minimal process might be explosive, so that the transition rates alone will not necessarily determine the birth-death process uniquely. Although we shall be concerned mainly with the minimal process, our most general results hold for any birth-death process whose transition probabilities satisfy both the backward and the forward Kolmogorov differential equations.