We study an optimal admission of arriving customers to a Markovian finite-capacity queue, e.g. an M/M/c/N queue, with several customer types. The system managers are paid for serving customers and penalized for rejecting them. The rewards and penalties depend on customer type. The goal is to maximize the average rewards per unit time subject to the constraint on the average penalties per unit time. We provide a solution to this problem based on Lagrangian optimization. For a feasible problem, we show the existence of a randomized trunk reservation optimal policy with the acceptance thresholds for different customer types ordered according to a linear combination of the service rewards and rejection costs. In addition, we prove that any 1-randomized stationary optimal policy has this structure. In particular, we establish the structure of an optimal policy that maximizes the average rewards per unit time subject to the constraint on the blocking probability of either one of the customer types or a group of customer types pooled together.

We propose a simple and efficient scheme for ranking all teams in a tournament where matches can be played simultaneously. We show that the distribution of the number of rounds of the proposed scheme can be derived using lattice path counting techniques used in ballot problems. We also discuss our method from the viewpoint of parallel sorting algorithms.

We propose a simple model for interaction between gene candidates in the two strands of bacterial DNA (deoxyribonucleic acid). Our model assumes that ‘final’ genes appear in one of the two strands, that they do not overlap (in bacteria there is only a small percentage of overlap), and that the final genes maximize the occupancy rate, which is defined to be the proportion of the genome occupied by coding zones. We are more concerned with describing the organization and distribution of genes in bacterial DNA than with the very hard problem of identifying genes. To this end, an algorithm for selecting the final genes according to the previously outlined maximization criterion is proposed. We study the graphical and probabilistic properties of the model resulting from applying the maximization procedure to a Markovian representation of the genic and intergenic zones within the DNA strands, develop theoretical bounds on the occupancy rate (which, in our view, is a rather intractable quantity), and use the model to compute quantities of relevance to the Escherichia coli genome and compare these to annotation data. Although this work focuses on genomic modelling, we point out that the proposed model is not restricted to applications in this setting. It also serves to model other resource allocation problems.

We consider the stability of the longest-queue-first scheduling policy (LQF), a natural and low-complexity scheduling policy, for a generalized switch model. Unlike that of common scheduling policies, the stability of LQF depends on the variance of the arrival processes in addition to their average intensities. We identify new sufficient conditions for LQF to be throughput optimal for independent, identically distributed arrival processes. Deterministic fluid analogs, proved to be powerful in the analysis of stability in queueing networks, do not adequately characterize the stability of LQF. We combine properties of diffusion-scaled sample path functionals and local fluid limits into a sharper characterization of stability.

We consider growth-collapse processes (GCPs) that grow linearly between random partial collapse times, at which they jump down according to some distribution depending on their current level. The jump occurrences are governed by a state-dependent rate function r(x). We deal with the stationary distribution of such a GCP, (Xt)t≥0, and the distributions of the hitting times Ta = inf{t ≥ 0 : Xt = a}, a > 0. After presenting the general theory of these GCPs, several important special cases are studied. We also take a brief look at the Markov-modulated case. In particular, we present a method of computing the distribution of min[Ta, σ] in this case (where σ is the time of the first jump), and apply it to determine the long-run average cost of running a certain Markov-modulated disaster-ridden system.

Consider the random variable Ln defined as the length of a longest common subsequence of two random strings of length n and whose random characters are independent and identically distributed over a finite alphabet. Chvátal and Sankoff showed that the limit γ=limn→∞E[Ln]/n is well defined. The exact value of this constant is not known, but various methods for the computation of upper and lower bounds have been discussed in the literature. Even so, high-precision bounds are hard to come by. In this paper we discuss how large deviation theory can be used to derive a consistent sequence of upper bounds, (qm)m∈ℕ, on γ, and how Monte Carlo simulation can be used in theory to compute estimates, q̂m, of the qm such that, for given Ξ > 0 and Λ ∈ (0,1), we have P[γ < q̂ < γ + Ξ] ≥ Λ. In other words, with high probability the result is an upper bound that approximates γ to high precision. We establish O((1 − Λ)−1Ξ−(4+ε)) as a theoretical upper bound on the complexity of computing q̂m to the given level of accuracy and confidence. Finally, we discuss a practical heuristic based on our theoretical approach and discuss its empirical behavior.

We consider the class of level-independent quasi-birth-and-death (QBD) processes that have countably many phases and generator matrices with tridiagonal blocks that are themselves tridiagonal and phase independent. We derive simple conditions for possible decay rates of the stationary distribution of the ‘level’ process. It may be possible to obtain decay rates satisfying these conditions by varying only the transition structure at level 0. Our results generalize those of Kroese, Scheinhardt, and Taylor, who studied in detail a particular example, the tandem Jackson network, from the class of QBD processes studied here. The conditions derived here are applied to three practical examples.

