In this paper, we consider a single-server queue with stationary input, where each job joining the queue has an associated deadline. The deadline is a time constraint on job sojourn time and may be finite or infinite. If the job does not complete service before its deadline expires, it abandons the queue and the partial service it may have received up to that point is wasted. When the queue operates under a first-come-first served discipline, we establish conditions under which the actual workload process—that is, the work the server eventually processes—is unstable, weakly stable, and strongly stable. An interesting phenomenon observed is that in a nontrivial portion of the parameter space, the queue is weakly stable, but not strongly stable. We also indicate how our results apply to other nonidling service disciplines. We finally extend the results for a single node to acyclic (feed-forward) networks of queues with either per-queue or network-wide deadlines.

We consider a system with a finite state space subject to continuous-time Markovian deterioration while running that leads to failure. Failures are instantaneously detected. This system is submitted to sequential checking and preventive maintenance: up states are divided into ‘good’ and ‘degraded’ ones and the system is sequentially checked through perfect and instantaneous inspections until it is found in a degraded up state and stopped to allow maintenance (or until it fails). Time between inspections is random and is chosen at each inspection according to the current degradation degree of the system. Markov renewal equations fulfilled by the reliability of the maintained system are given and an exponential equivalent is derived for the reliability. We prove the existence of an asymptotic failure rate for the maintained system, which we are able to compute. Sufficient conditions are given for the preventive maintenance policy to improve the reliability and the asymptotic failure rate of the system. A numerical example illustrates our study.

The general coalescent process with simultaneous multiple mergers of ancestral lines was initially characterized by Möhle and Sagitov (2001) in terms of a sequence of measures defined on the finite-dimensional simplices. A more compact characterization of the general coalescent requiring a single probability measure Ξ defined on the infinite simplex Δ was suggested by Schweinsberg (2000). This paper presents a simple criterion of weak convergence to the Ξ-coalescent. In contrast to the earlier criterion of Möhle and Sagitov (2001) based on the moment conditions, the key condition here is expressed in terms of the joint distribution of the ranked offspring sizes. This criterion interprets a vector in Δ as the ranked fractions of the total population size assigned to sibling groups constituting a (rare) generation, where a merger might occur. An example of the general coalescent is developed on the basis of the Poisson–Dirichlet distribution. It suggests a simple algorithm of simulating the Kingman coalescent with occasional (simultaneous) multiple mergers.

We consider a discrete-time risk model which describes the evolution of the reserves of an insurance company at periodic dates fixed in advance. The amount of loss per unit of time corresponds to independent and identically distributed random variables with arithmetic distribution, and the process of the receipt of premiums is assumed to be deterministic, nonnegative but not uniform (instead of being constant and equal to 1 as in the standard, compound binomial model). For this model, we determine the probability of ruin (or of non-ruin), as well as the distribution of the severity of the eventual ruin, with some finite horizon. A compact and efficient exact expression is found by bringing up-to-date a generalised family of Appell polynomials. The method used is illustrated with some numerical examples.

