We continue the study of the asymptotic behaviour of a random walk when it exits from a symmetric region of the form {(x, n): |x| ≤ rnb} as r → ∞ which was begun in Part I of this work. In contrast to that paper, we are interested in the case where the probability of exiting at the upper boundary tends to 1. In this scenario we treat the case where the power b lies in the interval [0, 1), and we establish necessary and sufficient conditions for the overshoot to be relatively stable in probability (except for the case ), and for the pth moment of the overshoot to be O(rq) as r → ∞.

We develop a new, self-contained proof that the expected number of generations required for gene allele fixation or extinction in a population of size n is O(n) under general assumptions. The proof relies on a discrete Markov chain analysis. We further develop an algorithm to compute expected fixation or extinction time to any desired precision. Our proofs establish O(nH(p)) as the expected time for gene allele fixation or extinction for the Fisher-Wright problem, where the gene occurs with initial frequency p and H(p) is the entropy function. Under a weaker hypothesis on the variance, the expected time is O(n(p(1-p))1/2) for fixation or extinction. Thus, the expected-time bound of O(n) for fixation or extinction holds in a wide range of situations. In the multi-allele case, the expected time for allele fixation or extinction in a population of size n with n distinct alleles is shown to be O(n). From this, a new proof is given of a coalescence theorem about the mean time to the most recent common ancestor (MRCA), which applies to a broad range of reproduction models satisfying our mean and weak variation conditions.

We study estimation of the tail-decay parameter of the marginal distribution corresponding to a discrete-time, real-valued stationary stochastic process. Assuming that the underlying process is short-range dependent, we investigate properties of estimators of the tail-decay parameter which are based on the maximal extreme value of the process observed over a sampled time interval. These estimators only assume that the tail of the marginal distribution is roughly exponential, plus some modest ‘mixing’ conditions. Consistency properties of these estimators are established, as well as minimax convergence rates. We also provide some discussion on estimating the pre-exponent, when a more refined tail asymptotic is assumed. Properties of a certain moving-average variant of the extremal-based estimator are investigated as well. In passing, we also characterize the precise dependence (mixing) assumptions that support almost-sure limit theory for normalized extreme values and related first-passage times in stationary sequences.

We study the parametric perturbation of Markov chains with denumerable state spaces. We consider both regular and singular perturbations. By the latter we mean that transition probabilities of a Markov chain, with several ergodic classes, are perturbed such that (rare) transitions among the different ergodic classes of the unperturbed chain are allowed. Singularly perturbed Markov chains have been studied in the literature under more restrictive assumptions such as strong recurrence ergodicity or Doeblin conditions. We relax these conditions so that our results can be applied to queueing models (where the conditions mentioned above typically fail to hold). Assuming ν-geometric ergodicity, we are able to explicitly express the steady-state distribution of the perturbed Markov chain as a Taylor series in the perturbation parameter. We apply our results to quasi-birth-and-death processes and queueing models.

This paper considers a Markovian bulk-arriving queue modified to allow both mass arrivals when the queue is idle and mass departures which allow for the possibility of removing the entire workload. Properties of queues which terminate when the server becomes idle are developed first, since these play a key role in later developments. Results for the case of mass arrivals, but no mass annihilation, are then constructed with specific attention being paid to recurrence properties, equilibrium queue-size structure, and waiting-time distribution. A closed-form expression for the expected queue size and its Laplace transform are also established. All of these results are then generalised to allow for the removal of the entire workload, with closed-form expressions being developed for the equilibrium size and waiting-time distributions.

Normed ergodicity is a type of strong ergodicity for which convergence of the nth step transition operator to the stationary operator holds in the operator norm. We derive a new characterization of normed ergodicity and we clarify its relation with exponential ergodicity. The existence of a Lyapunov function together with two conditions on the uniform integrability of the increments of the Markov chain is shown to be a sufficient condition for normed ergodicity. Conversely, the sufficient conditions are also almost necessary.

The basic queueing system considered in this paper is the M/G/1 processor-sharing queue with or without impatience and with finite or infinite capacity. Under some mild assumptions, a criterion for the validity of the reduced-service-rate approximation is established when service times are heavy tailed. This result is applied to various models based on M/G/1 processor-sharing queues.

