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

In many communication and computer systems, information arrives to a multiplexer, switch or information processor at a rate which fluctuates randomly, often with a high degree of correlation in time. The information is buffered for service (the server typically being a communication channel or processing unit) and the service rate may also vary randomly. Accurate capture of the statistical properties of these fluctuations is facilitated by modeling the arrival and service rates as superpositions of a number of independent finite state reversible Markov processes. We call such models separable Markov-modulated rate processes (MMRP).

In this work a general mathematical model for separable MMRPs is presented, focusing on Markov-modulated continuous flow models. An efficient procedure for analyzing their performance is derived. It is shown that the ‘state explosion' problem typical of systems composed of a large number of subsystems, can be circumvented because of the separability property, which permits a decomposition of the equations for the equilibrium probabilities of these systems. The decomposition technique (generalizing a method proposed by Kosten) leads to a solution of the equilibrium equations expressed as a sum of terms in Kronecker product form. A key consequence of decomposition is that the computational complexity of the problem is vastly reduced for large systems. Examples are presented to illustrate the power of the solution technique.

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.

Here a response of a non-linear oscillator of the Liénard type with a large parameter α ≥ 0 is formulated as a solution of a two-dimensional stochastic differential equation with mean-field of the McKean type. This solution is governed by a special form of the Fokker–Planck equation such as the Smoluchowski–Kramers equation, which is an equation of motion for distribution functions in position and velocity space describing the Brownian motion of particles in an external field. By a change of time and displacement we find that the velocity process converges to a one-dimensional Ornstein–Uhlenbeck process as α →∞.

We consider the repairman problem which corresponds to the finite population M/M/1 queue. Asymptotic approximations for the transient probability distribution of the number of broken machines constructed when the number M of machines is large and the service (repair) rate is also large, specifically, O(M). The approximations are constructed by using singular perturbation techniques such as the ray method, boundary layer theory, and the method of matched asymptotic expansions. Extensive numerical comparisons show the quality of our approximations.

In this paper, we study a synchronous computer network model which may be described as follows. There are n service stations around a circle and there are k people to be serviced with at most one person per station. Time is slotted and in each time slot b adjacent people with an empty station ahead can move synchronously and simultaneously to the next counterclockwise station with probability pb. We show that the stationary distribution is uniform on all possible states, and using the Descartes' rule of signs we find the optimal value of k (fixed p and n) that yields maximal ‘throughput', i.e., the expected number of people served per time slot in equilibrium. We also briefly study an asynchronous model (introduced by D. Sarkar) where in each time slot a person moves with probability p to the next counterclockwise station if it is empty. We find, among other results, the new stationary distribution (Ramakrishnan et al. (1989) also find independently the stationary distribution and they also find the optimal value of k (fixed p and n) that yields maximal throughput in this model). We give tables comparing the synchronous and asynchronous models. Some applications which motivate this study are briefly presented.

This paper is concerned with a random walk process in which and for i = 1, 2, ···, 2n. This process is called a Bernoulli excursion. The main object is to find the distribution, the moments, and the asymptotic distribution of the random variable ω n defined by . The results derived have various applications in the theory of probability, including random graphs, tournaments and order statistics.

We consider a semi-Markov process with finite state space, partitioned into two classes termed ‘open' and ‘closed'. It is possible to observe only which class the process is in. We show that complete information concerning the aggregated process is contained in an embedded Markov renewal process, whose parameters, moments and equilibrium behaviour are determined. Such processes have found considerable application in stochastic modelling of single ion channels. In that setting there is time interval omission, i.e. brief sojourns in either class failed to be detected. Complete information on the aggregated process incorporating time interval omission is contained in a Markov renewal process, whose properties are derived, obtained from the above Markov renewal process by a further embedding. The embedded Markov renewal framework is natural, and its invariance to time interval omission leads to considerable economy in the derivation of properties of the observed process. The results are specialised to the case when the underlying process is a continuous-time Markov chain.

Suppose that in a ballot candidate A scores a votes and candidate B scores b votes, and that all the possible voting records are equally probable. Corresponding to the first r votes, let α r and β r be the numbers of votes registered for A and B, respectively. Let p be an arbitrary positive real number. Denote by δ (a, b, p)[δ *(a, b, ρ)] the number of values of r for which the inequality , r = 1, ···, a + b, holds. Heretofore the probability distributions of δand δ* have been derived for only a restricted set of values of a, b, and ρ, although, as pointed out here, they are obtainable for all values of (a, b, ρ) by using a result of Takács (1964). In this paper we present a derivation of the distribution of δ [δ *] whose development, for any (a, b, ρ), leads to both necessary and sufficient conditions for δ [δ *] to have a discrete uniform distribution.

This paper deals with the stationary bilinear model with Hermite degree 2 in discrete time which is built up by the first- and second-order Hermite polynomial of a Gaussian white noise process. The exact spectrum and bispectrum is constructed in terms of the transfer functions of the model.

We consider a ‘reduced state space' approach to the analysis of blocking in stochastic loss networks. We show how this approach provides insight into the approximations currently used in large networks and enables improved approximations to be deduced. We further give some ‘heavy traffic' asymptotic results for the limiting scheme of Kelly (1986).

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.

This paper presents a new approach for obtaining heavy-traffic limits for infinite-server queues and open networks of infinite-server queues. The key observation is that infinite-server queues having deterministic service times can easily be analyzed in terms of the arrival counting process. A variant of the same idea applies when the service times take values in a finite set, so this is the key assumption. In addition to new proofs of established results, the paper contains several new results, including limits for the work-in-system process, limits for steady-state distributions, limits for open networks with general customer routes, and rates of convergence. The relatively tractable Gaussian limits are promising approximations for many-server queues and open networks of such queues, possibly with finite waiting rooms.

The Ehrenfest urn model with d balls, or alternatively random walk on the unit cube in d dimensions, 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.

We consider a system of N finite-capacity queues attended by a single server in cyclic order. For each visit by the server to a queue, the service is given continuously until that queue becomes empty (exhaustive service), given continuously only to those customers present at the visiting instant (gated service), or given to only a single customer (limited service). The server then switches to the next queue with a random switchover time, and administers the same type of service there similarly. For such a system where each queue has a Poisson arrival process, general service time distribution, and finite capacity, we find the distribution of the waiting time at each queue by utilizing the known results for a single M/G/1/K queue with multiple vacations.

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.

Let X1, X2, · ··, Xn be positive i.i.d. random variables with known distribution function having a finite mean. For a given s ≥0 we define Nn = N(n, s) to be the largest number k such that the sum of the smallest k Xs does not exceed s, and Mn = M(n, s) to be the largest number k such that the sum of the largest k X's does not exceed s. This paper studies the precise and asymptotic behaviour of E(Nn), E(Mn), Nn, Mn, and the corresponding ‘stopped' order statistics and as n →∞, both for fixed s, and where s =sn is an increasing function of n.

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.

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

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