Given two random k-ary sequences of length n, what is f(n,k), the expected length of their longest common subsequence? This problem arises in the study of molecular evolution. We calculate f(n,k) for all k, where n ≦ 5, and f(n,2) where n ≦ 10. We study the limiting behaviour of n–1f(n,k) and derive upper and lower bounds on these limits for all k. Finally we estimate by Monte-Carlo methods f(100,k), f(1000,2) and f(5000,2).

Two distributions, F and G, are said be ordered in dispersion if F-1(β)-F-1(α)≦G-1(β)-G-1(α) whenever 0<α <β <1. This relation has been studied by Saunders and Moran (1978). The purpose of this paper is to study this partial ordering in detail. Few characterizations of this concept are given. These characterizations are then used to show that some particular pairs of distributions are ordered by dispersion. In addition to it some proofs of results of Saunders and Moran (1978) are simplified. Furthermore, the characterizations of this paper can be used to throw a new light on the meaning of the underlying partial ordering and also to derive various inequalities. Several examples illustrate the methods of this paper.

We study single-server queueing models where in addition to regular arriving customers, there are negative arrivals. A negative arrival has the effect of removing a customer from the queue. The way in which this removal is specified gives rise to several different models. Unlike the standard FIFO GI/GI/1 model, the stability conditions for these new models may depend upon more than just the arrival and service rates; the entire distributions of interarrival and service times may be involved.

Motivated by edge behaviour reported for biological organisms, we show that random walks with a bias at a boundary lead to a discontinuous probability density across the boundary. We continue by studying more general diffusion processes with such a discontinuity across an interior boundary. We show how hitting probabilities, occupancy times and conditional occupancy times may be solved from problems that are adjoint to the original diffusion problem. We highlight our results with a biologically motivated example, where we analyze the movement behaviour of an individual in a network of habitat patches surrounded by dispersal habitat.

If τ is the lifetime of a coherent system, then the signature of the system is the vector of probabilities that the lifetime coincides with the ith order statistic of the component lifetimes. The signature can be useful in comparing different systems. In this treatment we give a characterization of the signature of a system with independent identically distributed components in terms of the number of path sets in the system as well as in terms of the number of what we call ordered cut sets. We consider, in particular, the signatures of indirect majority systems and compare them with the signatures of simple majority systems of the same size. We note that the signature of an indirect majority system of size r × s = n is symmetric around , and use this to show that the expected lifetime of an r × s = n indirect majority system exceeds that of a simple (direct) majority system of size n when the components are exponentially distributed with the same parameter.

Known results relating the tail behaviour of a compound Poisson distribution function to that of its Lévy measure when one of them is convolution equivalent are extended to general infinitely divisible distributions. A tail equivalence result is obtained for random sum distributions in which the summands have a two-sided distribution.

We consider closed networks of interconnected service centers with multiple types of customers and multiple classes, whose stationary state probabilities at arbitrary times have a product form. A customer can change its class but not its type as it traverses the network. We show that the stationary state probabilities at instants at which customers of a particular type arrive at a particular service center and enter a particular class are equal to the stationary state probabilities at arbitrary times for the network with one less customer of that type. Applications of this result are given.

A definition of ESS (evolutionarily stable strategy) is suggested for games in which there are two types of player, each with its own set of strategies, and the fitness of any strategy depends upon the strategy mix, of both types, in the population as a whole. We check that the standard ESS results hold for this definition and discuss a mate-desertion model which has appeared in the literature in which the two types are male and female.

We prove large deviation results for the random sum , , where are non-negative integer-valued random variables and are i.i.d. non-negative random variables with common distribution function F, independent of . Special attention is paid to the compound Poisson process and its ramifications. The right tail of the distribution function F is supposed to be of Pareto type (regularly or extended regularly varying). The large deviation results are applied to certain problems in insurance and finance which are related to large claims.

We shall consider a many server (multiple channels in parallel) queueing process in which customers arrive at the queue according to a Poisson process. The service times are assumed to be independent and exponentially distributed. As usual, the service times are independent of the arrival process. We assume that no server is idle if there is a customer waiting, but that otherwise the service discipline is arbitrary. If there are n servers and we let Xn(t) denote the number of customers waiting or being served at time t, then it is well known that Xn(t) is a birth and death process with stationary transition probabilities. A very comprehensive analysis of this many server queue from the point of view of birth and death processes has been carried out by Karlin and McGregor [5].

