We investigate in this paper the stability of non-stationary stochastic processes, arising typically in applications of control. The setting is known as stochastic recursive sequences, which allows us to construct on one probability space stochastic processes that correspond to different initial states and even different control policies. It does not require any Markovian assumptions. A natural criterion for stability for such processes is that the influence of the initial state disappears after some finite time; in other words, starting from different initial states, the process will couple after some finite time to the same limiting (not necessarily stationary nor ergodic) stochastic process. We investigate this as well as other types of coupling, and present conditions for them to occur uniformly in some class of control policies. We then use the coupling results to establish new theoretical aspects in the theory of non-Markovian control.

The gating mechanism of a single ion channel is usually modelled by a continuous-time Markov chain with a finite state space. The state space is partitioned into two classes, termed ‘open’ and ‘closed’, and it is possible to observe only which class the process is in. In many experiments channel openings occur in bursts. This can be modelled by partitioning the closed states further into ‘short-lived’ and ‘long-lived’ closed states, and defining a burst of openings to be a succession of open sojourns separated by closed sojourns that are entirely within the short-lived closed states. There is also evidence that bursts of openings are themselves grouped together into clusters. This clustering of bursts can be described by the ratio of the variance Var (N(t)) to the mean [N(t)] of the number of bursts of openings commencing in (0, t]. In this paper two methods of determining Var (N(t))/[N(t)] and limt→∝ Var (N(t))/[N(t)] are developed, the first via an embedded Markov renewal process and the second via an augmented continuous-time Markov chain. The theory is illustrated by a numerical study of a molecular stochastic model of the nicotinic acetylcholine receptor. Extensions to semi-Markov models of ion channel gating and the incorporation of time interval omission are briefly discussed.

We consider a risk process with stochastic interest rate, and show that the probability of eventual ruin and the Laplace transform of the time of ruin can be found by solving certain boundary value problems involving integro-differential equations. These equations are then solved for a number of special cases. We also show that a sequence of such processes converges weakly towards a diffusion process, and analyze the above-mentioned ruin quantities for the limit process in some detail.

The asymptotic behaviour of the recursion is investigated; Yk describes the number of comparisons which have to be carried out to merge two sorted subsequences of length 2k–1 and Mk can be interpreted as the number of comparisons of ‘Simultaneous Merge–Sort'. The challenging problem in the analysis of the above recursion lies in the fact that it contains a maximum as well as a sum. This demands different ideal properties for the metric in the contraction method. By use of the weighted Kolmogorov metric it is shown that an exponential normalization provides the recursion's convergence. Furthermore, one can show that any sequence of linear normalizations of Mk must converge towards a constant if it converges in distribution at all.

An important model in communications is the stochastic FM signal st = A cos , where the message process {mt} is a stochastic process. In this paper, we investigate the linear models and limit distributions of FM signals. Firstly, we show that this non-linear model in the frequency domain can be converted to an ARMA (2, q + 1) model in the time domain when {mt} is a Gaussian MA (q) sequence. The spectral density of {St} can then be solved easily for MA message processes. Also, an error bound is given for an ARMA approximation for more general message processes. Secondly, we show that {St} is asymptotically strictly stationary if {mt} is a Markov chain satisfying a certain condition on its transition kernel. Also, we find the limit distribution of st for some message processes {mt}. These results show that a joint method of probability theory, linear and non-linear time series analysis can yield fruitful results. They also have significance for FM modulation and demodulation in communications.

This paper studies the expected average cost control problem for discrete-time Markov decision processes with denumerably infinite state spaces. A sequence of finite state space truncations is defined such that the average costs and average optimal policies in the sequence converge to the optimal average cost and an optimal policy in the original process. The theory is illustrated with several examples from the control of discrete-time queueing systems. Numerical results are discussed.

