When {Xn} is an irreducible, stationary, aperiodic Markov chain on the countable state space X = {i, j,…}, the study of long-range dependence of any square integrable functional {Yn} := {yXn} of the chain, for any real-valued function {yi: i ∈ X}, involves in an essential manner the functions Qijn = ∑r=1n(pijr − πj), where pijr = P{Xr = j | X0 = i} is the r-step transition probability for the chain and {πi: i ∈ X} = P{Xn = i} is the stationary distribution for {Xn}. The simplest functional arises when Yn is the indicator sequence for visits to some particular state i, Ini = I{Xn=i} say, in which case limsupn→∞n−1var(Y1 + ∙ ∙ ∙ + Yn) = limsupn→∞n−1 var(Ni(0, n]) = ∞ if and only if the generic return time random variable Tii for the chain to return to state i starting from i has infinite second moment (here, Ni(0, n] denotes the number of visits of Xr to state i in the time epochs {1,…,n}). This condition is equivalent to Qjin → ∞ for one (and then every) state j, or to E(Tjj2) = ∞ for one (and then every) state j, and when it holds, (Qijn / πj) / (Qkkn / πk) → 1 for n → ∞ for any triplet of states i, jk.

We give a simple and direct treatment of insensitivity in stochastic networks which is quite general and provides probabilistic insight into the phenomenon. In the case of multi-class networks, our results generalise those of Bonald and Proutière (2002), (2003).

Given two sequences of length n over a finite alphabet A of size |A| = d, the D2 statistic is the number of k-letter word matches between the two sequences. This statistic is used in bioinformatics for EST sequence database searches. Under the assumption of independent and identically distributed letters in the sequences, Lippert, Huang and Waterman (2002) raised questions about the asymptotic behavior of D2 when the alphabet is uniformly distributed. They expressed a concern that the commonly assumed normality may create errors in estimating significance. In this paper we answer those questions. Using Stein's method, we show that, for large enough k, the D2 statistic is approximately normal as n gets large. When k = 1, we prove that, for large enough d, the D2 statistic is approximately normal as n gets large. We also give a formula for the variance of D2 in the uniform case.

We investigate the probabilistic evolution of a near-critical bisexual branching process with mating depending on the number of couples in the population. We determine sufficient conditions which guarantee either the almost sure extinction of such a process or its survival with positive probability. We also establish some limiting results concerning the sequences of couples, females, and males, suitably normalized. In particular, gamma, normal, and degenerate distributions are proved to be limit laws. The results also hold for bisexual Bienaymé–Galton–Watson processes, and can be adapted to other classes of near-critical bisexual branching processes.

We develop an integration by parts technique for point processes, with application to the computation of sensitivities via Monte Carlo simulations in stochastic models with jumps. The method is applied to density estimation with respect to the Lebesgue measure via a modified kernel estimator which is less sensitive to variations of the bandwidth parameter than standard kernel estimators. This applies to random variables whose densities are not analytically known and requires the knowledge of the point process jump times.

A large dam model is the object of study of this paper. The parameters Llower and Lupper define its lower and upper levels, L = Lupper - Llower is large, and if the current level of water is between these bounds, the dam is assumed to be in a normal state. Passage across one or other of the levels leads to damage. Let J1 and J2 denote the damage costs of crossing the lower and, respectively, the upper levels. It is assumed that the input stream of water is described by a Poisson process, while the output stream is state dependent. Let Lt denote the dam level at time t, and let p1 = limt→∞P{Lt = Llower} and p2 = limt→∞P{Lt > Lupper} exist. The long-run average cost, J = p1J1 + p2J2, is a performance measure. The aim of the paper is to choose the parameter controlling the output stream so as to minimize J.

We consider ageing properties of a general repair process. Under certain assumptions we prove that the expectation of an age at the beginning of the next cycle in this process is smaller than the initial age of the previous cycle. Using this reasoning, we show that the sequence of random ages at the start (end) of consecutive cycles is stochastically increasing and is converging to a limiting distribution. We discuss possible applications and interpretations of our results.

Expressions for the joint distribution of the longest and second longest excursions as well as the marginal distributions of the three longest excursions in the Brownian bridge are obtained. The method, which primarily makes use of the weak convergence of the random walk to the Brownian motion, principally gives the possibility to obtain any desired joint or marginal distribution. Numerical illustrations of the results are also given.

In a sequence of independent Bernoulli trials the probability for success in the kth trial is pk, k = 1, 2, …. The number of strings with a given number of failures between two subsequent successes is studied. Explicit expressions for distributions and moments are obtained for the case in which pk = a/(a + b + k − 1), a > 0, b ≥ 0. Also, the limit behaviour of the longest failure string in the first n trials is considered. For b = 0, the strings correspond to cycles in random permutations.

