An important problem in computer communication systems is the design of finite buffers such that a small overflow probability is achieved. For the case of batch input and general service times, we derive an asymptotically exponential expansion for the overflow probability when the batch-arrival process is Poissonian. Next, the results are extended to handle applications with periodic service opportunities and random interruptions in service. A convenient model to handle these types of applications is the versatile queueing model with exceptional first services.

The manipulations and basic results of stochastic decision theory are introduced. The manipulations of idempotence, transposition, and repetition, introduced for deterministic decision trees, can be used to manipulate stochastic trees. However, there are two major differences. First, in order to obtain a complete set of manipulations it is necessary to introduce an additional rule called indifference. Second, these identities must be treated as rules of inference. Not all the rules can be soundly applied in both directions; in particular, idempotence is a one-way rule.

A manipulation of a stochastic decision tree not only alters the structure of the tree, but also the probability distributions associated with the tree. This allows probability calculation to be viewed as structural manipulation. In particular, a retrieval corresponds to a conditional probability calculation. The algorithm for doing this calculation has, therefore, many applications. For example, the solution to the classical state-estimation problem and the retrieval of information from probabilistic or uncertain knowledge bases may both be viewed as an application of this algorithm.

The main result of this paper is that these manipulations are complete and sound. In order to prove this result, it is necessary to have a semantic setting for these theories. The setting chosen is the category of description spaces which is a generalization of the category of bounded measure spaces with maps which do not increase measure. The proof of this result exploits the retrieval properties of stochastic terms and its relationship to conditional probability calculations in the models.

To find zeros or locate maximum values of a regression function with noisy measurements, a commonly used algorithm is the RM or KW procedure. In various applications, the dimensionality of the problems involved might be quite large. As a result, enormous memory space and extensive computation time may be needed. Motivated by the recent progress in stochastic approximation methods for decentralized and distributed computing, a parallel stochastic approximation algorithm is developed in this paper. The essence is to take advantage of state-space decompositions, and to exploit the opportunities provided by parallel processing and asynchronous communication. In lieu of utilizing a single processor as in the classical cases, a number of parallel processors are employed to solve the underlying problem in a cooperative way. First, the large dimensional vector is partitioned into a number of subvectors with relatively small dimension, then each of the subvectors is assigned to one of the processors. The processors compute and communicate in an asynchronous manner and at random times. Under rather weak conditions, the global convergence of the parallel algorithm is obtained via the methods of randomly varying truncations.

The distribution of upward first passage times in skip-free Markov chains can be expressed solely in terms of the eigenvalues in the spectral representation, without performing a separate calculation to determine the eigenvectors. We provide insight into this result and skip-free Markov chains more generally by showing that part of the spectral theory developed for birth-and-death processes extends to skip-free chains. We show that the eigenvalues and eigenvectors of skip-free chains can be characterized in terms of recursively defined polynomials. Moreover, the Laplace transform of the upward first passage time from 0 to n is the reciprocal of the nth polynomial. This simple relationship holds because the Laplace transforms of the first passage times satisfy the same recursion as the polynomials except for a normalization.

We analyze the optimal preemptive sequencing of n jobs on two machines to minimize expected total flow time. The running times of the jobs are independent samples from the distribution Pr(X = 1) = p, Pr(X = κ + 1) = 1 − p. We verify that the shortest-expected-remaining-processing-time (SERPT) policy, which is optimal for independent and identically distributed (i.i.d.) running times with a monotone hazard-rate distribution, is not optimal for this distribution. However, we prove that if p ≥ 1/κ, then the number of decisions where SERPT and an optimal policy disagree is bounded by a constant independent of n. For p < 1/k, we prove that the expected number of such decisions has a similar bound. In addition, bounds on the expected increase in flow times under SERPT are derived; these bounds are also independent of n.

Several models of maintenance of repairable multicomponent systems, subjected to a random environment, are introduced in this paper. For each model, it is shown how various probabilistic quantities of interest are “monotone” as a function of the probability law of the environment or as a function of other parameters of the model. Also, conditions are given which imply the positive dependence of the failure times, or of the counters of the number of failures, in these models.

Recently, the conjecture that the expected number of tests is nondecreasing in the failure probability for binomial group testing has been proved. The proof has also been extended to three models of multiaccess systems. However, probabilistic algorithms are used as a crucial part of these proofs. In this paper, we give conceptually simpler new proofs without using probabilistic algorithms. We also extend the result to a more general model where the number of tests is replaced by a cost function.

Consider the problem of simulating w independent Bernoulli random variables X1 X2, …, Xw, so that {Xk = 1 = zk}, using a computer with a w–bit word length. A conventional method would be to generate w pseudorandom numbers uniform in [0,1], then “threshold” them with the values zk. This paper proposes an alternative method that only requires c pseudorandom numbers, where c is large enough so that the numbers zk are approximated satisfactorily with c bits. In many cases, c ≪ w and so fewer pseudorandom numbers are required. The new method is tested against the conventional method by employing both in simulations to estimate the reliabilities of several coherent systems. The results show that the new method is much faster.

Compensator or dual predictable projection is one of the main concepts of the general theory of stochastic processes, established by a French probabilistic school. In general, it is a considerably abstract concept and difficult to grasp. But in the Poisson case, it affords very powerful tools to calculate the expectation of certain stochastic integrals with respect to Poisson processes and random measures. Naturally, compensators can be used to solve certain problems of applied probability, involved in Poisson processes and random measures. In this direction, Brémaud and Jacod [1] had used the compensators of Poisson processes to solve the optimal dispatching problem, investigated by Ross [4] originally. In this note, we use the compensators of Poisson random measures to solve two optimal stopping problems: house selling and the burglary problem. The solutions are simple and completely rigorous as well. Our objective is to attract more attention to this method of using compensators. To facilitate reading, we introduce some fundamental results on marked point processes and Poisson random measures and their compensators.

Previous studies have examined the behavior of outlier detection rules for symmetric distributions that label as “outside” any observations that fall outside the interval [FL – k(Fu – FL), Fu + k(Fu – FL)], where FL and FU are functions of the order statistics estimating the 0.25 and 0.75 quantiles of the distribution underlying the i.i.d. sample. A measure of the performance of this type of rule is the “some-outside rate” per sample computed with respect to a given (usually Gaussian) null distribution. The “some-outside rate” (SOR) per sample is the probability that the sample will contain one or more observations labeled as “outside,” given that the null distribution is the true distribution. In this paper, asymptotic expansions of k = kn as a function of n that guarantee an asymptotically constant, prespecified SOR are given for a variety of symmetric null distributions including the Gaussian, double exponential, logistic, and Cauchy distributions. The main theorem also applies to the case of a nonsymmetric null distribution by slightly modifying the labeling rule.