We consider an epidemic model where the spread of the epidemic can be described by a discrete-time Galton-Watson branching process. Between times n and n + 1, any infected individual is detected with unknown probability π and the numbers of these detected individuals are the only observations we have. Detected individuals produce a reduced number of offspring in the time interval of detection, and no offspring at all thereafter. If only the generation sizes of a Galton-Watson process are observed, it is known that one can only estimate the first two moments of the offspring distribution consistently on the explosion set of the process (and, apart from some lattice parameters, no parameters that are not determined by those moments). Somewhat surprisingly, in our context, where we observe a binomially distributed subset of each generation, we are able to estimate three functions of the parameters consistently. In concrete situations, this often enables us to estimate π consistently, as well as the mean number of offspring. We apply the estimators to data for a real epidemic of classical swine fever.

Mixtures of increasing failure rate distributions can decrease, at least in some intervals of time. Usually this property is observed asymptotically, as t → ∞, which is due to the fact that a mixture failure rate is ‘bent down’, as the weakest populations are dying out first. We consider a survival model that generalizes additive hazards models, proportional hazards models, and accelerated life models very well known in reliability and survival analysis. We obtain new explicit asymptotic relations for a general setting and study specific cases. Under reasonable assumptions we prove that the asymptotic behavior of the mixture failure rate depends only on the behavior of the mixing distribution in the neighborhood of the left-hand endpoint of its support, and not on the whole mixing distribution.

Autoregressive arrival models are described by a few parameters and provide a simple means to obtain analytical models for matching the first- and second-order statistics of measured data. We consider a discrete-time queueing system where the service time of a customer occupies one slot and the arrival process is governed by a discrete autoregressive process of order 1 (a DAR(1) process) which is characterized by an arbitrary stationary batch size distribution and a correlation coefficient. The tail behaviors of the queue length and the waiting time distributions are examined. In particular, it is shown that, unlike in the classical queueing models with Markovian arrival processes, the correlation in the DAR(1) model results in nongeometric tail behavior of the queue length (and the waiting time) if the stationary distribution of the DAR(1) process has infinite support. A complete characterization of the geometric tail behavior of the queue length (and the waiting time) is presented, showing the impact of the stationary distribution and the correlation coefficient when the stationary distribution of the DAR(1) process has finite support. It is also shown that the stationary distribution of the queue length (and the waiting time) has a tail of regular variation with index -β − 1, by finding an explicit expression for the tail asymptotics when the stationary distribution of the DAR(1) process has a tail of regular variation with index -β.

The estimation of P(Sn>u) by simulation, where Sn is the sum of independent, identically distributed random varibles Y1,…,Yn, is of importance in many applications. We propose two simulation estimators based upon the identity P(Sn>u)=nP(Sn>u, Mn=Yn), where Mn=max(Y1,…,Yn). One estimator uses importance sampling (for Yn only), and the other uses conditional Monte Carlo conditioning upon Y1,…,Yn−1. Properties of the relative error of the estimators are derived and a numerical study given in terms of the M/G/1 queue in which n is replaced by an independent geometric random variable N. The conclusion is that the new estimators compare extremely favorably with previous ones. In particular, the conditional Monte Carlo estimator is the first heavy-tailed example of an estimator with bounded relative error. Further improvements are obtained in the random-N case, by incorporating control variates and stratification techniques into the new estimation procedures.

In this paper, we extend the integer-valued model class to give a nonnegative integer-valued bilinear process, denoted by INBL(p,q,m,n), similar to the real-valued bilinear model. We demonstrate the existence of this strictly stationary process and give an existence condition for it. The estimation problem is discussed in the context of a particular simple case. The method of moments is applied and the asymptotic joint distribution of the estimators is given: it turns out to be a normal distribution. We present numerical examples and applications of the model to real time series data on meningitis and Escherichia coli infections.

In this paper, motivated by the problem of the coexistence on transmission links of telecommunications networks of elastic and unresponsive traffic, we study the impact on the busy period of an M/M/1 queue of a small perturbation in the service rate. The perturbation depends upon an independent stationary process (X(t)) and is quantified by means of a parameter ε ≪ 1. We specifically compute the two first terms of the power series expansion in ε of the mean value of the busy period duration. This allows us to study the validity of the reduced service rate approximation, which consists in comparing the perturbed M/M/1 queue with the M/M/1 queue whose service rate is constant and equal to the mean value of the perturbation. For the first term of the expansion, the two systems are equivalent. For the second term, the situation is more complex and it is shown that the correlations of the environment process (X(t)) play a key role.

The ‘square root formula’ in the Internet transmission control protocol (TCP) states that if the probability p of packet loss becomes small and there is independence between packets, then the stationary distribution of the congestion window W is such that the distribution of W√p is almost independent of p and is completely characterizable. This paper gives an elementary proof of the convergence of the stationary distributions for a much wider class of processes that includes classical TCP as well as T. Kelly's ‘scalable TCP’. This paper also gives stochastic dominance results that translate to a rate of convergence.

In this paper our object is to show that a certain class of nonstationary random processes can locally be approximated by stationary processes. The class of processes we are considering includes the time-varying autoregressive conditional heteroscedastic and generalised autoregressive conditional heteroscedastic processes, amongst others. The measure of deviation from stationarity can be expressed as a function of a derivative random process. This derivative process inherits many properties common to stationary processes. We also show that the derivative processes obtained here have alpha-mixing properties.