Let X1,X2,… be an ergodic Markov chain on the countable state space. We construct a strong stationary dual chain X* whose first hitting times give sharp bounds on the convergence to stationarity for X. Examples include birth and death chains, queueing models, and the excess life process of renewal theory. This paper gives the first extension of the stopping time arguments of Aldous and Diaconis [1,2] to infinite state spaces.

The use of the total hazard variable in simulation is studied. When estimating the mean time until a certain event occurs, this variable can be a powerful variance-reducing control variate. When estimating a small probability, it can be utilized as a direct estimator. Applications to reliability, quality control, and queueing are given.

An infinite random stream of ordered pairs arrives sequentially in discrete time. A pair consists of a “candidate” and an “offer,” each of which is either of type I (with probability p) or of type II (with probability q = 1 – p). Offers are to be assigned to candidates, yielding a reward R > 0 if they match in type, or a smaller reward 0 ≤ r ≤ R if not. An arriving candidate resides in the system until it is assigned, whereas an arriving offer is either assigned immediately to one of the waiting candidates or lost forever. We show that the optimal long-term average reward is R, independent of the population proportion p and the “second prize” r, and that the optimal average reward policy is to assign only a match. Optimal policies for discounted and finite horizon models are also derived.

Let X1, X2,… be i.i.d. random points in R2 with distribution v, and let Ln be the length of the shortest path through X1,…, Xn. The exact almost sure rate of growth of Ln, is obtained under the assumption that v is self-similar in an appropriate sense. This extends a well-known theorem of Beardwood, Halton, and Hammersley.

Suppose that you find yourself trapped in a maze about which you know nothing except that it has an exit point. We present an optimal strategy that will lead you to the exit point in minimum expected time. This strategy ensures that the expected total length of the arcs you traverse will not exceed the sum of the lengths of the arcs in the maze.

Bivariate Lomax distribution due to Lindley and Singpurwalla has been characterized through the bivariate extension of a univariate characterizing property of the Lomax distribution.

A number of data items (1,2,…,n) are to be maintained in a structure which consists of several linear lists. Successive requests to access items are independent random variables, and the probability that a particular request is for item i is pi. The cost of accessing the jth item from the front of a list is j. For a single list, the move-to-front rule (MF) has been extensively studied and has been shown to provide good performance. In some actual circumstances, MF is the only physically realizable or convenient policy. We extend the study of move-to-front by examining the case where items are kept in several lists. Following its access, an item must be replaced at the front of one of the lists. In certain cases, assuming the pi's are known, the policy which minimizes the average retrieval cost takes a particularly simple form: no item is ever moved from the list in which it is placed initially.

We consider a problem in which jobs continually arrive to a set of n processors that are arranged in an ordered list. When a job arrives the first processor in line attempts to process it; if it is unsuccessful then the next in line attempts it, and so on. Each time that processor j attempts to process a job it is, independently of all else, successful with (an unknown) probability pj. After a job has been completed or all n attempts have failed then, based on the result, we can reorder the processors before the next job arrives, with the objective being to minimize the average number of attempts per job. This paper compares the transposition rule and the move to the front rule.

In the classical TDMA, which has been the subject of extensive research in the past, a single slot is allocated to each and every user within every frame. In many situations this leads to an inefficient utilization of the channel calling for a nonhomogeneous allocation of slots. This paper focuses on a generalized TDMA scheme in which users are allocated more than a single slot per frame, not necessarily contiguous. We derive the delay distribution and buffer occupancy for such a scheme as well as the expected values of these quantities.

The burn-in problem is reframed in a decision-making context. The role of the predictive life distribution in the burn-in decision problem is highlighted. The case in which the predictive distribution is a mixture of exponentials is discussed extensively.

In this paper, we consider a discrete-time queueing model for a Time Division Multiplexing (TDM) system with integration of voice and data (a model introduced by Li and Mark [16]). The voice traffic is a superposition of N Markov chains, which alternate between two states: the talkspurt state and the silence state. The data traffic is Poisson and independent of the voice sources. We show that the average queue size is increasing in certain correlation coefficients of the voice sources, increasing convex in the proportion of time the voice sources are in talkspurts, increasing convex in the number of voice sources, and increasing convex in the data traffic intensity. However, it is decreasing convex in the number of channels. These structural results yield various bounds. To take video traffic into account as well, we adapt a model of Maglaris et al. [18]. In their model, video traffic is generated by a continuous-state autoregressive Markov process that matches the average rate and the autocovariance of the output of a video coder. We show that if we replace their autoregressive model by a two-state Markov chain model with the same rate and correlation coefficient, we obtain an upper bound for the queue size. This replacement enables us to treat the video traffic as a voice source and use the techniques developed for dealing with voice/data integration to obtain bounds and estimates.

We introduce the concept of “strong interchangeability” of random vectors. Strongly interchangeable random vectors arise naturally in packetized voice channels, M/G/1 queues, symmetric queueing networks, and other standard symmetric distributions. We study some properties of strongly interchangeable random vectors. We show that if (X1, …, XN) is a strongly interchangeable random vector, then even though there is no Markov property, taboo probabilities can be used to compute the joint distribution of ŽN = min1≤n≤N σnk=IXk and ZN = max1≤n≤N σnk=1Xk. For a special instance of this problem that arises in packetized voice communication, it is shown that the resulting algorithm essentially has a complexity of order N4. When ( σnk=1Xk, n = 1,… N) is an associated random vector bound for the joint distribution of ŽN and ZN are obtained and applied to the packetized voice communication problem.