A saddlepoint expansion is given for conditional probabilities of the form where is an average of n independent bivariate random vectors. A more general version, corresponding to the conditioning on a p – 1-dimensional linear function of a p-dimensional variable is also included. A separate formula is given for the lattice case. The expansion is a generalization of the Lugannani and Rice (1980) formula, which reappears if and are independent. As an example an approximation to the hypergeometric distribution is derived.

Let M be a random matrix chosen from Haar measure on the unitary group Un. Let Z = X + iY be a standard complex normal random variable with X and Y independent, mean 0 and variance ½ normal variables. We show that for j = 1, 2, …, Tr(Mj) are independent and distributed as √jZ asymptotically as n →∞. This result is used to study the set of eigenvalues of M. Similar results are given for the orthogonal and symplectic and symmetric groups.

We apply the general theory of stochastic integration to identify a martingale associated with a Lévy process modified by the addition of a secondary process of bounded variation on every finite interval. This martingale can be applied to queues and related stochastic storage models driven by a Lévy process. For example, we have applied this martingale to derive the (non-product-form) steady-state distribution of a two-node tandem storage network with Lévy input and deterministic linear fluid flow out of the nodes.

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.

The maximum drawdown at time T of a random process on [0,T] can be defined informally as the largest drop from a peak to a trough. In this paper, we investigate the behaviour of this statistic for a Brownian motion with drift. In particular, we give an infinite series representation of its distribution and consider its expected value. When the drift is zero, we give an analytic expression for the expected value, and for nonzero drift, we give an infinite series representation. For all cases, we compute the limiting (T → ∞) behaviour, which can be logarithmic (for positive drift), square root (for zero drift) or linear (for negative drift).

We study geometric moment contracting properties of nonlinear time series that are expressed in terms of iterated random functions. Under a Dini-continuity condition, a central limit theorem for additive functionals of such systems is established. The empirical processes of sample paths are shown to converge to Gaussian processes in the Skorokhod space. An exponential inequality is established. We present a bound for joint cumulants, which ensures the applicability of several asymptotic results in spectral analysis of time series. Our results provide a vehicle for statistical inferences for fractals and many nonlinear time series models.

An expression is found for the stationary density of the allele frequencies, in the infinitely-many alleles model. It is assumed that all alleles are neutral, that there is a constant mutation rate, and that the population is sufficiently large for the diffusion model to apply. Bounds on some moments are calculated from the density, and some applications are made to the problem of which allele is oldest in a population. A postulate made by Ewens (1972), concerning the distribution of allele numbers in a finite random sample from the neutral diffusion population, is shown to be correct.

1. 1. (Y) for all non-negative, non-decreasing convex functions φ (X is convexly smaller than Y) if and only if, for all .

2. 2. Let H be the Hardy–Littlewood maximal function HY(x) = E(Y – X | Y > x). Then HY(Y) is the smallest random variable exceeding stochastically all random variables convexly smaller than Y.

3. 3. Let X1X2 · ·· Xn be random variables with given marginal distributions, let I1,I2, ···, Ik be arbitrary non-empty subsets of {1,2, ···, n} and let M = max (M is the completion time of a PERT network with paths Ij, and delay times Xi.) The paper introduces a computation of the convex supremum of M in the class of all joint distributions of the Xi's with specified marginals, and of the ‘bottleneck probability' of each path.

As proposed by Ebrahimi, uncertainty in the residual lifetime distribution can be measured by means of the Shannon entropy. In this paper, we analyse a dual characterization of life distributions that is based on entropy applied to the past lifetime. Various aspects of this measure of uncertainty are considered, including its connection with the residual entropy, the relation between its increasing nature and the DRFR property, and the effect of monotonic transformations on it.

A queueing theoretic model of an assembly operation is introduced. The model, consisting of K ≧ 2 renewal input processes and a single server, is a multiple input generalization of the GI/G/1 queue. The server requires one input item of each type k = 1,…, K for each of his services. It is shown that the model is inherently unstable in the following sense. The associated vector waiting time process Wn cannot converge in distribution to a non-defective limit, regardless of how well balanced the input and service processes may be. Limit theorems are developed for appropriately normalized versions of Wn under the various possible load conditions. Another waiting time process, equivalent to that in a single-server queue whose input is the minimum of K renewal processes, is also identified. It is shown to converge in distribution to a particular limit under certain load conditions.