We establish strong consistency (i.e., almost sure convergence) of infinitesimal perturbation analysis (IPA) estimators of derivatives of steady-state means for a broad class of systems. Our results substantially extend previously available results on steady-state derivative estimation via IPA.

Our basic assumption is that the process under study is regenerative, but our analysis uses regenerative structure in an indirect way: IPA estimators are typically biased over regenerative cycles, so straightforward differentiation of the regenerative ratio formula does not necessarily yield a valid estimator of the derivative of a steady-state mean. Instead, we use regeneration to pass from unbiasedness over fixed, finite time horizons to convergence as the time horizon grows. This provides a systematic way of extending results on unbiasedness to strong consistency.

Given that the underlying process regenerates, we provide conditions under which a certain augmented process is also regenerative. The augmented process includes additional information needed to evaluate derivatives; derivatives of time averages of the original process are time averages of the augmented process. Thus, through this augmentation we are able to apply standard renewal theory results to the convergence of derivatives.

Let X be a random vector and A a matrix. Let M be the maximal coordinate of the vector AX. For given marginal distributions of the coordinates of X, we present sharp bounds on the expectations of convex increasing functions of M. We derive joint distributions of X that achieve some of these bounds, and under these “worst case” distributions we study the joint distribution of M and the index of the largest coordinate of AX. Some possible applications are PERT network analysis and design of experiments.

A double-loop network G(h1, h2) has n nodes represented by the n residues modulo n and 2n links given by i ↦i + h1, i ↦ i + h2, i = 0,1,…,n – 1.We consider the reliability model where each link fails independently with probability p, the nodes always work, and the network fails if it is not strongly connected. There exists no known polynomial time algorithm to compute the reliabilities of general double-loop networks. When p is small, the reliability is dominated by the link connectivity. As all strongly connected double.loop networks have link connectivity exactly 2, a finer measure of reliability is needed. In this paper we give such a measure and show how to use it to obtain the most reliable double-loop networks.

The Lagrange-Sylvester interpolation polynomial approach provides a simple, eigenvector-free representation for finite diagonalizable matrices. This paper discusses the Lagrange-Sylvester methodology and applies it to skip free to the right Markov chains. It leads to relatively simple, eigenvalue-based expressions for first passage time distributions and transition probabilities.

μ-Geometric ergodicity of two-dimensional versions of the ALOHA and coupled processors models is verified by checking μ-geometric recurrence. Ergodicity and convergence of the Laplace-Stieltjes transforms in a neighborhood of 0 are necessary and sufficient conditions for the first model. The second model is exponential, for which ergodicity suffices to establish the required results.

Employing a failure rate approach, we propose a test statistic, , for the classic goodness-of-fit problem. It is then shown that a variation of , obtained by replacing observed variances by expected variances (an unwise change in our point of view), leads to the classical test statistic, x2. We argue that should be better approximated by a chi-square distribution, and thus employing , the true p−values should be closer to the nominal p−values than under x2 Various other comparisons of the two tests are made.

Let x(j) be the expected reward accumulated up to hitting an absorbing set in a Markov chain, starting from state j. Suppose the transition probabilities and the one-step reward function depend on a parameter, and denote by y(j) the derivative of x(j) with respect to that parameter. We estimate y(0) starting from the respective Poisson equations that x = [x(0),x(l),…] and y = [y(0),y(l),…] satisfy. Relative to a likelihood-ratio-method (LRM) estimator, our estimator generally has (much) smaller variance; in a certain sense, it is a conditional expectation of that estimator given x. Unlike LRM, however, we have to estimate certain components of x. Our method has broader scope than LRM: we can estimate sensitivity to opening arcs.

In this work, the discrete event systems called Stochastic Marked Graphs (SMGs) are investigated from a stability point of view. Being a special class of Timed Petri Nets with stochastic firing times, they are studied under general assumptions of stationarity and ergodicity of the firing times and ergodicity of flows of their free strongly connected components. The values of the flows of tokens in an SMG are specified as functions of the intrinsic rates of its free strongly connected components, and various stability issues are discussed.

We consider tandem queueing systems with a general arrival process and exponential service distribution. The queueing system consists of several stations with finite intermediate buffer capacity between the stations. We address the problem of determining the optimal arrangement for the stations. We find that considering the last two stations, the departure process is stochastically faster if the slower station is last. Our results are consistent with the “bowl shape” phenomenon that has been observed in serial queueing systems with zero buffer capacity.

