bluuebunny/crossref_metadata_2025 huggingface dataset:
Self-organizing files with dependent accesses
Authors: Lam Kin , Leung Ming-Ying , Siu Man-Keung
Published: April 2006

We analyze certain self-organizing filing techniques when accesses are assumed to be dependent on each other. The stream of requests for accessing records in a file is modelled as a Markov chain. A general framework is introduced to obtain the asymptotic search cost of a memory-free self-organizing heuristic. The move-to-front heuristic is studied in detail. A formula for the asymptotic search cost, which generalizes that in the case of independent accesses, is obtained. Numerical examples on the performance of the transposition heuristic are provided, and compared with that of the move-to-front heuristic.
Probability maximizing approach to a secretary problem by random change-point of the distribution law of the observed process
Authors: Yoshida Minoru
Published: April 2006

Before some random moment θ, independent identically distributed random variables x1, · ··, xθ–1 with common distribution function μ (dx) appear consecutively. After the moment θ, independent random variables xθ, xθ+1, · ·· have another common distribution function f (x)μ (dx). Our information about θ can be constructed only by successively observed values of the x's.

In this paper we find an optimal stopping policy by which we can maximize the probability that the quantity associated with the stopping time is the largest of all θ + m – 1 quantities for a given integer m.
Recurrence processes
Authors: McCullagh Peter
Published: April 2006

A recurrence process is the process of forward recurrence times from the points of one renewal process to the next subsequent event in a second independent renewal process. Univariate and multivariate recurrence processes are examined. Exponential recurrence processes are investigated in greater detail.
On a random mapping (T, Pj)
Authors: Jaworski Jerzy
Published: April 2006

A random mapping (T,Pj) of a finite set V into itself is studied. We give a new proof of the fundamental lemma of [6]. Our method leads to the derivation of several results which cannot be deduced from [6]. In particular we determine the distribution of the number of components, cyclical points and ancestors of a given point.
Insensitivity of blocking probabilities in a circuit-switching network
Authors: Burman D. Y. , Lehoczky J. P. , Lim Y.
Published: April 2006

Consider a network of nodes (switches) and connecting links. Each link consists of a group of channels (trunks). A call instantaneously seizes channels along a route between the originating and terminating node, holds them for a randomly distributed length of time and frees them instantaneously at the end of the call. If no channels are available, the call is blocked. For special networks with exponential call holding times, Erlang has shown that the steady-state probabilities are in product form. In this paper, we extend this work to general networks and show that if for each pair of nodes there is a unique route, then the blocking probabilities are in product form and are insensitive to the call holding-time distribution, which means that they depend on the call duration only through its mean.
The first-passage density of a continuous gaussian process to a general boundary
Authors: Durbin J.
Published: April 2006

Under mild conditions an explicit expression is obtained for the first-passage density of sample paths of a continuous Gaussian process to a general boundary. Since this expression will usually be hard to compute, an approximation is given which is computationally simple and which is exact in the limit as the boundary becomes increasingly remote. The integral of this approximating density is itself approximated by a simple formula and this also is exact in the limit. A new integral equation is derived for the first-passage density of a continuous Gaussian Markov process. This is used to obtain further approximations.
Renewal theory for several patterns
Authors: Breen Stephen , Waterman Michael S. , Zhang Ning
Published: April 2006

Discrete renewal theory is generalized to study the occurrence of a collection of patterns in random sequences, where a renewal is defined to be the occurrence of one of the patterns in the collection which does not overlap an earlier renewal. The action of restriction enzymes on DNA sequences provided motivation for this work. Related results of Guibas and Odlyzko are discussed.
A characterization of order statistic point processes that are mixed Poisson processes and mixed sample processes simultaneously
Authors: Deffner A. , Haeusler E.
Published: April 2006

The results of Nawrotzki (1962), Feigin (1979) and Puri (1982) show that the class of all point processes (on the real line) with the order statistic property consists of all mixed Poisson processes up to a time-scale transformation, and of all mixed sample processes. The present note characterizes those order statistic point processes that are mixed Poisson processes and mixed sample processes simultaneously.
A note on stochastic decomposition in a GI/G/1 queue with vacations or set-up times
Authors: Doshi Bharat T.
Published: April 2006

In this note we prove some stochastic decomposition results for variations of the GI/G/1 queue. Our main model is a GI/G/1 queue in which the server, when it becomes idle, goes on a vacation for a random length of time. On return from vacation, if it finds customers waiting, then it starts serving the first customer in the queue. Otherwise it takes another vacation and so on. Under fairly general conditions the waiting time of an arbitrary customer, in steady state, is distributed as the sum of two independent random variables: one corresponding to the waiting time without vacations and the other to the stationary forward recurrence time of the vacation. This extends the decomposition result of Gelenbe and Iasnogorodski [5]. We use sample path arguments, which are also used to prove stochastic decomposition in a GI/G/1 queue with set-up time.
Sequential random displacements of points in an interval
Authors: Mannion David
Published: April 2006

