We study first-passage percolation on the random graph Gp(N) with exponentially distributed weights on the links. For the special case of the complete graph, this problem can be described in terms of a continuous-time Markov chain and recursive trees. The Markov chain X(t) describes the number of nodes that can be reached from the initial node in time t. The recursive trees, which are uniform trees of N nodes, describe the structure of the cluster once it contains all the nodes of the complete graph. From these results, the distribution of the number of hops (links) of the shortest path between two arbitrary nodes is derived.

We generalize this result to an asymptotic result, as N → ∞, for the case of the random graph where each link is present independently with a probability pN as long as NpN/(log N)3 → ∞. The interesting point of this generalization is that (1) the limiting distribution is insensitive to p and (2) the distribution of the number of hops of the shortest path between two arbitrary nodes has a remarkable fit with shortest path data measured in the Internet.

Steady-state availability has long been a popular descriptor of effectiveness for repairable systems because it captures both the operability and repairability aspects of the system. A related measure of effectiveness is the availability of continuous service, which is particularly relevant for safety critical applications. In this article, two different measures of this quantity are described for a repairable system whose state is described by an ergodic finite-state-space continuous-time Markov chain. Using these ideas, formulas for computing system long-run mean time between failures and the long-run system reliability function are derived.

Bounds for aging properties in mixtures and their derivatives are provided. Such bounds allow control of the behavior of those characteristics through the aging properties of the distributions in the mixture. We also obtain some results for discrete mixtures involving exponential distributions. In addition, well-known mixture-preserving properties for several distribution classes are derived with little algebraic complexity.

An operational profile describes, in a probabilistic way, how a software is utilized by its users. It makes the testing procedure more realistic and efficient. We consider a model where the software is tested sequentially in all of the operations that it is designed to perform. The stochastic and deterministic model parameters involving costs and failures all depend on the operations. In particular, the failure process generated by each fault is quite general and debugging is not necessarily perfect. Our aim is to find the optimal testing durations in all of the operations in order to minimize the total expected cost. This problem leads to an interesting nonlinear programming formulation that can be solved using well-known procedures in convex optimization.

It is well known that mixtures of decreasing failure rate (DFR) distributions are always DFR. It turns out that, very often, mixtures of increasing failure rate (IFR) distributions can decrease at least in some intervals of time. Usually, this property can be observed asymptotically as t → ∞. In this article, several types of underlying continuous IFR distribution are considered. Two models of mixing are studied: additive and multiplicative. The limiting behavior of a mixture failure rate function is analyzed. It is shown that the conditional characteristics (expectation and variance) of the mixing parameter are crucial for the limiting behavior. Several examples are presented and possible generalizations are discussed.

We study deviation matrices of birth–death processes. This is relevant to the control of multidimensional queueing systems. We give an algorithm for computing deviation matrices for birth–death processes. As an application, we compute them explicitly for the M/M/s/N and M/M/s/∞ queues.

The Waxman graphs are frequently chosen in simulations as topologies resembling communications networks. For the Waxman graphs, we present analytic, exact expressions for the link density (average number of links) and the average number of paths between two nodes. These results show the similarity of Waxman graphs to the simpler class G>p(N). The first result enables one to compare simulations performed on the Waxman graph with those on other graphs with same link density. The average number of paths in Waxman graphs can be useful to dimension (or estimate) routing paths in networks. Although higher-order moments of the number of paths in Gp(N) are difficult to compute analytically, the probability distribution of the hopcount of a path between two arbitrary nodes seems well approximated by a Poisson law.

In view of the growing importance of reversed hazard rate (RHR) in reliability analysis and stochastic modeling, we have considered different implicative relationships with respect to the monotonic behavior of RHR. In that context, a few characterizing properties have also been presented based on expected inactivity time.

This article concerns Markov decision chains with finite state and action spaces, and a control policy is graded via the expected total-reward criterion associated to a nonnegative reward function. Within this framework, a classical theorem guarantees the existence of an optimal stationary policy whenever the optimal value function is finite, a result that is obtained via a limit process using the discounted criterion. The objective of this article is to present an alternative approach, based entirely on the properties of the expected total-reward index, to establish such an existence result.

Let X1:n ≤ X2:n ≤ ··· ≤ Xn:n denote the order statistics of a set of independent and not necessarily identically distributed random variables X1,..., Xn. Under mild assumptions, it is shown that Xk−1:n−1 ≤lrXk:n for k = 2,..., n if X1 ≤lrX2 ≤lr ··· ≤lrXn and that Xk:n ≤lrXk:n−1 for k = 1,..., n − 1 if X1 ≥lrX2 ≥lr ··· ≥lrXn, where ≤lr denotes the likelihood ratio order. Concerning the mean residual life order (≤mrl), it is shown that Xn−1:n−1 ≤mrlXn:n if Xj ≤mrlXn for j = 1,..., n − 1. Two counterexamples are also given to illustrate that Xk−1:n−1 ≤mrlXk:n in this case is, in general, not true for k < n.

Let X1,..., Xn be independent exponential random variables with possibly different scale parameters. Kochar and Korwar [J. Multivar. Anal. 57 (1996)] conjectured that, in this case, the successive normalized spacings are increasing according to hazard rate ordering. In this article, we prove this conjecture in the case of a single-outlier exponential model when all except one of the parameters are identical. We also prove that the spacings are more dispersed and larger in the sense of hazard rate ordering when the vector of scale parameters is more dispersed in the sense of majorization.

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.

In this article, we give some results on the preservation of orderings between the components under the formation of coherent systems with different structures. We consider the stochastic, failure rate, reversed failure rate, and likelihood ratio orderings to compare two coherent structures formed from a set of components and from two sets of components, in both cases, when components are independent and either identically distributed or not necessarily identically distributed. As a consequence, we get new stochastic comparisons of systems with different k-out-of-n structures, and some results of partial orderings given by other authors may be also obtained from ours.