In this paper, we present the distribution of the coalescence time of two DNA sequences (or genes) subject to symmetric migration between two islands, and conditional on the observed number of segregating sites in the sequences. The distribution for the segregating-site pattern is also obtained. Some surprising results emerge when both genes are initially on the same island. First, the post-data mean coalescence time is shown to be dependent on the migration parameter, as opposed to the pre-data mean. Second, both the post-data density and expectation for the coalescence time are shown to converge, in the weak-migration limit, to the corresponding panmictic results, as opposed to the pre-data situation where there is convergence in the density but not in the expectation. Finally, it is shown that there is convergence in the weak-migration limit in the distribution of the number of segregating sites but not in the expectation and variance. Numerical and graphical results for samples of size greater than two are also presented.

A complete and sufficient statistic is found for various stationary Poisson processes of compact sets with known primary grain. In the particular case of a segment process, the uniformly best unbiased estimator for the length density is the number of segments hitting the sampling window divided by a certain constant and multiplied by the mean segment length.

We consider generalisations of two classical stochastic scheduling models, namely the discounted branching bandit and the discounted multi-armed bandit, to the case where the collection of machines available for processing is itself a stochastic process. Under rather mild conditions on the machine availability process we obtain performance guarantees for a range of controls based on Gittins indices. Various forms of asymptotic optimality are established for index-based limit policies as the discount rate approaches 0.

We study a Markovian model for a perishable inventory system with random input and an external source of obsolescence: at Poisson random times the whole current content of the system is spoilt and must be scrapped. The system can be described by its virtual death time process. We derive its stationary distribution in closed form and find an explicit formula for the Laplace transform of the cycle length, defined as the time between two consecutive item arrivals in an empty system. The results are used to compute several cost functionals. We also derive these functionals under the corresponding heavy traffic approximation, which is modeled using a Brownian motion in [0,1] reflected at 0 and 1 and restarted at 1 at the Poisson disaster times.

Variograms and covariance functions are key tools in geostatistics. However, various properties, characterizations, and decomposition theorems have been established for covariance functions only. We present analogous results for variograms and explore the connections with covariance functions. Our findings include criteria for covariance functions on intervals, and we apply them to exponential models, fractional Brownian motion, and locally polynomial covariances. In particular, we characterize isotropic locally polynomial covariance functions of degree 3.

We show that if performance measures in a general stochastic scheduling problem satisfy partial conservation laws (PCL), which extend the generalized conservation laws (GCL) introduced by Bertsimas and Niño-Mora (1996), then the problem is solved optimally by a priority-index policy under a range of admissible linear performance objectives, with both this range and the optimal indices being determined by a one-pass adaptive-greedy algorithm that extends Klimov's: we call such scheduling problems PCL-indexable. We further apply the PCL framework to investigate the indexability property of restless bandits (two-action finite-state Markov decision chains) introduced by Whittle, obtaining the following results: (i) we present conditions on model parameters under which a single restless bandit is PCL-indexable, and hence indexable; membership of the class of PCL-indexable bandits is tested through a single run of the adaptive-greedy algorithm, which further computes the Whittle indices when the test is positive; this provides a tractable sufficient condition for indexability; (ii) we further introduce the subclass of GCL-indexable bandits (including classical bandits), which are indexable under arbitrary linear rewards. Our analysis is based on the achievable region approach to stochastic optimization, as the results follow from deriving and exploiting a new linear programming reformulation for single restless bandits.

Siegmund and Worsley (1995) considered the problem of testing for signals with unknown location and scale in a Gaussian random field defined on ℝN. The test statistic was the maximum of a Gaussian random field in an N+1 dimensional ‘scale space’, N dimensions for location and 1 dimension for the scale of a smoothing filter. Scale space is identical to a continuous wavelet transform with a kernel smoother as the wavelet, though the emphasis here is on signal detection rather than image compression or enhancement. Two methods were used to derive an approximate null distribution for N=2 and N=3: one based on the method of volumes of tubes, the other based on the expected Euler characteristic of the excursion set. The purpose of this paper is two-fold: to show how the latter method can be extended to higher dimensions, and to apply this more general result to χ2 fields. The result of Siegmund and Worsley (1995) then follows as a special case. In this paper the results are applied to the problem of searching for activation in brain images obtained by functional magnetic resonance imaging (fMRI).