An array of points {Z1, Z2, …, Zn–1} in the interval V = [0, L], is such that 0 ≦ Z1, ≦ Z2 ≦ … ≦ Zn–1, ≦ L. One of the points is chosen at random (Zk, say, with probability pk) and displaced to a new position within the interval [Zk–1, Zk+ 1], the position again chosen at random according to a probability distribution Gk. We derive some results concerning the limiting distribution of the array after a succession of such displacements. If Gk is a uniform distribution, it appears that the number of displacements necessary to open up a gap between at least one pair of adjacent points of size at least γ is O(ρ n), n →∞, where ρ = L/(L – γ).
Coefficients of ergodicity with respect to vector norms
Authors: Tan Choon-Peng
Published: April 2006

The stationary distribution may be used to estimate the rate of geometric convergence to ergodicity for a finite homogeneous ergodic Markov chain. This is done by invoking the spectrum localization property of a new class of ergodicity coefficients defined with respect to column vector norms for the transition matrix P. Explicit functional forms in terms of the entries of P are obtained for these coefficients with respect to the l∞ and l1, norms, and comparison in performance with various known coefficients is made with the aid of numerical examples.
On the asymptotic distribution of the size of a stochastic epidemic
Authors: Sellke Thomas
Published: April 2006

For a stochastic epidemic of the type considered by Bailey [1] and Kendall [3], Daniels [2] showed that ‘when the threshold is large but the population size is much larger, the distribution of the number remaining uninfected in a large epidemic has approximately the Poisson form.' A simple, intuitive proof is given for this result without use of Daniels's assumption that the original number of infectives is ‘small'. The proof is based on a construction of the epidemic process which is more explicit than the usual description.
Exact distributions of kin numbers in a Galton-Watson process
Authors: Joffe A. , Waugh W. A. O'n.
Published: April 2006

The kin number problem involves the relationship between sibship sizes and offspring numbers, and also numbers of relatives of other degrees of affinity of a random member of a population, to be called Ego. The problem has been well known to demographers for some time, but results obtained only gave expected numbers. Recently a study of it, based on the Galton-Watson process, was made, with a view to obtaining joint distributions (Waugh (1981)). In the latter study it was assumed that the population was large, and thus some of the results obtained were approximations.

In the present paper exact distributions are obtained, for any size of population. This can be of use in applications, where the population considered may be a small, isolated tribe or other special group. As a theoretical investigation, it replaces some heuristic arguments with limiting properties that are intrinsic to the process and it makes it possible to evaluate the previous approximations.
A note on the background of several Bonferroni–Galambos-type inequalities
Authors: Móri Tamás F. , Székely Gábor J.
Published: April 2006

LetA1,A2, · ··,Anbe events on a probability space. Denote bySkthekth binomial moment of the number Mnof thoseA's which occur. Sharp lower and upper bounds ofSmwill be given in terms ofSkandSl.The same method can be applied for proving Bonferroni–Galambos-type inequalities.
Calculation of the equilibrium distribution for a solar energy storage model
Authors: Hooghiemstra G. , Keane M.
Published: April 2006

The study of simple solar energy storage models leads to the question of analyzing the equilibrium distribution of Markov chains (Harris chains), for which the state at epoch (n + 1) (i.e. the temperature of the storage tank) depends on the state at epoch n and on a controlled input, acceptance of which entails a further decrease of the temperature level. Here we study the model where the input is exponentially distributed. For all values of the parameters involved an explicit expression for the equilibrium distribution of the Markov chain is derived, and from this we calculate, as one of the possible applications, the exact values of the mean of this equilibrium distribution.
On the general bilinear time series model
Authors: Liu Jian , Brockwell Peter J.
Published: April 2006

A sufficient condition is derived for the existence of a strictly stationary solution of the general bilinear time series equations. The condition is shown to reduce to the conditions of Pham and Tran (1981) and Bhaskara Rao et al. (1983) in the special cases which they consider. Under the condition specified, a solution is constructed which is shown to be causal, stationary and ergodic. It is moreover the unique causal solution and the unique stationary solution of the defining equations. In the special case when the defining equations contain no non-linear terms, our condition reduces to the well-known necessary and sufficient condition for existence of a causal stationary solution.
On berry–esseen rate for queue length of the GI/G/K system in heavy traffic
Authors: Jin Xing
Published: April 2006

This paper provides Berry–Esseen rate of limit theorem concerning the number of customers in a GI/G/K queueing system observed at arrival epochs for traffic intensity ρ > 1. The main method employed involves establishing several equalities about waiting time and queue length.
Extinction times for certain predator–prey processes
Authors: Ridler-Rowe C. J.
Published: April 2006

Finiteness of mean extinction times for certain predator-prey models has been established by Hitchcock (1986) with the aid of a criterion of Reuter (1957). Using this criterion and a ‘minimisation' lemma this note shows that the mean extinction times tend to zero as the combined initial population of predators and prey becomes large.
An application of the system-point method to inventory models under continuous review
Authors: Azoury K. , Brill P. H.
Published: April 2006