We continue the study of the discrete-time risk model introduced by Picard et al. (2003). The cumulative loss process (St)t∊ℕ has independent and stationary increments, the increments per unit of time having nonnegative integer values with distribution {ai, i ∊ ℕ and mean ā. The premium receipt process (ck)k∊ℕ is deterministic, nonnegative and nonuniform; in addition, we assume it to be regular in order for there to exist a constant c > ā such that the deviation is bounded as the time t varies. We are interested in whether or not ruin occurs within a finite time. If T is the time of ruin, we obtain P(T = ∞) as the limit of P(T > t) as t → ∞, firstly in the particular case where c = 1/d for some positive d ∊ ℕ, and then in the general case for positive c under the condition that a0 > ½.

This paper addresses Paris barrier options, as introduced by G. Kentwell and J. Cornwall at Bankers Trust Australia in the mid-1990s, and their valuation, as developed by Chesnay, Jeanblanc-Picqué and Yor using the Laplace-transform approach. The notion of Paris barrier options is extended so that their valuation becomes possible at any point during their lifespan, and the pertinent Laplace transforms of Chesnay, Jeanblanc-Picqué and Yor are modified when necessary.

We introduce a new class of lifetime distributions exhibiting a notion of positive ageing, called the ℳ-class, which is strongly related to the well-known ℒ-class. It is shown that distributions in the ℳ-class cannot have an undesirable property recently observed in an example of an ℒ-class distribution by Klar (2002). Moreover, it is shown how these and related classes of life distributions can be characterized by expected remaining lifetimes after a family of random times, thus extending the notion of NBUE. We give examples of ℳ-class distributions by using simple sufficient conditions, and we derive reliability bounds for distributions in this class.

We consider polling systems with mixtures of exhaustive and gated service in which the server visits the queues periodically according to a general polling table. We derive exact expressions for the steady-state delay incurred at each of the queues under standard heavy-traffic scalings. The expressions require the solution of a set of only M—N linear equations, where M is the length of the polling table and N is the number of queues, but are otherwise explicit. The equations can even be expressed in closed form for several routeing schemes commonly used in practice, such as the star and elevator visit order, in a general parameter setting. The results reveal a number of asymptotic properties of the behavior of polling systems. In addition, the results lead to simple and fast approximations for the distributions and the moments of the delay in stable polling systems with periodic server routeing. Numerical results demonstrate that the approximations are highly accurate for medium and heavily loaded systems.

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.

We study the genealogical structure of a population with stochastically fluctuating size. If such fluctuations, after suitable rescaling, can be approximated by a nice continuous-time process, we prove weak convergence in the Skorokhod topology of the scaled ancestral process to a stochastic time change of Kingman's coalescent, the time change being given by an additive functional of the limiting backward size process.

We study the properties of sums of lower records from a distribution on [0,∞) which is either continuous, except possibly at the origin, or has support contained in the set of nonnegative integers. We find a necessary and sufficient condition for the partial sums of lower records to converge almost surely to a proper random variable. An explicit formula for the Laplace transform of the limit is derived. This limit is infinitely divisible and we show that all infinitely divisible random variables with continuous Lévy measure on [0,∞) originate as infinite sums of lower records.

This paper is a first study of two-person zero-sum games for denumerable continuous-time Markov chains determined by given transition rates, with an average payoff criterion. The transition rates are allowed to be unbounded, and the payoff rates may have neither upper nor lower bounds. In the spirit of the ‘drift and monotonicity’ conditions for continuous-time Markov processes, we give conditions on the controlled system's primitive data under which the existence of the value of the game and a pair of strong optimal stationary strategies is ensured by using the Shapley equations. Also, we present a ‘martingale characterization’ of a pair of strong optimal stationary strategies. Our results are illustrated with a birth-and-death game.

The formation of patterns from letters of a finite alphabet is considered. The strings of letters are generated by general discrete- and continuous-time models which embrace as particular cases all models considered in the literature. The letters of the alphabet are identified by the states of either discrete- or continuous-time semi-Markov processes. A new and unifying method is introduced for evaluation of the generating functions of both the intersite distance between occurrences of an arbitrary, but fixed, pattern and the waiting time until the first occurrence of that pattern. Our method also covers in a unified way relevant and important joint generating functions. Furthermore, our results lead to an easy and efficient implementation of the relevant evaluations.

Strings are generated by sequences of independent draws from a given alphabet. For a given pattern H of length l and an integer n ≥ l, our goal is to maximize the probability of stopping on the last appearance of the pattern H in a string of length n (if any), given that, if we choose to stop on an occurrence of H, we must do so right away. This contrasts with the goals of several other investigations on patterns in strings such as computing the expected occurrence time and the probability of finding exactly r patterns in a string of fixed length. Several motivations are given for our problem ranging from relatively simple best choice problems to more difficult stopping problems allowing for a variety of interesting applications. We solve this problem completely in the homogeneous case for uncorrelated patterns. However, several of these results extend immediately to the inhomogeneous case. In the homogeneous case, optimal success probabilities are shown to vary, depending on characteristics of the pattern, essentially between the value 1/e and a new asymptotic constant 0.619…. These results demonstrate a considerable difference between the true optimal success probability compared with what a first approximation by heuristic arguments would yield. It is interesting to see that the so-called odds algorithm which gives the optimal rule for l = 1 yields an excellent approximation of the optimal rule for any l. This is important for applications because the odds algorithm is very convenient. We finally give a detailed asymptotic analysis for the homogeneous case.

Consider a sequence of outcomes from Markov dependent two-state (success-failure) trials. In this paper, the exact distributions are derived for three longest-run statistics: the longest failure run, longest success run, and the maximum of the two. The method of finite Markov chain imbedding is used to obtain these exact distributions, and their bounds and large deviation approximation are also studied. Numerical comparisons among the exact distributions, bounds, and approximations are provided to illustrate the theoretical results. With some modifications, we show that the results can be easily extended to Markov dependent multistate trials.

The leaky bucket is a flow control mechanism that is designed to reduce the effect of the inevitable variability in the input stream into a node of a communication network. In this paper we study what happens when an input stream with heavy-tailed work sessions arrives to a server protected by such a leaky bucket. Heavy-tailed sessions produce long-range dependence in the input stream. Previous studies of single server fluid queues without flow control suggested that such long-range dependence can have a dramatic effect on the system performance. By concentrating on the expected time till overflow of a large finite buffer we show that leaky-bucket flow control does make the system overflow less often, but long-range dependence still makes its presence felt.

We analyse the performance of a material handling system consisting of two carousels and one picker. We derive expressions for the system throughput and picker utilization. We work out the throughput and picker utilization for two different pick-time distributions: deterministic, which might be a reasonable model when a robot is picking, and exponential, which might be a reasonable model when a person is picking.

In this paper, we investigate sooner and later waiting time problems for patterns S0 and S1 in multistate Markov dependent trials. The probability functions and the probability generating functions of the sooner and later waiting time random variables are studied. Further, the probability generating functions of the distributions of distances between successive occurrences of S0 and between successive occurrences of S0 and S1 and of the waiting time until the rth occurrence of S0 are also given.

Suppose that {Xs, 0 ≤ s ≤ T} is an m-dimensional geometric Brownian motion with drift, μ is a bounded positive Borel measure on [0,T], and ϕ : ℝm → [0,∞) is a (weighted) lq(ℝm)-norm, 1 ≤ q ≤ ∞. The purpose of this paper is to study the distribution and the moments of the random variable Y given by the Lp(μ)-norm, 1 ≤ p ≤ ∞, of the function s ↦ ϕ(Xs), 0 ≤ s ≤ T. By using various geometric inequalities in Wiener space, this paper gives upper and lower bounds for the distribution function of Y and proves that the distribution function is log-concave and absolutely continuous on every open subset of the distribution's support. Moreover, the paper derives tail probabilities, presents sharp moment inequalities, and shows that Y is indetermined by its moments. The paper will also discuss the so-called moment-matching method for the pricing of Asian-styled basket options.

We consider the following ordering for stochastic processes as introduced by Irle and Gani (2001). A process (Yt)t is said to be slower in level crossing than a process (Zt)t if it takes (Yt)t stochastically longer than (Zt)t to exceed any given level. In Irle and Gani (2001), this ordering was investigated for Markov chains in discrete time. Here these results are carried over to semi-Markov processes with particular attention to birth-and-death processes and also to Wiener processes.