The concept of rainflow cycles is often used in fatigue of materials for analyzing load processes. Methods are developed for computation of the rainflow matrix for a random load that is changing properties over time due to changes of the system dynamics; for example, for a random vehicle load it could reflect different driving conditions. The random load is modeled by a switching process with Markov regime; that is, the random load changes properties according to a hidden (not observed) Markov chain.

An algorithm is developed for a switching process where each part of the load is modeled by a Markov chain. As only the local extremes are of importance for rainflow analysis, another approach is to model the sequence of turning points by a Markov chain. The main result of this paper is an algorithm for computation of the rainflow matrix for a switching process where each part is described by a Markov chain of turning points. The algorithms are illustrated by numerical examples.

In this paper we study a new variability order that is denoted by ≤st:icx. This order has important advantages over previous variability orders that have been introduced and studied in the literature. In particular, X ≤st:icxY implies that Var[h(X)] ≤ Var[h (Y)] for all increasing convex functions h. The new order is also closed under formations of increasing directionally convex functions; thus it follows that it is closed, in particular, under convolutions. These properties make this order useful in applications. Some sufficient conditions for X ≤st:icxY are described. For this purpose, a new order, called the excess wealth order, is introduced and studied. This new order is based on the excess wealth transform which, in turn, is related to the Lorenz curve and to the TTT (total time on test) transform. The relationships to these transforms are also studied in this paper. The main closure properties of the order ≤st:icx are derived, and some typical applications in queueing theory are described.

The elementary problem of exhaustively sampling a finite population without replacement is used as a nonreversible test case for comparing two recently proposed MCMC algorithms for perfect sampling, one based on backward coupling and the other on strong stationary duality. The backward coupling algorithm runs faster in this case, but the duality-based algorithm is unbiased for user impatience. An interesting by-product of the analysis is a new and simple stochastic interpretation of a mixing-time result for the move-to-front rule.

For discrete versions of red-and-black with a goal, for timid play to be optimal, it suffices, but is not necessary, that no win probability be less than one-half. A condition that is both necessary and sufficient is provided.

Consider a queueing system where the input traffic consists of background traffic, modeled by a Markov Arrival Process, and foreground traffic modeled by N ≥ 1 homogeneous on–off sources. The queueing system has an increasing and concave service rate, which includes as a particular case multiserver queueing systems. Both the infinite-capacity and the finite-capacity buffer cases are analyzed. We show that the queue length in the infinite-capacity buffer system (respectively, the number of losses in the finite-capacity buffer system) is larger in the increasing convex order sense (respectively, the strong stochastic order sense) than the queue length (respectively, the number of losses) of the queueing system with the same background traffic and M N homogeneous on–off sources of the same total intensity as the foreground traffic, where M is an arbitrary integer. As a consequence, the queue length and the loss with a foreground traffic of multiple homogeneous on–off sources is upper bounded by that with a single on–off source and lower bounded by a Poisson source, where the bounds are obtained in the increasing convex order (respectively, the strong stochastic order). We also compare N ≥ 1 homogeneous arbitrary two-state Markov Modulated Poisson Process sources. We prove the monotonicity of the queue length in the transition rates and its convexity in the arrival rates. Standard techniques could not be used due to the different state spaces that we compare. We propose a new approach for the stochastic comparison of queues using dynamic programming which involves initially stationary arrival processes.

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.

We consider a discounted cost Markov decision process with a constraint. Relating this to a vector-valued Markov decision process, we prove that there exists a constrained optimal randomized semistationary policy if there exists at least one policy satisfying a constraint. Moreover, we present an algorithm by which we can find the constrained optimal randomized semistationary policy, or we can discover that there exist no policies satisfying a given constraint.

In this paper we compare the variance of functions of random variables and functionals of point processes. Specifically we give sufficient conditions on two random variables X and Y under which the variances var f(X) and var f(Y) of the function f of these random variables can be compared. For example we show that if X is smaller than Y in the shifted-up mean residual life and in the usual stochastic order, then var f(X) ≤ var f(y) for all increasing convex functions f, whenever these variances are well defined. In the context of point processes we compare the variances var Φ(M) and var Φ(N) of the functional Φ of two point processes M = {M(t), t ≥ 0} and N = {N(t), t ≥ 0}. We provide sufficient conditions under which these variances can be compared. Specifically we consider comparisons between (i) two renewal processes and between (ii) two (homogeneous or nonhomogeneous) Poisson processes. For example we show that for any nonhomogeneous Poisson process N with a rate function bounded from above by λ and from below by μ and two homogeneous Poisson processes L and M with rates λ and μ, respectively, var Φ (L) ≤ var Φ (N) ≤ var Φ (M) for any functional Φ that is increasing directionally convex in the event times, whenever these variances are well defined. This, for example, implies that if Tnis the nth event time of N, then n/λ2 ≤ var (Tn) ≤ n/μ2. Some applications of these results are given.