This paper derives the stationary probability distribution of inventory level for continuous-review models, by means of the system-point method of level-crossing analysis. We analyze inventory problems with decaying products under (nQ, r) and (s, S) ordering policies and zero lead-time, and derive the relevant cost functions. Our results have implications for the case of positive lead-time and to a non-decaying inventory problem with two types of demand processes.
Bonferroni bounds revisited
Authors: Kounias Stratis , Sotirakoglou Kiki
Published: April 2006

Lower and upper bounds of degree m for the probability of the union of n not necessarily exchangeable events are established. These bounds may be constructed to improve the Bonferroni and the Sobel–Uppuluri bounds.

An application to equi-correlated multivariate normal distribution is given.
An LCFS finite buffer model with finite source batch input
Authors: Van Dijk Nico M.
Published: April 2006

Queueing systems are studied with a last-come, first-served queueing discipline and batch arrivals generated by a finite number of non-exponential sources. A closed-form expression is derived for the steady-state queue length distribution. This expression has a scaled geometric form and is insensitive to the input distribution. Moreover, an algorithm for the recursive computation of the normalizing constant and the busy source distribution is presented. The results are of both practical and theoretical interest as an extension of the standard Poisson batch input case.
On estimating the diffusion coefficient
Authors: Dohnal Gejza
Published: April 2006

Random processes of the diffusion type have the property that microscopic fluctuations of the trajectory make possible the identification of certain statistical parameters from one continuous observation. The paper deals with the construction of parameter estimates when observations are made at discrete but very dense time points.
On the maximum of random fields represented by stochastic integrals over circles
Authors: Orsingher Enzo
Published: April 2006

In this paper we obtain an upper bound for the maximum of random fields of the form , where CP denotes circles of fixed radius and dW(P′) is a plane white noise field.

The results presented are obtained by means of successive steps involving Slepian's lemma for random fields, inequalities on Brownian fields and planar stochastic integrals.
Reliability importance for continuum structure functions
Authors: Kim Chul , Baxter Laurence A.
Published: April 2006

A continuum structure function is a non-decreasing mapping from the unit hypercube to the unit interval. A definition of the reliability importance, ℛi(α) say, of component i at system level α(0 < α ≦ 1) is proposed. Some properties of this function are deduced, in particular conditions under which and conditions under which ℛi(α) is positive (0 < α < 1).
A useful generalization of renewal theory: counting processes governed by non-negative Markovian increments
Authors: Kijima Masaaki , Sumita Ushio
Published: April 2006

Let N(t) be a counting process associated with a sequence of non-negative random variables (Xj)1∞ where the distribution of Xn+1 depends only on the value of the partial sum Sn = Σj=1nXj. In this paper, we study the structure of the function H(t) = E[N(t)], extending the ordinary renewal theory. It is shown under certain conditions that h(t) = (d/dt)H(t) exists and is a unique solution of an extended renewal equation. Furthermore, sufficient conditions are given under which h(t) is constant, monotone decreasing and monotone increasing. Asymptotic behavior of h(t) and H(t) as t → ∞ is also discussed. Several examples are given to illustrate the theoretical results and to demonstrate potential use of the study in applications.
Computer experimentation in applied probability
Authors: Neuts Marcel F.
Published: April 2006

This is a discussion of the place of empirical methods in the study of probability models. It is argued that, for models of great complexity, careful experimentation may be a legitimate source of factual information on the behavior of such models. The need for rigorous standards of empirical methodology and of appropriate reporting is stressed. A simple, but interesting question on the distribution of the maximal eigenvalue of positive matrices with random elements is used as an example of an experimental study. In the course of the discussion of that example, several operational rules of sound computer experimentation are stated.
Hot metal to hard disc
Authors: Lyle Kathleen M.
Published: April 2006

The effects of computer technology on various aspects of mathematical printing are discussed. A brief account is given of the use of a microcomputer and commercial software in a publishing office environment.
Approximations for the GI/G/c queue
Authors: Van Hoorn M. H. , Seelen L. P.
Published: April 2006

In this paper, we give good-quality approximations for multiserver queues with general service-time distributions. For the interarrival-time distribution we consider hyperexponential distributions and mixtures of Erlang distributions with the same scale parameters. We give an algorithm to compute various operating characteristics such as the delay probability and the mean queue length.

The approximations are obtained by making assumptions regarding the residual service times of services in progress at service completion epochs, whereas the arrival process is modelled exactly. As the operating characteristics are far more sensitive to changes in the parameters of the arrival process, the latter is very important.

The quality of the approximations is extensively tested by using the exact results of more than 2000 cases. In heavy traffic the average relative error is up to 1% and in moderate traffic about 4%.
Subcritical branching processes in a two-state random environment, and a percolation problem on trees
Authors: Dekking F. M.
Published: April 2006