We consider stochastic orders of the following type. Let be a class of functions and let P and Q be probability measures. Then define , if ∫ ⨍ d P ≦ ∫ ⨍ d Q for all f in . Marshall (1991) posed the problem of characterizing the maximal cone of functions generating such an ordering. We solve this problem by using methods from functional analysis. Another purpose of this paper is to derive properties of such integral stochastic orders from conditions satisfied by the generating class of functions. The results are illustrated by several examples. Moreover, we show that the likelihood ratio order is closed with respect to weak convergence, though it is not generated by integrals.

Let (X, S) = {(Xn, Sn); n ≧0} be a Markov random walk with finite state space. For a ≦ 0 < b define the stopping times τ= inf {n:Sn > b} and T= inf{n:Sn∉(a, b)}. The diffusion approximations of a one-barrier probability P {τ < ∝ | Xo= i}, and a two-barrier probability P{ST ≧b | Xo = i} with correction terms are derived. Furthermore, to approximate the above ruin probabilities, the limiting distributions of overshoot for a driftless Markov random walk are involved.

We consider probability metrics of the following type: for a class of functions and probability measures P, Q we define A unified study of such integral probability metrics is given. We characterize the maximal class of functions that generates such a metric. Further, we show how some interesting properties of these probability metrics arise directly from conditions on the generating class of functions. The results are illustrated by several examples, including the Kolmogorov metric, the Dudley metric and the stop-loss metric.

We consider a problem proposed by S. Alpern (European Journal of Operational Research (1997)) of how two players can optimally rendezvous while at the same time evading an enemy searcher. This problem can be modelled as a two-person, zero-sum game between the rendezvous team R (with agents R1, R2) and the searcher S. This paper gives the first solution to such a rendezvous-evasion game by considering a version that is discrete in time and space, as in the pure rendezvous problem of Anderson and Weber (Journal of Applied Probability28, pp. 839–851). R1,R2 and S start at different locations among the n identical locations where there is no common labelling and at each integer time they may rellocate to any one of the n locations. When some location is occupied by more than one player, the game ends. If S is at this location, S (maximizer) wins and the payoff is 1; otherwise R(minimizer) wins and the payoff is 0. The value of the game is the probability that Swins under optimal play. We assume that R1 and R2 can jointly randomize their strategies. When n equals 3, the value of the game is . We also prove that the value of the game is bounded above by asymptotically. If, in addition, the players share a common notion of a directed cycle containing all the nlocations (while still able to move between any two locations), the value of the game is ((1 – 2/n)n–1 + l)/2. Finally, we prove that with this extra information, R can secure a strictly lower value for all n.

We consider extreme value theory for a class of stationary Markov chains with values in ℝd. The asymptotic distribution of Mn, the vector of componentwise maxima, is determined under mild dependence restrictions and suitable assumptions on the marginal distribution and the transition probabilities of the chain. This is achieved through computation of a multivariate extremal index of the sequence, extending results of Smith [26] and Perfekt [21] to a multivariate setting. As a by-product, we obtain results on extremes of higher-order, real-valued Markov chains. The results are applied to a frequently studied random difference equation.

It is shown that totally positive order 2 (TP2) properties of the infinitesimal generator of a continuous-time Markov chain with totally ordered state space carry over to the chain's transition distribution function. For chains with such properties, failure rate characteristics of the first passage times are established. For Markov chains with partially ordered state space, it is shown that the first passage times have an IFR distribution under a multivariate total positivity condition on the transition function.

In this paper we study a new kind of option, called hereinafter a Parisian barrier option. This option is the following variant of the so-called barrier option: a down-and-out barrier option becomes worthless as soon as a barrier is reached, whereas a down-and-out Parisian barrier option is lost by the owner if the underlying asset reaches a prespecified level and remains constantly below this level for a time interval longer than a fixed number, called the window. Properties of durations of Brownian excursions play an essential role. We also study another kind of option, called here a cumulative Parisian option, which becomes worthless if the total time spent below a certain level is too long.

