A special pattern of consecutive points on a control chart often suggests that the process is out of control due to a special cause. Usually, the probability of such a pattern is not difficult to calculate, but its relation to the rate of a false signal in a control chart is unclear. In this paper we give such a relation for a wide class of patterns that includes six of the eight patterns of special cause discussed in the AT&T Statistical Quality Control Handbook (1958). We derive a surprisingly simple formula for the rate of a false signal in terms of the pattern probability and use this result to improve on the test proposed in the handbook. We also use this formula to give a simple proof of a result of Wolfowitz (1944, Annals of Mathematical Statistics 15: 163–172) and Olmstead (1945, Annals of Mathematical Statistics 17: 24–33) on the monotone sequence. Finally, we give an approximation of the rate of a false signal for another wide class of patterns that covers the two remaining patterns of special cause in the AT&T handbook.

A practical source coding scheme based on approximate string matching is proposed. It is an approximate fixed-length string matching data compression combined with a block-coder based on the empirical distribution. A lemma on approximate string matching, which is an extension of the Kac Lemma, is proved. It is shown, based on the lemma, that the deterministic algorithm converts the stationary and ergodic source, u, into an output process v, and under the assumption that v is a stationary process, after the scheme has run for an infinite time, the optimal compression ratio R(D) is achieved. This reduces the problem of the universal lossy coder to the proof of stationarity of the output process ν in the proposed algorithm. The main advantages of the proposed method are the asymptotic sequential behavior of the encoder and the simplicity of the decoder.

A duality is presented for real-valued stochastic sequences [Vn] defined by a general recursion of the form Vn+1 = f(Vn, Un), with [Un] a stationary driving sequence and f nonnegative, continuous, and monotone in its first variable. The duality is obtained by defining a dual function g of f, which if used recursively on the time reversal of [Un] defines a dual risk process. As a consequence, we prove that steady-state probabilities for Vn can always be expressed as transient probabilities of the dual risk process. The construction is related to duality of stochastically monotone Markov processes as studied by Siegmund (1976, The equivalence of absorbing and reflecting barrier problems for stochastically monotone Markov processes, Annals of Probability 4: 914–924). Our method of proof involves an elementary sample-path analysis. A variety of examples are given, including random walks with stationary increments and two reflecting barriers, reservoir models, autoregressive processes, and branching processes. Finally, general stability issues of the content process are dealt with by expressing them in terms of the dual risk process.

This paper is concerned with how coupling can be used to enhance the efficiency of a certain class of terminating simulations, in Markov process settings in which the stationary distribution is known. We are able to theoretically establish that our coupling-based estimator is often more efficient than the naive estimator. In addition, we discuss extensions of our methodology to Markov process settings in which conventional coupling fails and show (for Doeblin chains) that knowledge of the stationary distribution is sometimes unnecessary.

Bidimensional processes defined by dx(t) = ρ(x, y) dt and dy(t) = f(y) dt + σ(y) dW(t), where W(t) is a Wiener process, are considered. Let T(x, y, ξ) = inf[t ≥ 0: x(t] = ξ| x(0) = x, y(0) = y). Explicit expressions for the moment generating function of T(x, y, 0) and for the characteristic function of y(T(x, y, ξ)) are obtained in two special cases. The method of similarity solutions is used. Applications to optimal control problems are presented.

We consider a bandit problem with infinitely many Bernoulli arms whose unknown parameters are i.i.d. We present two policies that maximize the almost sure average reward over an infinite horizon. Neither policy ever returns to a previously observed arm after switching to a new one or retains information from discarded arms, and runs of failures indicate the selection of a new arm. The first policy is nonstationary and requires no information about the distribution of the Bernoulli parameter. The second is stationary and requires only partial information; its optimality is established via renewal theory. We also develop ε-optimal stationary policies that require no information about the distribution of the unknown parameter and discuss universally optimal stationary policies.

The total hazard Monte Carlo estimator has been successfully applied to estimate the unreliability of multicomponent systems. Nevertheless, there are some cases where it is less efficient than the crude estimator. We propose in this paper a simple modification that improves the performance of the total hazard estimator.

We consider an infinite series of independent and identical -/GI/∞ queues fed by an arbitrary stationary and ergodic arrival process, A1. Let Ai be the arrival process to the ith node, and let νi be the law of Ai. Denote by (·) the input–output map of the ·/GI/∞ node; that is, νi+1 = (νi). It is known that the Poisson process is a fixed point for . In this paper, we are interested in the asymptotic distribution of the departure process from the nth node, νn+1 = n(ν1), as n ∞. Using couplings for random walks, this limiting distribution is shown to be either a Poisson process or a stationary ν-Poisson process, depending on the joint distribution of A1 and the service process. This generalizes a result of Vere-Jones (1968, Journal of the Royal Statistical Society, Series B 30: 321–333) and is similar in flavor to Mountford and Prabhakar (1995, Annals of Applied Probability 5(1): 121–127), where Poisson convergence is established for departures from a series of exponential server queues using coupling methods.