We determine the decay rate of the survival probability of subcritical branching processes in a two-state random environment, where one state is subcritical, the other supercritical. This result is applied to obtain the asymptotic behavior (as n →∞) of the number of different words of length n occurring on the binary, and generally the b-ary, tree with Bernoulli percolation.
An upper bound on the performance of queues with returning customers
Authors: Greenberg Betsy S. , Wolff Ronald W.
Published: April 2006

Multiple channel queues with Poisson arrivals, exponential service distributions, and finite capacity are studied. A customer who finds the system at capacity either leaves the system for ever or may return to try again after an exponentially distributed time. Steady state probabilities are approximated by assuming that the returning customers see time averages. The approximation is shown to result in an upper bound on system performance.
A drug addiction model
Authors: Billard L. , Dayananda P. W. A.
Published: April 2006

A drug addiction process in which individuals in a closed population can become addicts or pushers is modelled. Expressions for the state probabilities and factorial moments are obtained. A generalized model is also developed. This generalized drug addiction process can be viewed as a particular case of what may be called a competing death process.
Multitype branching processes based on exact progeny lengths of particles in a Galton-Watson branching process
Authors: Gadag V. G. , Rajarshi M. B.
Published: April 2006

In Gadag and Rajarshi (1987), we studied a bivariate (multitype) branching process based on infinite and finite lines of descent, of particles of a supercritical one-dimensional (multitype) Galton-Watson branching process (GWBP). In this paper, we discuss a few more meaningful and interesting univariate and multitype branching processes, based on exact progeny lengths of particles in a GWBP. Our constructions relax the assumption of supercriticality made in Gadag and Rajarshi (1987). We investigate some finite-time and asymptotic results of these processes in some details and relate them to the original process. These results are then used to propose new and better estimates of the offspring mean. An illustration based on the branching process of the white male population of the USA is also given. We believe that our work offers a rather finer understanding of the branching property.
Slepian models for X2-processes with dependent components with application to envelope upcrossings
Authors: Lindgren Georg
Published: April 2006

A Slepian model for the local behaviour near the level upcrossings of a x2-process with dependent Gaussian components is presented. In case of independent components, this model is shown to take on a rather simple form, thereby simplifying earlier results by Aronowich and Adler.

The Slepian model is applied to the envelope of a stationary Gaussian process and used to approximate the probability of ‘empty' envelope upcrossings, i.e. the probability that an envelope upcrossing is not followed by a level crossing in the original process.
Commande optimale du processus de wiener
Authors: Lefebvre Mario
Published: April 2006

The problem of the optimal control of the Wiener process in Rn is considered. The optimal value of the control is obtained from the mathematical expectation of a quantity defined in terms of the moment and the place where the uncontrolled process hits the boundary of the continuation region for the first time. Explicit results are presented.
A certain configuration of random points on a circle associated with a generalized Lotka-Volterra equation
Authors: Itoh Yoshiaki
Published: April 2006

Invariant integrals of a Lotka-Volterra system with infinitely many species are introduced. The values of these integrals are given by the probabilities of certain configurations of random points on a circle when the probability density on the circle satisfies a certain symmetry condition.
Quasi-ergodicity for non-homogeneous continuous-time Markov chains
Authors: Zeifman A. I.
Published: April 2006

We consider a non-homogeneous continuous-time Markov chain X(t) with countable state space. Definitions of uniform and strong quasi-ergodicity are introduced. The forward Kolmogorov system for X(t) is considered as a differential equation in the space of sequences l1. Sufficient conditions for uniform quasi-ergodicity are deduced from this equation. We consider conditions of uniform and strong ergodicity in the case of proportional intensities.
Stereological analysis of particles of varying ellipsoidal shape
Authors: Møller J.
Published: April 2006

Stereological analysis of d-dimensional particles of ellipsoidal shape based on lower-dimensional sections through the particles is discussed. It is proved that the non-void intersections between three parallel hyperplanes and an ellipsoid uniquely determine the ellipsoid, and based on this fact we may reconstruct ellipsoids from sectional information. Combining this reconstruction with a new sampling procedure we obtain a useful tool for non-parametric stereological analysis of particle aggregates of ellipsoids. Finally, parametric models for ellipsoids which are mathematically convenient for the present set up are introduced and discussed.
Concepts of dispersion in distributions: a comparative note
Authors: Hickey Raymond J.
Published: April 2006

The Lewis-Thompson (L-T) approach to ordering distributions in terms of dispersion is compared to the dispersion ordering obtained from majorisation. For given conditions, L-T ordering is shown to be stronger than majorisation ordering. Dilation is considered in relation to majorisation ordering.
Two sufficient properties for the insensitivity of a class of queueing models
Authors: Haviv Moshe
Published: April 2006

