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.

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.

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 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.

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.

It is well known that in the case of a Poisson process with constant intensity function the interarrival times are independent and identically distributed, each having exponential distribution. We study this problem when the intensity function is monotone. In particular, we show that in the case of a nonhomogeneous Poisson process with decreasing (increasing) intensity the interarrival times are increasing (decreasing) in the hazard rate ordering sense and they are also jointly likelihood ratio ordered (cf. Shanthikumar and Yao, 1991, Bivariate characterization of some stochastic order relations, Advances in Applied Probability 23: 642–659). This result is stronger than the usual stochastic ordering between the successive interarrival times. Also in this case, the interarrival times are conditionally increasing in sequence and, as a consequence, they are associated. We also consider the problem of comparing two nonhomogeneous Poisson processes in terms of the ratio of their intensity functions and establish some results on the successive number of events from one process occurring between two consecutive occurrences from the second process.

We analyze a family of queueing systems where the interarrival time In+1 between customers n and n + 1 depends on the service time Bn of customer n. Specifically, we consider cases where the dependency between In+1 and Bn is a proportionality relation and Bn is an exponentially distributed random variable. Such dependencies arise in the context of packet-switched networks that use rate policing functions to regulate the amount of data that can arrive to a link within any given time interval. These controls result in significant dependencies between the amount of work brought in by customers/packets and the time between successive customers. The models developed in the paper and the associated solutions are, however, of independent interest and are potentially applicable to other environments.

Several scenarios that consist of adding an independent random variable to the interarrival time, allowing the proportionality to be random and the combination of the two are considered. In all cases, we provide expressions for the Laplace-Stieltjes Transform of the waiting time of a customer in the system. Numerical results are provided and compared to those of an equivalent system without dependencies.

This paper examines the availability of an inspected system where the rate of deterioration is governed by an exogenous random environment. We develop a qualitative result that exposes the relationship among remaining life, deterioration, and repairs. This result requires no specific distributional assumptions. We use this result in developing a simple bound on stationary availability. We investigate these relationships numerically for a Markovian system and provide insights useful to practitioners in selecting an inspection process that guarantees a target availability.

Diameter measurements on successive metal hubs from a machining operation are modeled using a random walk with observation error and linear drift corresponding to tool wear. After producing and measuring a hub, the depth of the cutting tool on the lathe can be adjusted in integer multiples of 0.0001 inches. How should the tool be adjusted?

An optimal discrete adjustment strategy is derived assuming that the lathe automatically corrects for deterministic tool wear. The objective is to minimize expected run costs proportional to the sum of squared diameter deviations from a target plus fixed charges for manual tool adjustments. The optimal strategy makes no manual adjustment if an estimate of the process mean is near target. Otherwise, an adjustment is made to return the estimated mean as near to target as possible within the adjustment resolution.

The region where no adjustments are made widens near the end of the production run where adjustments have only short-term impact. The region converges as the number of remaining periods increases. Plots of expected run costs show that the extra cost of discreteness is small at high resolution but is substantial when the adjustment grid is coarse.

An implementable on-line approach to solve the nonlinear filtering equation for a partially observed system in which both the state and observation processes are jump processes is presented. By making use of the special structure of jump processes, the new method allows us to obtain the solution of the resulting nonlinear filtering equation from solving a linear system of ordinary differential equations and a linear system of algebraic equations recursively and via a simple normalization procedure.