This paper is concerned with overflows in queues fed by Markov fluid input. The results are asymptotic in the number of sources; that is, we let the number of users grow large. The main objectives of this study are to characterize both overflow probability and the “most probable way” in which overflow occurs. Applying large deviations techniques, known results (Weiss, 1986, Advances in Applied Probability 18: 506–532) for exponential on-off sources are extended to general Markov fluid input. Successively, zero, small, and large buffers are treated. Finally, results for multiclass input are given.

A variety of methods for reducing the variance on Monte Carlo estimators of the expected waiting time Wn of the nth customer in a GI/G/1 queue are studied. The ideas involve Spitzer's identity, importance sampling, and sums with stratified or controlled randomized length.

We study two single-server multiclass systems in tandem. As simple optimal policies exist only in special cases, our objective is to study simple policies that perform close to optimality. For one such policy, which is based on the μc rule, we prove that it is optimal in an asymptotic sense. Numerical work comparing this policy with the optimal one is also supplied.

This paper presents diffusion limits for congestion in networks of finite-buffer queues. We consider both loss networks, such as those in communication systems, and networks with manufacturing blocking. In both cases, the number in system process, under conditions of approximate balance under heavy traffic and appropriate scaling of buffers, is shown to behave like a multidimensional Brownian motion reflected to stay within a rectangle in the positive orthant. The two limits differ in directions of reflection off the faces representing full buffers. The limits suggest possible diffusion approximations for finitebuffer networks.

Recently, a Pollaczek-Khintchine-like formulation for M/G/l queues with disasters has been obtained. A disaster is said to occur if a negative arrival causes all the customers (and therefore work) to depart from the system immediately. This study generalizes this result further, as it is shown to hold even when negative arrivals cause only part of the work to be demolished. In other words, an arbitrary amount of work, following a known distribution, is allowed to be removed at a negative event. Under these circumstances, a general approach for obtaining the Pollaczek–Khintchine Formula is proposed, which is then illustrated via several examples. Typically, it is seen that the formulainvolves certain parameters that are not explicitly known. The formula itself is made possible due to the number in system being geometric under preemptive last in-first out discipline.

Consider a renewal process [N(t), t>0]. For fixed t > 0 and each n ≥ 1, let yn,1, …, Yn,n be independent exponentials each having mean t/n, independent of the renewal process. Ross [2] developed a recursion for the sequence of approximations mn = EN(Yn,1 + … + Yn,n) that converges to m(t)if the renewal function m(·) = EN(·) is continuous at t > 0. In this note, we derive an upper bound on the rate of convergence of this sequence under mild conditions on m near t. Tightness of this bound is discussed in terms of regularity conditions on m.

An optimal search among discrete cells for a Markovian object has been labeled the leprechaun problem. This paper discusses the leprechaun's problem: How should the leprechaun behave in order to maximize the probability of being found? A subjective Bayesian approach is taken in modeling the leprechaun.

This paper considers a variation of the classical full-information best-choice problem. The problem allows success to be obtained even when the best item is not selected, provided the item that is selected is within the allowance of the best item. Under certain regularity conditions on the allowance function, the general nature of the optimal strategy is given as well as an algorithm to determine it exactly. It is also examined how the success probability depends on the allowance function and the underlying distribution of the observed values of the items.

We present necessary and suffi2ient Foster-type conditions for a countable state Markov chain to have an invariant probability with at least a geometric tail. These conditions are obtained by using a generalized Farkas Theorem in Linear Algebra. The purpose of this note is also to pose an interesting and important research problem that is still largely open.

This paper studies bicriterion optimization of an M/G/1 queue with a server that can be switched on and off. One criterion is an average number of customers in the system, and another criterion is an average operating cost per unit time. Operating costs consist of switching and running costs. We describe the structure of Pareto optimal policies for a bicriterion problem and solve problems of optimization of one of these criteria under a constraint for another one.

We analyze service systems where Nservers (N > 2) move one at a time along an array of stations to satisfy a known number of requests for service. Processing a request consists of determining the server to satisfy the request. The cost of processing a request is determined by the distance the server that performs the request has to move. We determine qualitative properties of sequencing strategies that minimize the expected cost incurred by the service of all requests when the array of stations is on a circle or an interval.

Motivated by two measures of presortedness, number of runs and oscillation of a permutation, related to the sorting problem, we derive an error bound for normal approximation to the distribution of Here, αij's are given real numbers and π is a uniformly distributed random permutation of {l,…, n}. The derivation is based on Stein's method.