For indivisible strong work-conserving queueing models with a Poisson arrival process, each of the following two properties is a sufficient condition for insensitivity. (1) The completed workload of a job receiving service is independent of the number of jobs in the system. (2) Independently of the completed workloads of the jobs in the system, they all are equally likely to be in service. For models which additionally belong to the class described by two families of parameters each of these properties is also necessary for insensitivity.
On estimating the diffusion coefficient from discrete observations
Authors: Florens-Zmirou Danielle
Published: April 2006

This paper is concerned with the problem of estimation for the diffusion coefficient of a diffusion process on R, in a non-parametric situation. The drift function can be unknown and considered as a nuisance parameter. We propose an estimator of σ based on discrete observation of the diffusion X throughout a given finite time interval. We describe the asymptotic behaviour of this estimator when the step of discretization tends to zero. We prove consistency and asymptotic normality, the rate of convergence to the normal law being a random variable linked to the local time of the diffusion or to its suitable discrete approximation. This can also be interpreted as a convergence to a mixture of normal law.
On an index policy for restless bandits
Authors: Weber Richard R. , Weiss Gideon
Published: April 2006

We investigate the optimal allocation of effort to a collection of n projects. The projects are ‘restless' in that the state of a project evolves in time, whether or not it is allocated effort. The evolution of the state of each project follows a Markov rule, but transitions and rewards depend on whether or not the project receives effort. The objective is to maximize the expected time-average reward under a constraint that exactly m of the n projects receive effort at any one time. We show that as m and n tend to ∞ with m/n fixed, the per-project reward of the optimal policy is asymptotically the same as that achieved by a policy which operates under the relaxed constraint that an average of m projects be active. The relaxed constraint was considered by Whittle (1988) who described how to use a Lagrangian multiplier approach to assign indices to the projects. He conjectured that the policy of allocating effort to the m projects of greatest index is asymptotically optimal as m and n tend to∞. We show that the conjecture is true if the differential equation describing the fluid approximation to the index policy has a globally stable equilibrium point. This need not be the case, and we present an example for which the index policy is not asymptotically optimal. However, numerical work suggests that such counterexamples are extremely rare and that the size of the suboptimality which one might expect is minuscule.
Ornstein–Uhlenbeck process with quadratic killing
Authors: Wenocur Michael L.
Published: April 2006

An Ornstein-Uhlenbeck process subject to a quadratic killing rate is analyzed. The distribution for the process killing time is derived, generalizing the analogous result for Brownian motion. The derivation involves the use of Hermite polynomials in a spectral expansion.
On the recurrence of simple random walks on some fractals
Authors: Xian-Yin Zhou
Published: April 2006

In this paper, the recurrence or transience of simple random walks on some lattice fractals is investigated. As results, we obtain that the simple random walk on the pre-Sierpinski gasket inddimensions is recurrent for alld≧ 2, and on the pre-Sierpinski carpet inddimensions it is recurrent ford= 2 and transient for alld≧ 3.
The distribution and moments of the number of components of a random function
Authors: Kupka Joseph
Published: April 2006

A relatively simple formula is presented for the probability distribution of the number K of components of a random function. This formula facilitates the (computer) calculation of the factorial moments of K and yields new expressions for the mean and variance of K.
Distances between censored intersections between a square lattice and a random smooth path
Authors: Wheelwright A. V. , Glasbey C. A.
Published: April 2006

A random smooth path of infinite length crossed a square lattice. Intersections with the lattice were censored if they lay within a threshold distance of a preceding uncensored intersection, defined by tracking along the path in one direction. The distribution of distances between consecutive uncensored intersections is derived.
Percolation of coalescing random walks
Authors: Nguyen Bao Gia
Published: April 2006

We study the shape of the binary tree containing 0 that is created from percolation of coalescing random walks. The key result is a duality lemma describing the shape of the tree. Furthermore, we show thatandwhereA(R0),M(R0),L(R0) are respectively the area, the number of external nodes and the length of the longest path of the treeR0.
Construction of first-passage-time densities for a diffusion process which is not necessarily time-homogeneous
Authors: Jáimez R. Gutiérrez , Gonzalez A. Juan , Román P. Román
Published: April 2006

In Giorno et al. (1988) a new method for constructing first-passage-time probability density functions is outlined. This rests on the possibility of constructing the transition p.d.f. of a new time-homogeneous diffusion process in terms of a preassigned transition p.d.f. without making use of the classical space-time transformations of the Kolmogorov equation (Ricciardi (1976)).

In the present paper we give an extension of this result to the case of a diffusion process X(t) which is not necessarily time-homogeneous, and a few examples are presented.
Convergence theorems for a class of simulated annealing algorithms on ℝd
Authors: Bélisle Claude J. P.
Published: April 2006

We study a class of simulated annealing algorithms for global minimization of a continuous function defined on a subset ofWe consider the case where the selection Markov kernel is absolutely continuous and has a density which is uniformly bounded away from 0. This class includes certain simulated annealing algorithms recently introduced by various authors. We show that, under mild conditions, the sequence of states generated by these algorithms converges in probability to the global minimum of the function. Unlike most previous studies where the cooling schedule is deterministic, our cooling schedule is allowed to be adaptive. We also address the issue of almost sure convergence versus convergence in probability.
Uniformly distributed first-order autoregressive time series models and multiplicative congruential random number generators
Authors: Lawrance A. J.
Published: April 2006

