In this paper, a new sufficient condition for comparing linear combinations of independent gamma random variables according to star ordering is given. This unifies some of the newly proved results on this problem. Equivalent characterizations between various stochastic orders are established by utilizing the new condition. The main results in this paper generalize and unify several results in the literature including those of Amiri, Khaledi, and Samaniego [2], Zhao [18], and Kochar and Xu [9].

A stochastic dynamic program incurs two types of cost: a service cost and a quality of service (delay) cost. The objective is to minimize the expected average service cost, subject to a constraint on the average quality of service cost. When the state space S is finite, we show how to compute an optimal policy for the general constrained problem under weak conditions. The development uses a Lagrange multiplier approach and value iteration. When S is denumerably infinite, we give a method for computation of an optimal policy, using a sequence of approximating finite state problems. The method is illustrated with two computational examples.

Two approaches for simulating the reliability function are considered–one using the total hazard estimator and the other using importance sampling. It is shown both for the Wheatstone Bridge System and for a triangular system that the total hazard estimator has significantly smaller variance when compared both to the standard importance sampling estimator and to an improved version of it.

A novel algorithm is developed which computes the ergodic probability vector for large Markov chains. Decomposing the state space into lumps, the algorithm generates a replacement process on each lump, where any exit from a lump is instantaneously replaced at some state in that lump. The replacement distributions are constructed recursively in such a way that, in the limit, the ergodic probability vector for a replacement process on one lump will be proportional to the ergodic probability vector of the original Markov chain restricted to that lump. Inverse matrices computed in the algorithm are of size (M – 1), where M is the number of lumps, thereby providing a substantial rank reduction. When a special structure is present, the procedure for generating the replacement distributions can be simplified. The relevance of the new algorithm to the aggregation-disaggregation algorithm of Takahashi [29] is also discussed.

Generalized semi-Markov processes and stochastic Petri nets provide building blocks for specification of discrete event system simulations on a finite or countable state space. The two formal systems differ, however, in the event scheduling (clock-setting) mechanism, the state transition mechanism, and the form of the state space. We have shown previously that stochastic Petri nets have at least the modeling power of generalized semi-Markov processes. In this paper we show that stochastic Petri nets and generalized semi-Markov processes, in fact, have the same modeling power. Combining this result with known results for generalized semi-Markov processes, we also obtain conditions for time-average convergence and convergence in distribution along with a central limit theorem for the marking process of a stochastic Petri net.

In this article, we formalize the framework for the supplementary variable technique in stochastic models. Specifically, we show that the use of remaining or elapsed times (or any metric) as supplementary variables leads to the notion of forward or backward Chapman–Kolmogorov equations, respectively. We further show that for a class of queueing systems, using remaining time as the supplementary variable makes analysis simpler.

We define a notion of order of recurrence for the states and transitions of a general class of time-inhomogeneous Markov chains with transition probabilities proportional to powers of a small vanishing parameter. These orders are shown to satisfy a balance equation across every edge cut in the associated graph. The resulting order balance equations allow computation of the orders of recurrence of the states, and thereby the determination of the asymptotic behavior of the Markov chain.

The method of optimization by simulated annealing is a special case of such Markov processes, and can therefore be treated by means of these balance equations. In particular, in this special situation we show that there holds a detailed balance of order of recurrence across every edge in the graph. Moreover, the sum of the order of recurrence of a state and its cost is shown to be a constant in each connected set of recurrent states. By this approach, we determine the necessary and sufficient condition on the “rate of cooling” to guarantee that a minimum of the optimization problem is hit with probability one. Moreover, the rates of convergence of the probabilities can be deduced from the orders of recurrence.

The purpose of this study is two-fold. First, we investigate further properties of the second-order regular variation (2RV). These properties include the preservation properties of 2RV under the composition operation and the generalized inverse transform, among others. Second, we derive second-order expansions of the tail probabilities of convolutions of non-independent and identically distributed (i.i.d.) heavy-tail random variables, and establish second-order expansions of risk concentration under mild assumptions. The main results extend some ones in the literature from the i.i.d. case to non-i.i.d. case.

A carousel is a computer-controlled warehousing system, which is widely used to store small- and medium-sized goods. One of the most important performance characteristics of such systems is the pick time of an order, which mostly depends on the travel time of the carousel. In this article, we consider some reasonable heuristics for order picking. In particular, we establish properties of the Nearest Item (NI) heuristic. This one is frequently used in practice. We derive tight upper bounds for the travel time under the NI heuristic and closed-form expressions for its mean and variance. We also present a simple two-moment approximation for the distribution of the travel time. In addition, we find the mean, variance, and distribution for the number of turns.

In this paper, we study the dependence properties of spacings. It is proved that if X1,..., Xn are exchangeable random variables which are TP2 in pairs and their joint density is log-convex in each argument, then the spacings are MTP2 dependent. Next, we consider the case of independent but nonhomogeneous exponential random variables. It is shown that in this case, in general, the spacings are not MTP2 dependent. However, in the case of a single outlier when all except one parameters are equal, the spacings are shown to be MTP2 dependent and, hence, they are associated. A consequence of this result is that in this case, the variances of the order statistics are increasing. It is also proved that in the case of the multiple-outliers model, all consecutive pairs of spacings are TP2 dependent.