This paper presents a simple and practical approach to solving the equilibrium equations for a class of Markov chains with an infinite number of states. Markov chains arising in queueing and inventory applications often have the property that the state probabilities exhibit a geometric tail behavior. The basic idea of the approach is to reduce the infinite system of linear equations to a finite system using the geometric tail behavior of the equilibrium probabilities. The reduction typically leads to a remarkably small system of linear equations that can be routinely solved by a Gaussian elimination method. An application is given to the single-server queue with scheduled arrivals.

The loss probabilities of customers in the Mx/GI/1/k, GI/Mx/l/k and their related queues such as server vacation models are compared with respect to the convex order of several characteristics, for example, batch size, of the arrival or service process. In the proof, we give a characterization of a truncation expression for a stationary distribution of a finite Markov chain, which is interesting in itself.

We consider a communication network that can support both wideband video calls and narrowband data traffic. First we consider a single link and prove a weak convergence result to justify a piecewise-deterministic Markov process approximation to the system. We then generalize this approximation to allow priorities and more than one link. This second approximation is a generalization of the Erlang fixed-point approximation for loss networks and is justified via a diverse routing limit theorem.

In this paper we consider the problem of finding the optimal order for two servers in series when there is no queue capacity. We show that it is better for the faster server to be first. The strength of this conclusion will depend on the strength of the assumption made about the service distribution. We also find the optimal order for some systems where both servers have the same average service time and different service distributions.

The depth of insertion and the internal path length of recursive trees are studied. Luc Devroye has recently shown that the depth of insertion in recursive trees is asymptotically normal. We give a direct alternative elementary proof of this fact. Furthermore, via the theory of martingales, we show that In, the internal path length of a recursive tree of order n, converges to a limiting distribution. In fact, we show that there exists a random variable I such that (In – n In n)/n→I almost surely and in quadratic mean, as n → α. The method admits, in passing, the calculation of the first two moments of In.

A communication system of n stations is studied. Poisson arrival streams of messages enter the stations and require transmission to a destination station. Each station is equipped with k channels and has a waiting room for messages. For transmission of a message, one channel is needed both at the arrival and at the destination station. The transmission time is exponentially distributed. Messages are lost (possibly after a waiting time) if, at the destination station, all channels are busy. The queueing network model is of the nonproduct type. Sufficient conditions for the existence of an equilibrium distribution are given. For determining the losses at the n stations, a heuristical approximation that requires us to solve a system of nonlinear equations is developed. For this, an efficient iterative numerical algorithm is given. Simulation studies show that the approximation is accurate enough for larger n.

In this paper we present a general framework for stochastic one-machine scheduling problems with zero release times and no partial ordering and review and extend some of the results for nonpreemptive permutation schedules recently obtained for these models.

Sensitivity analysis is an integral part of virtually every study of system reliability. This paper describes a Monte Carlo sampling plan for estimating this sensitivity in system reliability to changes in component reliabilities. The unique feature of the approach is that sample data collected on K independent replications using a specified component reliability vector p are transformed by an importance function into unbiased estimates of system reliability for each component reliability vector q in a set of vectors Q. Moreover, this importance function together with available prior information about the given system enables one to produce estimates that require considerably less computing time to achieve a specified accuracy for all |Q| reliability estimates than a set of |Q| crude Monte Carlo sampling experiments would require to estimate each of the |Q| system reliabilities separately. As the number of components in the system grows, the relative efficiency continues to favor the proposed method.

The paper shows the intimate relationship between the proposal and the method of control variates. Next, it relates the proposal to the estimation of coefficients in a reliability polynomial and indicates how this concept can be used to improve computing efficiency in certain cases. It also describes a procedure that determines the p vector, to be used in the sampling experiment, that minimizes a bound on the worst-case variance. The paper also derives individual and simultaneous confidence intervals that hold for every fixed sample size K. An example illustrates how the proposal works in an s-t connectedness problem.

Separation is one measure of distance from stationarity for Markov chains. Strong stationary times provide bounds on separation and so aid in the analysis of mixing rates. The precise connection between separation and strong stationary times was drawn by Aldous and Diaconis (1987) (Advances in Applied Mathematics 8: 69−97) for discrete time chains. We develop the corresponding foundational theory for continuous time chains; several new and interesting mathematical issues arise.

A Markov decision chain with countable state space incurs two types of costs: an operating cost and a holding cost. The objective is to minimize the expected discounted operating cost, subject to a constraint on the expected discounted holding cost. The existence of an optimal randomized simple policy is proved. This is a policy that randomizes between two stationary policies, that differ in at most one state. Several examples from the control of discrete time queueing systems are discussed.

In this paper we consider one-machine scheduling problems with or without a perfect machine and random processing times and derive among other results elimination criteria for different classes of cost functions.