The work is concerned with the first-order linear autoregressive process which has a rectangular stationary marginal distribution. A derivation is given of the result that the time-reversed version is deterministic, with a first-order recursion function of the type used in multiplicative congruential random number generators, scaled to the unit interval. The uniformly distributed sequence generated is chaotic, giving an instance of a chaotic process which when reversed has a linear causal and non-chaotic structure. An mk-valued discrete process is then introduced which resembles a first-order linear autoregressive model and uses k-adic arithmetic. It is a particular form of moving-average process, and when reversed approximates in m a non-linear discrete-valued process which has the congruential generator function as its deterministic part, plus a discrete-valued noise component. The process is illustrated by scatter plots of adjacent values, time series plots and directed scatter plots (phase diagrams). The behaviour very much depends on the adic number, with k = 2 being very distinctly non-linear and k = 10 being virtually indistinguishable from independence.
Approximating the stationary distribution of an infinite stochastic matrix
Authors: Heyman Daniel P.
Published: April 2006

We are given a Markov chain with states 0, 1, 2, ···. We want to get a numerical approximation of the steady-state balance equations. To do this, we truncate the chain, keeping the first n states, make the resulting matrix stochastic in some convenient way, and solve the finite system. The purpose of this paper is to provide some sufficient conditions that imply that as n tends to infinity, the stationary distributions of the truncated chains converge to the stationary distribution of the given chain. Our approach is completely probabilistic, and our conditions are given in probabilistic terms. We illustrate how to verify these conditions with five examples.
Strong stochastic convexity: closure properties and applications
Authors: Shanthikumar J. George , Yao David D.
Published: April 2006

A family of random variables {X(θ)} parameterized by the parameter θ satisfies stochastic convexity (SCX) if and only if for any increasing and convex function f(x), Ef[X(θ)] is convex in θ. This definition, however, has a major drawback for the lack of certain important closure properties. In this paper we establish the notion of strong stochastic convexity (SSCX), which implies SCX. We demonstrate that SSCX is a property enjoyed by a wide range of random variables. We also show that SSCX is preserved under random mixture, random summation, and any increasing and convex operations that are applied to a set of independent random variables. These closure properties greatly facilitate the study of parametric convexity of many stochastic systems. Applications to GI/G/1 queues, tandem and cyclic queues, and tree-like networks are discussed. We also demonstrate the application of SSCX in bounding the performance of certain systems.
Rate conservation for stationary processes
Authors: Ferrandiz Josep M. , Lazar Aurel A.
Published: April 2006

We derive a rate conservation law for distribution densities which extends a result of Brill and Posner. Based on this conservation law, we obtain a generalized Takács equation for the G/G/m/B queueing system that only requires the existence of a stochastic intensity for the arrival process and the residual service time distribution density for the G/GI/1/B queue. Finally, we solve Takács' equation for the N/GI/1/∞ queueing system.
On the convex hull of n random points on a circle
Authors: Carnal H. , Hüsler J.
Published: April 2006

We consider the convex hull of a sample of n randomly placed points in a unit circle. Obviously not all of the n points are needed to construct the convex hull. We show that asymptotically only the points belonging to a certain ring are used for the convex hull, where the size of the ring decreases at a certain rate such that the error of not completely correct construction of the convex hull by the particular subset of points tends to 0.
The MacLaurin series for the GI/G/1 queue
Authors: Gong Wei-Bo , Hu Jian-Qiang
Published: April 2006

We derive the MacLaurin series for the moments of the system time and the delay with respect to the parameters in the service time or interarrival time distributions in the GI/G/1 queue. The coefficients in these series are expressed in terms of the derivatives of the interarrival time density function evaluated at zero and the moments of the service time distribution, which can be easily calculated through a simple recursive procedure. The light traffic derivatives can be obtained from these series. For the M/G/1 queue, we are able to recover the formulas for the moments of the system time and the delay, including the Pollaczek–Khinchin mean-value formula.
Stochastic dispatching of multi-priority jobs to heterogeneous processors
Authors: Xu Susan H. , Mirchandani Pitu B. , Kumar Srikanta P. R. , Weber Richard R.
Published: April 2006

A number of multi-priority jobs are to be processed on two heterogeneous processors. Of the jobs waiting in the buffer, jobs with the highest priority have the first option of being dispatched for processing when a processor becomes available. On each processor, the processing times of the jobs within each priority class are stochastic, but have known distributions with decreasing mean residual (remaining) processing times. Processors are heterogeneous in the sense that, for each priority class, one has a lesser average processing time than the other. It is shown that the non-preemptive scheduling strategy for each priority class to minimize its expected flowtime is of threshold type. For each class, the threshold values, which specify when the slower processor is utilized, may be readily computed. It is also shown that the social and the individual optimality coincide.
Marked point processes as limits of Markovian arrival streams
Authors: Asmussen Søren , Koole Ger
Published: April 2006