We consider the recursive equation x(n + 1)= A(n)⊗x(n), where x(n + 1) and x(n) are ℝk-valued vectors and A(n) is an irreducible random matrix of size k × k. The matrix-vector multiplication in the (max, +) algebra is defined by (A(n)⊗x(n))= maxj (Aij (n) + xj(n)). This type of equation can be used to represent the evolution of stochastic event graphs which include cyclic Jackson networks, some manufacturing models and models with general blocking (such as Kanban). Let us assume that the sequence {A(n), n ∈ ℕ} is i.i.d. or, more generally, stationary and ergodic. The main result of the paper states that the system couples in finite time with a unique stationary regime if and only if there exists a set of matrices such that and the matrices have a unique periodic regime.

Dependability evaluation is a basic component in the assessment of the quality of repairable systems. We develop a model taking simultaneously into account the occurrence of failures and repairs, together with the observation of user-defined success events. The model is built from a Markovian description of the behavior of the system. We obtain the distribution function of the joint number of observed failures and of delivered services on a fixed mission period of the system. In particular, the marginal distribution of the number of failures can be directly related to the distribution of the Markovian arrival process extensively used in queueing theory. We give both the analytical expressions of the considered distributions and the algorithmic solutions for their evaluation. An asymptotic analysis is also provided.

For Markov chains of M/G/1 type that are not skip-free to the left, the corresponding G matrix is shown to have special structure and be determined by its first block row. An algorithm that takes advantage of this structure is developed for computing G. For non-skip-free M/G/1 type Markov chains, the algorithm significantly reduces the computational complexity of calculating the G matrix, when compared with reblocking to a system that is skip-free to the left and then applying usual iteration schemes to find G. A similar algorithm to calculate the R matrix for G/M/1 type Markov chains that are not skip-free to the right is also described.

In a recent paper [16], one of us identified all of the quasi-stationary distributions for a non-explosive, evanescent birth-death process for which absorption is certain, and established conditions for the existence of the corresponding limiting conditional distributions. Our purpose is to extend these results in a number of directions. We shall consider separately two cases depending on whether or not the process is evanescent. In the former case we shall relax the condition that absorption is certain. Furthermore, we shall allow for the possibility that the minimal process might be explosive, so that the transition rates alone will not necessarily determine the birth-death process uniquely. Although we shall be concerned mainly with the minimal process, our most general results hold for any birth-death process whose transition probabilities satisfy both the backward and the forward Kolmogorov differential equations.

Recently, Asmussen and Koole (Journal of Applied Probability30, pp. 365–372) showed that any discrete or continuous time marked point process can be approximated by a sequence of arrival streams modulated by finite state continuous time Markov chains. If the original process is customer (time) stationary then so are the approximating processes. Also, the moments in the stationary case converge. For discrete marked point processes we construct a sequence of discrete processes modulated by discrete time finite state Markov chains. All the above features of approximating sequences of Asmussen and Koole continue to hold. For discrete arrival sequences (to a queue) which are modulated by a countable state Markov chain we form a different sequence of approximating arrival streams by which, unlike in the Asmussen and Koole case, even the stationary moments of waiting times can be approximated. Explicit constructions for the output process of a queue and the total input process of a discrete time Jackson network with these characteristics are obtained.

For autoregressive time series with positive innovations which either have heavy right or left tails, linear programming parameter estimates of the autoregressive coefficients have good rates of convergence. However, the asymptotic distribution of the estimators depends heavily on the distribution of the process and thus cannot be used for inference. A bootstrap procedure circumvents this difficulty. We verify the validity of the bootstrap and also give some general comments on the bootstrapping of heavy tailed phenomena.

In the series system (competing risks) set-up the observed data are generally accepted as the lifetime (T) and the identifier (δ) of the component causing the failure of the system. Peterson (1976) has provided bounds for the joint survival function of the component lifetimes in terms of the joint distribution of (T, δ). In the case of more complex coherent systems, there are various schemes of observation in the literature. In this paper we provide bounds for the joint and marginal survival functions of the component lifetimes in terms of the joint distribution of the data as obtained under existing and new schemes of observation. We also tackle the reverse problem of obtaining bounds for the joint distributions of the data for given marginal distributions of the component lifetimes and the distribution of the system lifetimes.