Consider a stochastic loss network, where calls or customer types arrive and have to find a path through the network to a given destination, and where our aim is to maximize the gain (suitably defined) from the network. In general there will be a number of paths available, and when a call arrives the two questions to answer are first, should the call be accepted, and secondly, if it is accepted which route should it take? The answer to the first question is in some sense harder than the second, and all dynamic routing or control policies have some explicit or implicit mechanism for rejecting calls and so answer the question in some way.

A simple random algorithm (SRA) is an algorithm whose behavior is governed by a first-order Markov chain. The expected time complexity of an SRA, given its initial state, is essentially the time to absorption of the underlying chain. The standard approach in computing the expected runtime is numerical. Under certain conditions on the probability transition matrix of an SRA, bounds on its expected runtime can be obtained using simple probabilistic arguments. In particular, one can obtain upper and lower (average time) logarithmic bounds for certain algorithms based on SRAs.

Items of various types arrive at a bin-packing facility according to random processes and are to be combined with other readily available items of different types and packed into bins using one of a number of possible packings. One might think of a manufacturing context in which randomly arriving subassemblies are to be combined with subassemblies from an existing inventory to assemble a variety of finished products. Packing must be done on-line; that is, as each item arrives, it must be allocated to a bin whose configuration of packing is fixed. Moreover, it is required that the packing be managed in such a way that the readily available items are consumed at predescribed rates, corresponding perhaps to optimal rates for manufacturing these items. At any moment, some number of bins will be partially full. In practice, it is important that the packing be managed so that the expected number of partially full bins remains uniformly bounded in time. We present a necessary and sufficient condition for this goal to be realized and describe an algorithm to achieve it.

It is known that the lifetime of a k−out−of−n system has increasing failure rate (IFR) if all of its components have independent and identically distributed IFR lifetimes. Derman, Lieberman, and Ross raised the same question for consecutive−k−out−of−n systems. But the scarcity of results gives no clue as to whether most of such systems have IFR's. In this paper, we completely solve the k = 2 and k = 3 cases. We prove that these systems, with a handful of exceptions, do not have IFR's (contradicting the result of Derman, Lieberman, and Ross that a consecutive-2-out-of-n cycle has IFR for any n). Our result suggests the conjecture that for every fixed k there exists nk such that for every n ≧ nk a consecutive-k−out−of−n system does not have IFR. We also prove that for every fixed d there exists nd large enough such that for all n ≧ nd a consecuive.(n – d)−out−of−n system has IFR. In particular, if the system is a line, then nd = 3d +1 for d ≧ 1.

In this paper we consider a problem that arises in estimating the heavy traffic limit of a sojourn time distribution in a queueing network during the course of a medium traffic simulation. We need to estimate α = E[f(γ, M)], where γ is an unknown constant and M a random variable. More specifically, we are given an iid sequence of random vectors {(Xi, Mi), 1 ≤ i ≤ n}, with γ = E[Xi] and Mi having the same distribution as M.

For known γ, we have a standard estimation problem, which we describe here. The standard estimate is unbiased and asymptotically (as n → 8 ) consistent. There is also a central limit theorem for this estimator. For unknown γ, we provide two estimation procedures, one that requires two passes through the data (as well as storage of {Mi, 1 ≤ i ≤ n}), and another one, which is recursive, requiring only one pass through and bounded storage. The estimators obtained from these two procedures are shown to be strongly consistent, and central limit theorems are also proven for them.

We present a decision procedure to determine the optimal maintenance intervals of a computer software throughout its operational phase. Our model accounts for the average cost per each maintenance activity and the damage cost per failure with the future cost discounted. Our decision policy is optimal in the sense that it minimizes the expected total cost. Our model assumes that the total number of errors in the software has a Poisson distribution with known mean λ and each error causes failures independently of other errors at a known constant failure rate. We study the structures of the optimal policy in terms of λ and present efficient numerical algorithms to compute the optimal maintenance time intervals, the optimal total number of maintenances, and the minimal total expected cost throughout the maintenance phase.

The capacity of the white Gaussian noise (WGN) channel is widely stated as S/N0 nats/unit time. This conclusion is commonly derived either formally, or from the capacity, W ln(l + S/N0W), of the corresponding band-limited channel with bandwidth W, by taking W→8. In this paper, the WGN channel capacity is instead found directly by treating WGN as an arbitrary noise sequence that whitens in a general sense. In addition, the coding theorems proved make explicit the class of allowable receivers, either finite- or infinite-dimensional correlation receivers, or unconstrained. The capacities for these three receiver classes are found to be, respectively: S/N0 for S> 0, and 0 for S = 0; and 8 for all S ≥ 0. In those cases where the capacity is infinite, actual transmitter–receiver pairs are specified that achieve capacity.

In this paper, TP2 orderings of distributions and of survival functions are considered. It is shown that the first passage time of a Markov process with TP2- ordered transition distributions has an increasing failure rate (IFR). Conditions are also given for which mixtures of IFR distributions are IFR. A formula is obtained for the failure rate when the strength distribution is a function of both load and strength. This formula, in conjunction with the TP2-ordering on the strength survival functions and log-concavity of the strength and load variables, leads to an increasing failure rate for the strength distribution. Finally, two models based on this theory are presented which explain the IFR character of the strength distribution of fibrous composite materials.