We study a fork-join processing network in which jobs arrive according to a Poisson process and each job splits into m tasks, which are simultaneously assigned to m nodes that operate like M/M/s queueing systems. When all of its tasks are finished, the job is completed. The main result is a closed-form formula for approximating the distribution of the network's response time (the time to complete a job) in equilibrium. We also present an analogous approximation for the distribution of the equilibrium queue length (the number of jobs in the system), when each node has one server. Kolmogorov-Smirnov statistical tests show that these formulae are good fits for the distributions obtained from simulations.

Let (φ(Xn))n be a function of a finite-state Markov chain (Xn)n. In this article, we investigate the conditions under which the random variables φ(n) have the same distribution as Yn (for every n), where (Yn)n is a Markov chain with fixed transition probability matrix. In other words, for a deterministic function φ, we investigate the conditions under which (Xn)n is weakly lumpable for the state vector. We show that the set of all probability distributions of X0, such that (Xn)n is weakly lumpable for the state vector, can be finitely generated. The connections between our definition of lumpability and the usual one (i.e. as the proportional dynamics property) are discussed.

The Kesten-Stigum theorem for the one-type Galton-Watson process gives necessary and sufficient conditions for mean convergence of the martingale formed by the population size normed by its expectation. Here, the approach to this theorem pioneered by Lyons, Pemantle and Peres (1995) is extended to certain kinds of martingales defined for Galton-Watson processes with a general type space. Many examples satisfy stochastic domination conditions on the offspring distributions and suitable domination conditions combine nicely with general conditions for mean convergence to produce moment conditions, like the X log X condition of the Kesten-Stigum theorem. A general treatment of this phenomenon is given. The application of the approach to various branching processes is indicated. However, the main reason for developing the theory is to obtain martingale convergence results in a branching random walk that do not seem readily accessible with other techniques. These results, which are natural extensions of known results for martingales associated with binary branching Brownian motion, form the main application.

We consider a failure-prone system operating in continuous time. Condition monitoring is conducted at discrete time epochs. The state of the system is assumed to evolve as a continuous-time Markov process with a finite state space. The observation process with continuous-range values is stochastically related to the state process, which, except for the failure state, is unobservable. Combining the failure information and the condition monitoring information, we derive a general recursive filter, and, as special cases, we obtain recursive formulae for the state estimation and other quantities of interest. Updated parameter estimates are obtained using the expectation-maximization (EM) algorithm. Some practical prediction problems are discussed and finally an illustrative example is given using a real dataset.

In this paper we derive bounds on the conductance and hence on the spectral gap of a Metropolis algorithm with a monotone, log-concave target density on an interval of ℝ. We show that the minimal conductance set has measure ½ and we use this characterization to bound the conductance in terms of the conductance of the algorithm restricted to a smaller domain. Whereas previous work on conductance has resulted in good bounds for Markov chains on bounded domains, this is the first conductance bound applicable to unbounded domains. We then show how this result can be combined with the state-decomposition theorem of Madras and Randall (2002) to bound the spectral gap of Metropolis algorithms with target distributions with monotone, log-concave tails on ℝ.

This paper studies the subexponential properties of the stationary workload, actual waiting time and sojourn time distributions in work-conserving single-server queues when the equilibrium residual service time distribution is subexponential. This kind of problem has been previously investigated in various queueing and insurance risk settings. For example, it has been shown that, when the queue has a Markovian arrival stream (MAS) input governed by a finite-state Markov chain, it has such subexponential properties. However, though MASs can approximate any stationary marked point process, it is known that the corresponding subexponential results fail in the general stationary framework. In this paper, we consider the model with a general stationary input and show the subexponential properties under some additional assumptions. Our assumptions are so general that the MAS governed by a finite-state Markov chain inherently possesses them. The approach used here is the Palm-martingale calculus, that is, the connection between the notion of Palm probability and that of stochastic intensity. The proof is essentially an extension of the M/GI/1 case to cover ‘Poisson-like’ arrival processes such as Markovian ones, where the stochastic intensity is admitted.

We consider a single-type supercritical or near-critical size-dependent branching process {Nn}n such that the offspring mean converges to a limit m ≥ 1 with a rate of convergence of order as the population size Nn grows to ∞ and the variance may vary at the rate where −1 ≤ β < 1. The offspring mean m(N) = m + μN-α + o(N-α) depends on an unknown parameter θ0 belonging either to the asymptotic model (θ0 = m) or to the transient model (θ0 = μ). We estimate θ0 on the nonextinction set from the observations {Nh,…,Nn} by using the conditional least-squares method weighted by (where γ ∈ ℝ) in the approximate model mθ,ν̂n(·), where ν̂n is any estimation of the parameter of the nuisance part (O(N-α) if θ0 = m and o(N-α) if θ0 = μ). We study the strong consistency of the estimator of θ0 as γ varies, with either h or n - h remaining constant as n → ∞. We use either a minimum-contrast method or a Taylor approximation of the first derivative of the contrast. The main condition for obtaining strong consistency concerns the asymptotic behavior of the process. We also give the asymptotic distribution of the estimator by using a central-limit theorem for random sums and we show that the best rate of convergence is attained when γ = 1 + β.