Sun and Waterman model DNA mutations during the PCR reaction by a non-canonical branching process. Mean-field approximated values fit the simulated values surprisingly well. We prove this as a theoretical result, for a wide range of the parameters. Thus, we bound explicitly the biases, in law and in the mean, that the mean-field approximation induces in the random number of mutations of a DNA molecule, as a function of the initial number of molecules, of the number of PCR cycles, of the efficiency rate and of the mutation rate. The range where we prove that the approximation is good contains the observed mutation rates in many actual PCR reactions.

We consider a stochastic model for the spread of an SIR (susceptible → infective → removed) epidemic among a closed, finite population that contains several types of individuals and is partitioned into households. The infection rate between two individuals depends on the types of the transmitting and receiving individuals and also on whether the infection is local (i.e., within a household) or global (i.e., between households). The exact distribution of the final outcome of the epidemic is outlined. A branching process approximation for the early stages of the epidemic is described and made fully rigorous, by considering a sequence of epidemics in which the number of households tends to infinity and using a coupling argument. This leads to a threshold theorem for the epidemic model. A central limit theorem for the final outcome of epidemics which take off is derived, by exploiting an embedding representation.

We consider a parametrization of the Heath-Jarrow-Morton (HJM) family of term structure of interest rate models that allows a finite-dimensional Markovian representation of the stochastic dynamics. This parametrization results from letting the volatility function depend on time to maturity and on two factors: the instantaneous spot rate and one fixed-maturity forward rate. Our main purpose is an estimation methodology for which we have to model the observations under the historical probability measure. This leads us to consider as an additional third factor the market price of interest rate risk, that connects the historical and the HJM martingale measures. Assuming that the information comes from noisy observations of the fixed-maturity forward rate, the purpose is to estimate recursively, on the basis of this information, the three Markovian factors as well as the parameters in the model, in particular those in the volatility function. This leads to a nonlinear filtering problem, for the solution of which we describe an approximation methodology, based on time discretization and quantization. We prove the convergence of the approximate filters for each of the observed trajectories.

With the aim of providing greater flexibility in developing and applying shot noise models, this paper studies shot noise on cluster point processes with both pointwise and cluster marks. For example, in financial modelling, responses to events in the financial market may occur in clusters, with random amplitudes including a ‘cluster component’ reflecting a degree of commonness among responses within a cluster. For such shot noise models, general formulae for the characteristic functional are developed and specialized to the case of Neyman-Scott clustering with cluster marks. For several general forms of response function, long range dependence of the corresponding equilibrium shot noise models is investigated. It is shown, for example, that long range dependence holds when the ‘structure component’ of the response function decays slowly enough, or when the response function has a finite random duration with a heavy tailed distribution.

We consider the problem of optimally tracking a Brownian motion by a sequence of impulse controls, in such a way as to minimize the total expected cost that consists of a quadratic deviation cost and a proportional control cost. The main feature of our model is that the control can only be exerted at the arrival times of an exogenous uncontrolled Poisson process (signal). In other words, the set of possible intervention times are discrete, random and determined by the signal process (not by the decision maker). We discuss both the discounted problem and the ergodic problem, where explicit solutions can be found. We also derive the asymptotic behavior of the optimal control policies and the value functions as the intensity of the Poisson process goes to infinity, or roughly speaking, as the set of admissible controls goes from the discrete-time impulse control to the continuous-time bounded variation control.

We prove a d-dimensional renewal theorem, with an estimate on the rate of convergence, for Markov random walks. This result is applied to a variety of boundary crossing problems for a Markov random walk (Xn,Sn), n ≥0, in which Xn takes values in a general state space and Sn takes values in ℝd. In particular, for the case d = 1, we use this result to derive an asymptotic formula for the variance of the first passage time when Sn exceeds a high threshold b, generalizing Smith's classical formula in the case of i.i.d. positive increments for Sn. For d > 1, we apply this result to derive an asymptotic expansion of the distribution of (XT,ST), where T = inf { n : Sn,1 > b } and Sn,1 denotes the first component of Sn.