The paper treats data compression from the viewpoint of probability theory where a certain error probability is tolerable. We obtain bounds for the minimal rate given an error probability for blockcoding of general stationary ergodic sources. An application of the theory of large deviations provides numerical methods to compute for memoryless sources, the minimal compression rate given a tolerable error probability. Interesting connections between Cramer's functions and Shannon's theory for lossy coding are found.

We consider a polling system with a finite number of stations fed by compound Poisson arrival streams of customers asking for service. A server travels through the system. Upon arrival at a nonempty station i, say, with x > 0 waiting customers, the server tries to serve there a random number B of customers if the queue length has not reached a random level C < x before the server has completed the B services. The random variable B may also take the value ∞ so that the server has to provide service as long as the queue length has reached size C. The distribution Hi, x of the air (B, C) may depend on i and x while the service time distribution is allowed to depend on i. The station to be visited next is chosen among some neighbors according to a greedy policy. That is to say that the server always tries to walk to the fullest station in his well-defined neighborhood. Under appropriate independence assumptions two conditions are established that are sufficient for stability and sufficient for instability. Some examples will illustrate the relevance of our results.

We explicitly give the probability mass function and the probability generating function of the first k-record index for a sequence of independent and identically distributed random variables that take on a finite set of possible values. We also compute its factorial moments.

We show how the importance sampling identity can often be used to efficiently bound tail probabilities, illustrating with the normal, Poisson, and gamma random variables.

We give conditions on the optimality of an index policy for multiarmed bandits when arms expire independently. We also give a new simple proof of the optimality of the Gittins index policy for the classic multiarmed bandit problem.

In this paper we discuss some properties of the reversed hazard rate function. This function has been shown to be useful in the analysis of data in the presence of left censored observations. It is also natural in discussing lifetimes with reversed time scale. In fact, ordinary hazard rate functions are most useful for lifetimes, and reverse hazard rates are natural if the time scale is reversed. Mixing up these concepts can often, although not always, lead to anomalies. For example, one result gives that if the reversed hazard rate function is increasing, its interval of support must be (—∞, b) where b is finite. Consequently nonnegative random variables cannot have increasing reversed hazard rates. Because of this result some existing results in the literature on the reversed hazard rate ordering require modification.

Reversed hazard rates are also important in the study of systems. Hazard rates have an affinity to series systems; reversed hazard rates seem more appropriate for studying parallel systems. Several results are given that demonstrate this. In studying systems, one problem is to relate derivatives of hazard rate functions and reversed hazard rate functions of systems to similar quantities for components. We give some results that address this. Finally, we carry out comparisons for k-out-of-n systems with respect to the reversed hazard rate ordering.

We consider several models of computer disk access and show that in many cases greedy policies, such as the nearest server policy, minimize the process of distances traveled by heads on circular, spherical, or linear data media. This minimization is in the joint stochastic or lower orthant sense.

This note presents an efficient algorithm for the simulation of the number of invariant positions in a random permutation of the integers 1,..., n. An application to the famous matching problem of Montmort is discussed.

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.

This paper deals with evaluation and optimization of polling systems with time limits. Performance measures are evaluated with the power-series algorithm, a flexible technique for computing performance measures for multiqueue systems. The constant time limits are approximated by Erlang distributed variables. The algorithm is extended to compute derivatives of performance measures. This allows for optimization of cost functions with respect to the mean values of the time limits by gradient methods. Several properties of the optimal time limits are revealed by the numerical solution of various optimization problems.

A significant amount of recent research has been focused on the stability of multiclass open networks of queues (MONQs). It has been shown that these networks may be unstable under various queueing disciplines even when at each one of the nodes the arrival rate is less than the service rate. Clearly, in such cases the expected delay and the expected number of customers in the system are infinite. In this paper we propose a new class of scheduling rules that can be used in multiclass queueing networks. We refer to this class as the stable shortfall-based priority (SSBP) rules. This SSBP class itself belongs to a larger class of rules, which we refer to as the shortfall-based priority (SBP) rules. SBP is a generalization of the standard non-preemptive priority rule in which customers of the same priority class are served first-come, first-served (FCFS). Rules from SBP can mimic FCFS as well as the so-called strict or head-of-the-line priority disciplines. We show that the use of any rule from the SSBP class ensures stability in a broad class of MONQs found in practice. We proceed with the construction of a sample path inequality for the work done by an SSBP server and show how this inequality can be used to derive upper bounds for the delay when service times are bounded. Bounds for the expected delay of each class of customers in an MONQ are then obtained under the assumptions that the external arrival processes have i.i.d. interarrival times, the routings are deterministic and the service times at each step of the route are bounded. In order to derive these bounds for the average delay in an MONQ we make use of some of the classical ideas of Kingman.

This paper deals with the following discrete-time optimal stopping problem. For fixed search costs, a random offer, w ~ F(w), will be found for each time. This offer is either accepted, rejected, or “reserved” for recall later. The reserving cost for any offer depends on its value, regardless of how long the offer is reserved. The objective is to maximize the expected discounted net profit, provided that an offer must be accepted. The major finding is that no previously reserved offer should be accepted prior to the deadline of the search process.