A random walk that is skip-free to the left can only move down one level at a time but can skip up several levels. Such random walk features prominently in many places in applied probability including queuing theory and the theory of branching processes. This article exploits the special structure in this class of random walk to obtain a number of simplified derivations for results that are much more difficult in general cases. Although some of the results in this article have appeared elsewhere, our proof approach is different.

In this article we investigate less restrictive conditions on the model parameters that enable one to establish the likelihood ratio ordering of one generalized order statistic by conditioning on the right tail of another lower-indexed generalized order statistic. One application of the main results is also presented.

In the literature, most of the bounds for the renewal function U(x) corresponding to a lifetime distribution F are given in terms of the first two moments of F only. The best general upper bound of this type is the one given in Lorden (1970). In the present article, we show that improved bounds can be obtained if one exploits the specific form of the distribution F. We derive a bound that improves upon Lorden's, at least on an interval [0,a) with a ≤ ∞, and we give both sufficient and necessary conditions for this improvement to hold uniformly for x ≥ 0. Refined upper as well as lower bounds are given for the case where F belongs to a class of distributions with monotone aging or when the renewal density is monotone.

We consider the reliability of one random variable relative to another, when the variables are continuous and take values in an interval [a, b). We give definitions and characterizations for the exponential property and the standard aging properties IFR, IFRA, and NBU. The exponential property defines an equivalence relation on the distributions, and then each of these aging properties defines a partial order on the distributions, modulo the exponential equivalence. We give a set of conditions that must be satisfied for a general aging property to define such a partial order and show that these conditions are not satisfied by the NBUE property. Several parametric families of distributions are considered.

We develop an algorithm for simulating approximate random samples from the invariant measure of a Markov chain using backward coupling of embedded regeneration times. Related methods have been used effectively for finite chains and for stochastically monotone chains: here we propose a method of implementation which avoids these restrictions by using a “cycle-length” truncation. We show that the coupling times have good theoretical properties and describe benefits and difficulties of implementing the methods in practice.

Motivated by a class of Partially Observable Markov Decision Processes with application in surveillance systems in which a set of imperfectly observed state processes is to be inferred from a subset of available observations through a Bayesian approach, we formulate and analyze a special family of multi-armed restless bandit problems. We consider the problem of finding an optimal policy for observing the processes that maximizes the total expected net rewards over an infinite time horizon subject to the resource availability. From the Lagrangian relaxation of the original problem, an index policy can be derived, as long as the existence of the Whittle index is ensured. We demonstrate that such a class of reinitializing bandits in which the projects' state deteriorates while active and resets to its initial state when passive until its completion possesses the structural property of indexability and we further show how to compute the index in closed form. In general, the Whittle index rule for restless bandit problems does not achieve optimality. However, we show that the proposed Whittle index rule is optimal for the problem under study in the case of stochastically heterogenous arms under the expected total criterion, and it is further recovered by a simple tractable rule referred to as the 1-limited Round Robin rule. Moreover, we illustrate the significant suboptimality of other widely used heuristic: the Myopic index rule, by computing in closed form its suboptimality gap. We present numerical studies which illustrate for the more general instances the performance advantages of the Whittle index rule over other simple heuristics.

We consider a modulated fluid system with a finite state-space Markov chain Jt as modulating process and general state-dependent net input rates. We derive differential equations for the transient and the stationary distribution of (Wt, Jt), where Wt is the content process, and the corresponding Laplace transforms with respect to time. Moreover, we study the level hitting times of Wt. Our results lead to explicit formulas in the case of two modulating states.

This paper considers simple step-stress accelerated life tests (SSALTs) for one-shot devices. The one-shot device is an item that cannot be used again after the test, for instance, munitions, rockets, and automobile air-bags. Either left-or right-censored data are collected instead of actual lifetimes of the devices under test. An expectation-maximization algorithm is developed here to find the maximum likelihood estimates of the model parameters based on one-shot device testing data collected from simple SSALTs. Furthermore, the asymptotic variance of the mean lifetime under normal operating conditions is determined under the expectation-maximization framework. On the other hand, the optimal design that minimizes the asymptotic variance of the estimate of the mean lifetime under normal operating conditions in terms of three decision variables, including stress levels, inspection times, and sample allocation is discussed. A procedure then is presented to determine the decision variables when a range of stress levels and the termination time of the test as well as normal operating conditions of the devices are given. The properties of the optimal design and the effects of errors in pre-specified planning values of the model parameters are also investigated. Comprehensive simulation studies show that the procedure is quite reliable for the design of simple SSALTs.

In this article we present a new representation for the steady-state distribution of the workload of the second queue in a two-node tandem network. It involves the difference of two suprema over two adjacent intervals. In the case of spectrally positive Lévy input, this enables us to derive the Laplace transform and Pollaczek–Khintchine representation of the workload of the second queue. Additionally, we obtain the exact distribution of the workload in the case of Brownian and Poisson input, as well as some insightful formulas representing the exact asymptotics for α-stable Lévy inputs.

In this paper we develop a stochastic differential equation to describe the dynamic evolution of the congestion window size of a single TCP session over a network. The model takes into account recovery from packet losses with both fast recovery and time-outs, boundary behavior at zero and maximum window size, and slow-start after time-outs. We solve the differential equation to derive the distribution of the window size in steady state. We compare the model predictions with the output from the NS simulator.