We consider the asymptotic behaviour of the stationary tail probabilities in the discrete-time GI/G/1-type queue with countable background state space. These probabilities are presented in matrix form with respect to the background state space, and shown to be the solution of a Markov renewal equation. Using this fact, we consider their decay rates. Applying the Markov renewal theorem, it is shown that certain reasonable conditions lead to the geometric decay of the tail probabilities as the level goes to infinity. We exemplify this result using a discrete-time priority queue with a single server and two types of customer.

We derive results that show the impact of aggregation in a queueing network. Our model consists of a two-stage queueing system where the first (upstream) queue serves many flows, of which a certain subset arrive at the second (downstream) queue. The downstream queue experiences arbitrary interfering traffic. In this setup, we prove that, as the number of flows being aggregated in the upstream queue increases, the overflow probability of the downstream queue converges uniformly in the buffer level to the overflow probability of a single queueing system obtained by simply removing the upstream queue in the original two-stage queueing system. We also provide the speed of convergence and show that it is at least exponentially fast. We then extend our results to non-i.i.d. traffic arrivals.

A new structure with the special property that instantaneous resurrection and mass disaster are imposed on an ordinary birth-death process is considered. Under the condition that the underlying birth-death process is exit or bilateral, we are able to give easily checked existence criteria for such Markov processes. A very simple uniqueness criterion is also established. All honest processes are explicitly constructed. Ergodicity properties for these processes are investigated. Surprisingly, it can be proved that all the honest processes are not only recurrent but also ergodic without imposing any extra conditions. Equilibrium distributions are then established. Symmetry and reversibility of such processes are also investigated. Several examples are provided to illustrate our results.

We consider a processing system, composed of several parallel queues and a processor, which operates in a time-varying environment that fluctuates between various states or modes. The service rate at each queue depends on the processor bandwidth allocated to it, as well as the environment mode. Each queue is driven by a job traffic flow, which may also depend on the environment mode. Dynamic processor scheduling policies are investigated for maximizing the system throughput, by adapting to queue backlogs and the environment mode. We show that allocating the processor bandwidth to the queues, so as to maximize the projection of the service rate vector onto a linear function of the workload vector, can keep the system stable under the maximum possible traffic load. The analysis of the system dynamics is first done under very general assumptions, addressing rate stability and flow conservation on individual traffic and environment evolution traces. The connection with stochastic stability is later discussed for stationary and ergodic traffic and environment processes. Various extensions to feed-forward networks of such nodes, the multi-processor case, etc., are also discussed. The approach advances the methodology of trace-based modelling of queueing structures. Applications of the model include bandwidth allocation in wireless channels with fluctuating interference and allocation of switching bandwidth to traffic flows in communication networks with fluctuating congestion levels.

We study the stochastic comparison of interacting particle systems where the state space of each particle is a finite set endowed with a partial order, and several particles may change their value at a time. For these processes we give local conditions, on the rates of change, that assure their comparability. We also analyze the case where one of the processes does not have any changes that involve several particles, and obtain necessary and sufficient conditions for their comparability. The proofs are based on the explicit construction of an order-preserving Markovian coupling. We show the applicability of our results by studying the stochastic comparison of infinite-station Jackson networks and batch-arrival, batch-service, and assemble-transfer queueing networks.

The issue of ‘fairness’ is raised frequently in the context of evaluating queueing policies, notably in relation to telecommunications and computer systems where it may be of no lesser importance than the conventional measures of performance. Comparisons of the fairness of various systems and policies are often awkward due to lack of generally accepted definitions and measures for this important property. The purpose of this work is to propose possible fairness measures enabling us to quantitatively measure and compare the level of fairness associated with G/G/R queueing systems. We define and discuss order (of service) fairness and use an axiomatic approach for developing a measure for it in the G/D/1 case. The measure obtained for the G/D/1 system is then generalized and applied to the G/G/R class of systems. A practical implication of this work is that, for a wide class of service disciplines, the variance of the waiting time can be used as a yardstick for comparing fairness levels.