A Markovian arrival stream is a marked point process generated by the state transitions of a given Markovian environmental process and Poisson arrival rates depending on the environment. It is shown that to a given marked point processthere is a sequenceof such Markovian arrival streams with the property thatasm→∞. Various related corollaries (involving stationarity, convergence of moments and ergodicity) and counterexamples are discussed as well.
Servers in tandem with communication and manufacturing blocking
Authors: Avi-Itzhak Benjamin , Halfin Shlomo
Published: April 2006

Tandem queueing systems with blocking are frequently used in modelling of data communications and production transfer lines. We study such a system with no intermediate queues under the communication and the manufacturing blocking schemes and the assumption of just-in-time input. Explicit expressions for residence times, departure times, equilibrium throughput and some other measures of performance are obtained for the case of equal service requirements at all servers. This case is shown to be the ‘worst’ under the manufacturing blocking scheme, but not under the communication blocking scheme. An approximation formula is proposed for the equilibrium throughput in the case of exponential i.i.d. service times under the manufacturing blocking scheme.
On fast simulation of the time to saturation of slotted ALOHA
Authors: Anantharam V.
Published: April 2006

Cottrell et al. (1983) have indicated how ideas from the large deviations theory lead to fast simulation schemes that estimate the mean time taken by the slotted ALOHA protocol to saturate starting empty. Such fast simulation schemes are particularly useful when the attempt probability is small. The remaining time to saturation when the protocol has been operating for a time is more accurately described by the quasi-stationary exit time from the stable regime. The purpose of this article is to prove that the ratio of the quasi-stationary exit time to the exit time starting empty approaches 1 as the attempt probability becomes small.
Exploiting Markov chains to infer queue length from transactional data
Authors: Daley D. J. , Servi L. D.
Published: April 2006

The use of taboo probabilities in Markov chains simplifies the task of calculating the queue-length distribution from data recording customer departure times and service commencement times such as might be available from automatic bank-teller machine transaction records or the output of telecommunication network nodes. For the case of Poisson arrivals, this permits the construction of a new simple exact O(n3) algorithm for busy periods with n customers and an O(n2 log n) algorithm which is empirically verified to be within any prespecified accuracy of the exact algorithm. The algorithm is extended to the case of Erlang-k interarrival times, and can also cope with finite buffers and the real-time estimates problem when the arrival rate is known.
On the volume distribution of the typical Poisson–Delaunay cell
Authors: Rathie P. N.
Published: April 2006

A method of obtaining the distribution of the volume of the typical cell of a Delaunay tessellation generated by a Poisson process in is developed and used to derive the density when d = 1, 2, 3.
Some joint distributions in Bernoulli excursions
Authors: Csáki Endre
Published: April 2006

Some exact and asymptotic joint distributions are given for certain random variables defined on the excursions of a simple symmetric random walk. We derive appropriate recursion formulas and apply them to get certain expressions for the joint generating or characteristic functions of the random variables.
Solution of finite QBD processes
Authors: de Nitto Personè Vittoria , Grassi Vincenzo
Published: April 2006

We provide an explicit matrix analytic solution for finite quasi birth and death (QBD) processes, directly expressed in terms of process parameters. We show that this solution has the same asymptotic complexity of previously proposed non-explicit solutions and is more general than some of them. Moreover, it can be easily extended to the case of generalized QBD processes.
Approximate upper bounds for the critical probability of oriented percolation in two dimensions based on rapidly mixing Markov chains
Authors: Bollabás Béla , Stacey Alan
Published: April 2006

We develop a technique for establishing statistical tests with precise confidence levels for upper bounds on the critical probability in oriented percolation. We use it to givepc< 0.647 with a 99.999967% confidence. As Monte Carlo simulations suggest thatpc≈ 0.6445, this bound is fairly tight.
Analysis of the Mx/G/1 queue by N-policy and multiple vacations
Authors: Lee Ho Woo , Lee Soon Seok , Park Jeong Ok , Chae K. C.
Published: April 2006

We consider an Mx/G/1 queueing system with N-policy and multiple vacations. As soon as the system empties, the server leaves for a vacation of random length V. When he returns, if the queue length is greater than or equal to a predetermined value N(threshold), the server immediately begins to serve the customers. If he finds less than N customers, he leaves for another vacation and so on until he finally finds at least N customers. We obtain the system size distribution and show that the system size decomposes into three random variables one of which is the system size of ordinary Mx/G/1 queue. The interpretation of the other random variables will be provided. We also derive the queue waiting time distribution and other performance measures. Finally we derive a condition under which the optimal stationary operating policy is achieved under a linear cost structure.
On the transition probabilities of the move-to-front scheme
Authors: Phatarfod R. M.
Published: April 2006

