Asymptotic distributional properties of the maximal length aligned word (a contiguous set of letters) among multiple random Markov dependent sequences composed of letters from a finite alphabet are given. For sequences of length N, Cr,s(N) defined as the longest common aligned word found in r or more of s sequences has order growth log N/(–logλ) where λis the maximal eigenvalue of r-Schur product matrices from among the collections of Markov matrices that generate the sequences. The count Z∗r,s(N, k) of positions that initiate an aligned match of length exceeding k = log N/(–logλ) + x but fail to match at the immediately preceding position has a limiting Poisson distribution. Distributional properties of other long aligned word relationships and patterns are also discussed.

The theory of Markov renewal processes is applied to study the occurrence of specific sequences of states in a Markov chain. Çinlar&s (1969) results are used to study both the basic process, and that obtained when the overlap of sequences is not permitted, as in the theory of counters. These results are applied to the fragments formed when DNA is digested using one, or more, restriction enzymes.

This paper is concerned with a pure death process, starting with N individuals, with death rates μ n, n = 1, 2, …, N. It is shown that the fates of distinct individuals are positively correlated if μ n/n decreases with n, and negatively correlated if μ n/n increases with n. The application of this result to the problem of variability in compartmental models is elaborated and in particular a conjecture of Faddy (1985) is settled. Further applications to well-known death processes are also briefly described.

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

Let N(t) be a finite semi-Markov process on 𝒩 and let X(t) be the associated age process. Of interest is the counting process M(t) for transitions of the semi-Markov process from a subset G of 𝒩 to another subset B where 𝒩 = B ∪ G and B ∩ G = ∅. By studying the trivariate process Y(t) =[N(t), M(t), X(t)] in its state space, new transform results are derived. By taking M(t) as a marginal process of Y(t), the Laplace transform generating function of M(t) is then obtained. Furthermore, this result is recaptured in the context of first-passage times of the semi-Markov process, providing a simple probabilistic interpretation. The asymptotic behavior of the moments of M(t) as t → ∞ is also discussed. In particular, an asymptotic expansion for E[M(t)] and the limit for Var [M(t)]/t as t → ∞ are given explicitly.

Conditions are given under which a space-time jump Markov process describing the stochastic model of non-linear chemical reactions with diffusion converges to the homogeneous state solution of the corresponding reaction-diffusion equation. The deviation is measured by a central limit theorem. This limit is a distribution-valued Ornstein–Uhlenbeck process and can be represented as the mild solution of a certain stochastic partial differential equation.

We consider a Markov process with state space {0, 1}Z where Os become 1s irreversibly at rates which depend on whether none of a 0&s nearest neighbours (nucleation), its left-hand neighbour (right-hand growth), or its right-hand neighbour (left-hand growth) is in the 1-state. Furthermore, we assume that Os with both nearest neighbours in the 1-state remain in the 0-state forever and that at time 0 only the origin is in the 1-state. We determine the size distribution of the cluster (maximal sequence of 1s uninterrupted by Os) at the origin and the distribution of the time when its growth is stopped (by birth (nucleation) or competitive growth of neighbouring clusters). In the final state of the process, the spatial distribution of the (trapped) sites in the 0-state is considered. Some information on the size distribution of clusters well away from the cluster at the origin is obtained.

A general way to look at kernel estimates of densities is to regard them as stochastic integrals with respect to a spatial point process. Under regularity conditions these behave asymptotically as if the point process were Poisson. However, this Poisson approximation may not work well if the data exhibits a lot of clustering. In this paper a more refined approximation to the characteristic functions of the integrals is developed. For clustered data, a ‘Gauss–Poisson’ approximation works better than the Poisson.

A natural model for stochastic flow systems is regulated or reflecting Brownian motion (RBM), which is Brownian motion on the positive real line with constant negative drift and constant diffusion coefficient, modified by an impenetrable reflecting barrier at the origin. As a basis for understanding how stochastic flow systems approach steady state, this paper provides relatively simple descriptions of the moments of RBM as functions of time. In Part I attention is restricted to the case in which RBM starts at the origin; then the moment functions are increasing. After normalization by the steady-state limits, these moment c.d.f.&s (cumulative distribution functions) coincide with gamma mixtures of inverse Gaussian c.d.f.&s. The first moment c.d.f. thus coincides with the first-passage time to the origin starting in steady state with the exponential stationary distribution. From this probabilistic characterization, it follows that the kth-moment c.d.f is the k-fold convolution of the first-moment c.d.f. As a consequence, it is easy to see that the (k + 1)th moment approaches its steady-state limit more slowly than the kth moment. It is also easy to derive the asymptotic behavior as t →∞. The first two moment c.d.f.&s have completely monotone densities, supporting approximation by hyperexponential (H2) c.d.f.&s (mixtures of two exponentials). The H2 approximations provide easily comprehensible descriptions of the first two moment c.d.f.&s suitable for practical purposes. The two exponential components of the H2 approximation yield simple exponential approximations in different regimes. On the other hand, numerical comparisons show that the limit related to the relaxation time does not predict the approach to steady state especially well in regions of primary interest. In Part II (Abate and Whitt (1987a)), moments of RBM with non-zero initial conditions are treated by representing them as the difference of two increasing functions, one of which is the moment function starting at the origin studied here.