This article deals with the distribution of the view of a random environment as seen by an observer whose location at each moment is determined by the environment. The main application is in statistical fluid mechanics, where the environment consists of a random velocity field and the observer is a particle moving in the velocity field, possibly subject to molecular diffusion. Several results on such Lagrangian observations of the environment have appeared in the literature, beginning with the 1957 dissertation of J. L. Lumley. This article unites these results into a simple unified framework and rounds out the theory with new results in several directions. When the environment is homogeneous, the problem can be re-cast in terms of certain random mappings on the physical space that are based on the random location of the observer. If these mappings preserve the invariant measure on the physical space, then the view from the random location has the same distribution as the view from the origin. If these mappings satisfy the flow property and the environment is stationary, then the succession of Lagrangian observations over time forms a strictly stationary process. In particular, for motion in a homogeneous, stationary, and nondivergent velocity field, the Lagrangian velocity (the velocity of the particle) is strictly stationary, which was first observed by Lumley. In the compressible case, the distribution of a Lagrangian observation has a density with respect to the distribution of the view from the origin, and in some cases convergence in distribution of the Lagrangian observations as time tends to infinity can be shown.

Following Füredi and Komlós, we develop a graph theory method to study the high moments of large random matrices with independent entries. We apply this method to sparse N × N random matrices AN,p that have, on average, p non-zero elements per row. One of our results is related to the asymptotic behaviour of the spectral norm ∥AN,p∥ in the limit 1 ≪ p ≪ N. We show that the value pc = log N is the critical one for lim ∥AN,p/√p∥ to be bounded or not. We discuss relations of this result with the Erdős–Rényi limit theorem and properties of large random graphs. In the proof, the principal issue is that the averaged vertex degree of plane rooted trees of k edges remains bounded even when k → ∞. This observation implies fairly precise estimates for the moments of AN,p. They lead to certain generalizations of the results by Sinai and Soshnikov on the universality of local spectral statistics at the border of the limiting spectra of large random matrices.

We present a stochastic algorithm which generates optimal probabilities for the chaos game to decompress an image represented by the fixed point of an IFS operator. The algorithm can be seen as a sort of time-inhomogeneous regenerative process. We prove that optimal probabilities exist and, by martingale methods, that the algorithm converges almost surely. The method holds for IFS operators associated with any arbitrary number of possibly overlapping affine contraction maps on the pixels space.

Let X(t) be a continuous two-dimensional stationary Gaussian process with mean zero, having a marginal density function p[x] and covariance matrix R(t). Let Δ = {∂L; L > 0} be a family of piecewise smooth boundaries of similar two-dimensional star-shaped regions ΓL. We show that, under two conditions on R(t), the asymptotic distribution of the duration of an excursion of X(t) outside ΓL, for large L, depends on the position of the maximum of p[x] on ∂L and on whether R′(0) is zero or not, should the maximum occur at a vertex. We obtain the asymptotic distributions of the duration of an excursion for each of the three cases that arise. We also generalise some results of Breitung (1994) on the asymptotic crossing rates of vector Gaussian processes.

Sharp upper and lower bounds are derived for the solution of renewal equations. These include as special cases exponential inequalities, some of which have been derived for specific renewal equations. Together with the well-known Cramér-Lundberg asymptotic estimate, these bounds give additional information about the behaviour of the solution. Nonexponential bounds, which are of use in connection with defective renewal equations, are also obtained. The results are then applied in examples involving the severity of insurance ruin, age-dependent branching processes, and a generalized type II Geiger counter.

In this paper we study the asymptotic relationship between the loss ratio in a finite buffer system and the overflow probability (the tail of the queue length distribution) in the corresponding infinite buffer system. We model the system by a fluid queue which consists of a server with constant rate c and a fluid input. We provide asymptotic upper and lower bounds on the difference between log P{Q > x} and logPL(x) under different conditions. The conditions for the upper bound are simple and are satisfied by a very large class of input processes. The conditions on the lower bound are more complex but we show that various classes of processes such as Markov modulated and ARMA type Gaussian input processes satisfy them.