We analyze the unit-demand Euclidean vehicle routeing problem, where n customers are modeled as independent, identically distributed uniform points and have unit demand. We show new lower bounds on the optimal cost for the metric vehicle routeing problem and analyze them in this setting. We prove that there exists a constant ĉ > 0 such that the iterated tour partitioning heuristic given by Haimovich and Rinnooy Kan (1985) is a (2 - ĉ)-approximation algorithm with probability arbitrarily close to 1 as the number of customers goes to ∞. It has been a longstanding open problem as to whether one can improve upon the factor of 2 given by Haimovich and Rinnooy Kan. We also generalize this, and previous results, to the multidepot case.

Aven and Jensen (1999) proposed an approximation to the downtime distribution for arbitrary coherent systems with binary and independent repairable components, where each component follows an alternating renewal process. The approximation is based on a mixture of the duration distributions of the cut sets in the system. We extend this approach to coherent systems composed by multistate independent components, where every component follows a semi-Markov process and where we introduce the concept of a minimal cut set in the multistate setting. We test our proposal on a simple power demand-generation system, by comparing the analytic approximation with simulation results, and we find it is accurate when the system is highly available.

Computer analysis of biological sequences often detects deviations from a random model. In the usual model, sequence letters are chosen independently, according to some fixed distribution over the relevant alphabet. Real biological sequences often contain simple repeats, however, which can be broadly characterized as multiple contiguous copies (usually inexact) of a specific word. This paper quantifies inexact simple repeats as local sums in a Markov additive process (MAP). The maximum of the local sums has an asymptotic distribution with two parameters (λ and k), which are given by general MAP formulas. The general MAP formulas are usually computationally intractable, but an essential simplification in the case of repeats permits λ and k to be computed from matrices whose dimension equals the size of the relevant alphabet. The simplification applies to some MAPs where the summand distributions do not depend on consecutive pairs of Markov states as usual, but on pairs with a fixed time-lag larger than one.

In this paper we are interested in a nonlinear parabolic evolution equation occurring in rheology. We give a probabilistic interpretation to this equation by associating a nonlinear martingale problem with it. We prove the existence of a unique solution, P, to this martingale problem. For any t, the time marginal of P at time t admits a density ρ(t,x) with respect to the Lebesgue measure, where the function ρ is the unique weak solution to the evolution equation in a well-chosen energy space. Next we introduce a simulable system of n interacting particles and prove that the empirical measure of this system converges to P as n tends to ∞. This propagation-of-chaos result ensures that the solution to the equation of interest can be approximated using a Monte Carlo method. Finally, we illustrate the convergence in some numerical experiments.

We develop a conservation law for a multi-class GI/GI/1 queue operating under a general work-conserving scheduling discipline. For single-class single-server queues, conservation laws have been obtained for both nonanticipating and anticipating disciplines with general service time distributions. For multi-class single-server queues, conservation laws have been obtained for (i) nonanticipating disciplines with exponential service time distributions and (ii) nonpreemptive nonanticipating disciplines with general service time distributions. The unifying conservation law we develop generalizes already existing conservation laws. In addition, it covers popular nonanticipating multi-class time-sharing disciplines such as discriminatory processor sharing (DPS) and generalized processor sharing (GPS) with general service time distributions. As an application, we show that the unifying conservation law can be used to compare the expected unconditional response time under two scheduling disciplines.

We present an elegant uniqueness criterion for the weighted Markov branching process in the potentially explosive case.

The Vardi casino with parameter 0 < c < 1 consists of infinitely many tables indexed by their odds, each of which returns the same (negative) expected winnings -c per dollar. A gambler seeks to maximize the probability of reaching a fixed fortune by gambling repeatedly with suitably chosen stakes and tables (odds). The optimal strategy is derived explicitly subject to the constraint that the gambler is allowed to play only a given finite number of times. Some properties of the optimal strategy are also discussed.

A simple derivation of the explicit form of the transition density of a planar random motion at finite speed, based on some specific properties of the wave propagation on the plane R2, is given.

The analysis of stochastic loss networks has long been of interest in computer and communications networks and is becoming important in the areas of service and information systems. In traditional settings computing the well-known Erlang formula for blocking probabilities in these systems becomes intractable for larger resource capacities. Using compound point processes to capture stochastic variability in the request process, we generalize existing models in this framework and derive simple asymptotic expressions for the blocking probabilities. In addition, we extend our model to incorporate reserving resources in advance. Although asymptotic, our experiments show an excellent match between derived formulae and simulation results even for relatively small resource capacities and relatively large values of the blocking probabilities.

In this paper we investigate a class of N-person nonconstant sum red-and-black games with bet-dependent win probability functions. We assume that N players and a gambling house are engaged in a game played in stages, where the player's probability of winning at each stage is a function f of the ratio of his bet to the sum of all the players' bets. However, at each stage of the game there is a positive probability that all the players lose and the gambling house wins their bets. We prove that if the win probability function is super-additive and it satisfies f(s)f(t)≤f(st), then a bold strategy is optimal for all players.