The first-passage-time p.d.f. through a time-dependent boundary for one-dimensional diffusion processes is proved to satisfy a new Volterra integral equation of the second kind involving two arbitrary continuous functions. Use of this equation is made to prove that for the Wiener and the Ornstein–Uhlenbeck processes the singularity of the kernel can be removed by a suitable choice of these functions. A simple and efficient numerical procedure for the solution of the integral equation is provided and its convergence is briefly discussed. Use of this equation is finally made to obtain closed-form expressions for first-passage-time p.d.f.'s in the case of various time-dependent boundaries.

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

We consider the N-oscillator system of the van der Pol type, which contains a small positive parameter ε multiplying the non-linear damping and the random disturbance. For a formulation of the output we take the solution X(t) = (Xi(t))i=1···,N of the system of 2N-dimensional stochastic differential equations. Rotating each component Xi(t) about the origin of the plane by an angle t, we find that on time scales of order 1/ε together with sufficiently large N each Xi(t) behaves as the equi-ultimately bounded solution of an equation of the McKean type admitting a stationary probability distribution.

This paper continues an investigation of the time-dependent behavior of regulated or reflecting Brownian motion (RBM). Part I focused on RBM starting at the origin; Part II focuses on RBM starting at a fixed positive state. The first two moments of RBM as functions of time are analyzed by representing them as the difference of two increasing functions, one of which is the moment function starting at the origin studied in Part I. By appropriate normalization, the two monotone components can be converted into cumulative distribution functions that can be analyzed probabilistically, e.g., their moments can be calculated. Simple approximations are then developed by fitting convenient distributions to these moments. Overall, the analysis yields a better understanding of the way RBM and related stochastic flow systems approach steady state.

Records from the sequence Yn = Xn + cn, n ≧ 1 are analyzed, where {Xn} is a strictly stationary random sequence. We prove various limit theorems for the record rate, record times, and record values. The situation when {Xn} is a stationary Gaussian process is considered with special attention given to Gaussian ARMA sequences. Data for the 400 and 800 metre races are used to illustrate these results.

The method of Skorokhod embedding, that is to say of coupling to Brownian motion, is used to establish the asymptotic behaviour of one-dimensional scattering processes.

A regression approximation of wavelength and amplitude distribution in an almost surely continuous process η (t), is based on a successively more detailed decomposition, η (t) = η n(t) + Δn(t), into one regression term η n on n suitably chosen random quantities, and one residual process Δn. The distances between crossings, maxima, etc., are then approximated by the corresponding quantities in the regression term, and explicit expressions given for the densities of these quantities.

We consider a class of functions on [0,∞), denoted by Ω, having Laplace transforms with only negative zeros and poles. Of special interest is the class Ω+ of probability density functions in Ω. Simple and useful conditions are given for necessity and sufficiency of f ∊ Ω to be in Ω+. The class Ω+ contains many classes of great importance such as mixtures of n independent exponential random variables (CMn), sums of n independent exponential random variables (PF∗n), sums of two independent random variables, one in CMr and the other in PF∗1 (CMPFn with n = r + l) and sums of independent random variables in CMn(SCM). Characterization theorems for these classes are given in terms of zeros and poles of Laplace transforms. The prevalence of these classes in applied probability models of practical importance is demonstrated. In particular, sufficient conditions are given for complete monotonicity and unimodality of modified renewal densities.

Let Xt, be a Markov random field assuming values in RM. Let In be a rectangular box in Zm with its center at 0 and corner points with coordinates ±n. Let (An) be a sequence of measurable subsets of RM such that neighborhood of t) → 0, for n → ∞; and let fn(x) be the indicator of An. Under appropriate conditions on the nearest-neighbor distributions of (Xt), the conditional distribution of given the values of Xs, for s on the boundary of In, converges to the Poisson distribution. An immediate application is an extreme value limit theorem for a real-valued Markov random field.

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

In this paper we obtain conditions under which partial balance in a component is preserved and these often amount to the requirement that there exists a quantity which is unaffected by the internal workings of the component in question. We give particular attention to the components of a stratified clustering process as these most often suffer from loss of partial balance.

A class of optimal stopping problems for the Wiener process is studied herein, and asymptotic expansions for the optimal stopping boundaries are derived. These results lead to a simple index-type class of asymptotically optimal solutions to the classical discounted multi-armed bandit problem: given a discount factor 0<β <1 and k populations with densities from an exponential family, how should x1, x2,… be sampled sequentially from these populations to maximize the expected value of Ʃ∞1 βi−1xi, in ignorance of the parameters of the densities?