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.

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.

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.

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, 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.

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.

By using the martingale method, we show that thinning of an arbitrary point process produces independent thinned processes if and only if the original point process is (nonhomogeneous) Poisson. Thinning is a classical problem for point processes. It is well-known that independent homogeneous Poisson processes result from constant Bernoulli thinnings of homogeneous Poisson processes. In fact, the conclusion remains true for nonconstant Bernoulli thinnings of nonhomogeneous Poisson processes. processes. In fact, the conclusion remains true for nonconstant Bernoulli thinnings of nonhomogeneous Poisson processes. It is easy to see that the converse is also true, i.e., if the thinned processes are independent nonhomogeneous Poisson processes, so are the original processes. But if we only suppose the thinned processes are independent, nothing is concerned with their distribution law, the problem of whether or not the original processes are (nonhomogeneous) Poisson becomes interesting and challenging, which is the objective of this paper. It is considerably surprising for us to arrive at the affirmative answer. So far as this problem is concerned, the most work was done under the renewal assumption. For example, Bremaud [1] showed that for arbitrary delayed renewal processes, the existence of a pair of uncorrelated thinned processes is sufficient to guarantee that the original process is Poisson. It is natural that the mathematical tools to solve the problem in this case be typical ones for renewal theory, such as renewal equations and Laplace-Stieltjes transformations. Obviously, they are not available for nonrenewal processes. We find out that the martingale method is the most efficient one to solve this problem in the general case. More precisely, we use mainly the dual predictable projections of point processes. In fact, the distribution law of a point process is determined uniquely by its dual predictable projection (see [5]), and Ma [6] offered us a very useful criterion of independence of jump processes having no common jump time through their dual predictable projections. Based on these results, it is not a long way to arrive at the destination.

This paper is concerned with the problem of optimally scheduling a multiclass open queueing network with four single-server stations in which dynamic control policies are permitted. Under the assumption that the system is heavily loaded, the original scheduling problem can be approximated by a dynamic control problem involving Brownian motion. We reformulate and solve this problem and, from the interpretation of the solution, we obtain two dynamic scheduling policies for our queueing network. We compare the performance of these policies with two static scheduling policies and a lower bound via simulation. Our results suggest that under either dynamic policy the system, at least when heavily loaded, exhibits the form of resource pooling given by the solution to the approximating control problem. Furthermore, even when lightly loaded the system performs better under the dynamic policies than under either static policy.