The transition probabilities of the move-to-front scheme are obtained by exploiting the connection between it and the coupon-collector's problem.
Optimal policies for scheduling repairs and allocating heterogeneous servers
Authors: Righter Rhonda
Published: April 2006

We consider the machine repairman, or resource utilization, model in which there is a finite source of jobs with non-identically distributed exponential return times and a single server with job dependent service times. We also consider a related problem of scheduling jobs at heterogeneous servers. We construct a coupling framework that provides a simple unified proof that strengthens many of the results in the literature, and generalizes easily to prove several new results.
The final outcome of an epidemic model with several different types of infective in a large population
Authors: Ball Frank , Clancy Damian
Published: April 2006

We consider a stochastic model for the spread of an epidemic amongst a closed homogeneously mixing population, in which there are several different types of infective, each newly infected individual choosing its type at random from those available. The model is based on the carrier-borne model of Downton (1968), as extended by Picard and Lefèvre (1990). The asymptotic distributions of final size and area under the trajectory of infectives are derived as the initial population becomes large, using arguments based on those of Scalia-Tomba (1985), (1990). We then use our limiting results to compare the asymptotic final size distribution of our model with that of a related multi-group model, in which the type of each infective is assigned deterministically.
A multitype decomposable age-dependent branching process and its applications
Authors: Lee Chinsan , Yang Grace L.
Published: April 2006

Asymptotic formulas for means and variances of a multitype decomposable age-dependent supercritical branching process are derived. This process is a generalization of the Kendall–Neyman–Scott two-stage model for tumor growth. Both means and variances have exponential growth rates as in the case of the Markov branching process. But unlike Markov branching, these asymptotic moments depend on the age of the original individual at the start of the process and the life span distribution of the progenies.
On the estimation of probabilities for birth and death processes
Authors: Zeifman A. I.
Published: April 2006

Let X(t) be a non-homogeneous birth and death process. In this paper we develop a general method of estimating bounds for the state probabilities for X(t), based on inequalities for the solutions of the forward Kolmogorov equations. Specific examples covered include simple estimates of Pr(X(t) < j | X(0) = k) for the M(t)/M(t)/N/0 and M(t)/M(t)/N queue-length processes.
On the calculation of the reliability of general load sharing systems
Authors: Lee Shiowjen , Durham S. , Lynch J.
Published: April 2006

Harlow et al. (1983) have given a recursive formula which is fundamental for computing the bundle strength distribution under a general class of load sharing rules called monotone load sharing rules. As the bundle size increases, the formula becomes prohibitively complex and, by itself, does not give much insight into the relationship of the assumed load sharing rule to the overall strength distribution. In this paper, an algorithm is given which gives some additional insight into this relationship. Here it is shown how to explicitly compute the bundle strength survival distribution by using a new type of graph called the loading diagram. The graph is parallel in structure and recursive in nature and so would appear to lend itself to large-scale computation. In addition, the graph has an interesting property (which we refer to as the cancellation property) which is related to the asymptotics of the Weibull as a minimum stable law.
Analysis of Markov renewal shock models
Authors: Igaki Nobuko , Sumita Ushio , Kowada Masashi
Published: April 2006

A trivariate stochastic process is considered, describing a sequence of random shocks {Xn} at random intervals {Yn} with random system state {Jn}. The triviariate stochastic process satisfies a Markov renewal property in that the magnitude of shocks and the shock intervals are correlated pairwise and the corresponding joint distributions are affected by transitions of the system state which occur after each shock according to a Markov chain. Of interest is a system lifetime terminated whenever a shock magnitude exceeds a prespecified level z. The distribution of system lifetime, its moments and a related exponential limit theorem are derived explicitly. A similar transform analysis is conducted for a second type of system lifetime with system failures caused by the cumulative magnitude of shocks exceeding a fixed level z.
Optimizing a single uncertain selection by recall of observations
Authors: Sweet Ted
Published: April 2006

This paper considers a variation of the classical secretary problem; this variation allows for the interviewer to make an offer to previously interviewed applicants and for the applicant to reject an offer. In this version, the process ends after any offer is made. Two special cases are considered, where the optimal procedure and its probability of success are given for each. Furthermore, the problem is discussed in general and conditions for optimal strategies are given.
Uniqueness of maximum values in discrete distributions
Authors: Floréen Patrik , Huuskonen Taneli
Published: April 2006

We discuss the probability that among a number of random discrete values there is a unique maximal value. Some general inequalities are derived. As an application, we study the limit behavior of the probability of uniqueness for a subexponential number of binomially distributed variables.
Braess's paradox in a loss network
Authors: Bean N. G. , Kelly F. P. , Taylor P. G.
Published: April 2006

Braess's paradox is said to occur in a network if the addition of an extra link leads to worse performance. It has been shown to occur in transportation networks (such as road networks) and also in queueing networks. Here, we show that it can occur in loss networks.