Every realization of a Poisson line process is a set of lines which subdivides the plane into a population of non-overlapping convex polygons. To explore the unknown statistical features of this population, an alternative stochastic construction of random polygons is developed. This construction, which is based on an alternating sequence of random angles and side lengths, provides a fast simulation method for obtaining a random sample from the polygon population. For the isotropic case, this construction is used to obtain a random sample of 2500000 polygons, providing the most precise estimates to date of some of the unknown distributional characteristics.

In this paper we obtain an upper bound for the maximum of random fields of the form , where CP denotes circles of fixed radius and dW(P′) is a plane white noise field.

The results presented are obtained by means of successive steps involving Slepian's lemma for random fields, inequalities on Brownian fields and planar stochastic integrals.

A Poisson limit theorem for sums of dissociated 0–1 random variables is refined by deriving the first terms in an asymptotic expansion. The most natural refinement does not remove all the first-order error in a number of applications to tests of clustering, and a further approximation is derived which gives excellent results in practice. The proofs are based on the technique of Stein and Chen.

We consider the problem of approximating the stationary distribution of a positive-recurrent Markov chain with infinite transition matrix P, by stationary distributions computed from (n × n) stochastic matrices formed by augmenting the entries of the (n × n) northwest corner truncations of P, as n →∞.

A continuum structure function γ is a non-decreasing mapping from the unit hypercube to the unit interval. Block and Savits (1984) use the sets and to determine bounds on the distribution of γ (X) when X is a vector of associated random variables. It is shown that, if γ admits of a modular decomposition, improved bounds may be obtained.

We consider the relative error of a tail function when this is approximated by y–α using an estimator of Hill's for α. The results combine recent work of Davis and Resnick on tail estimation with Anderson's work on large deviations in extreme-value theory. Treating separately the domains of attraction of Φα and Λ, we obtain general conditions for the relative error to tend to 0 as u →∞, y → ∞ simultaneously. The results serve as warning against the automatic extrapolation of estimates based on extreme-value approximations.

Keilson [7] showed that for a birth-death process defined on non-negative integers with reflecting barrier at 0 the first-passage-time density from 0 to N (N to N + 1) has Pólya frequency of order infinity (is completely monotone). Brown and Chaganty [3] and Assaf et al. [1] studied the first-passage-time distribution for classes of discrete-time Markov chains and then produced the essentially same results as these through a uniformization. This paper addresses itself to an extension of Keilson's results to classes of Markov chains such as time-reversible Markov chains, skip-free Markov chains and birth-death processes with absorbing states. The extensions are due to the spectral representations of the infinitesimal generators governing these Markov chains. Explicit densities for those first-passage times are also given.

Uniformization permits the replacement of a semi-Markov decision process (SMDP) by a Markov chain exhibiting the same average rewards for simple (non-randomized) policies. It is shown that various anomalies may occur, especially for stationary (randomized) policies; uniformization introduces virtual jumps with concomitant action changes not present in the original process. Since these lead to discrepancies in the average rewards for stationary processes, uniformization can be accepted as valid only for simple policies.

We generalize uniformization to yield consistent results for stationary policies also. These results are applied to constrained optimization of SMDP, in which stationary (randomized) policies appear naturally. The structure of optimal constrained SMDP policies can then be elucidated by studying the corresponding controlled Markov chains. Moreover, constrained SMDP optimal policy computations can be more easily implemented in discrete time, the generalized uniformization being employed to relate discrete- and continuous-time optimal constrained policies.

Heuristic solution methods for combinatorial optimization problems are often based on local neighborhood searches. These tend to get trapped in a local optimum and the final result is often heavily dependent on the starting solution. Simulated annealing methods attempt to avoid these problems by randomizing the procedure so as to allow for occasional changes that worsen the solution. In this paper we provide probabilistic analyses of different designs of these methods.

We consider some linear regression models Y = Σα lfl(z) + X, where X is an autoregressive (AR) process. The residuals estimate the i.i.d. innovations sequence which drives the AR process. We then consider the partial sum process of the residuals and show they converge to Brownian bridges in certain cases. Some remarks are also made on similar processes when differencing is first applied to remove trends. When an AR process is differenced the residual partial sum can be asymptotically a random polynomial.

We study monotone and associated Markov chains on finite partially ordered state spaces. Both discrete and continuous time, and both time-homogeneous and time-inhomogeneous chains are considered. The results are applied to binary and multistate reliability theory.

A general method to obtain insensitive upper and lower bounds for the stationary distribution of queueing networks is sketched. It is applied to an overflow model. The bounds are shown to be valid for service distributions with decreasing failure rate. A characterization of phase-type distributions with decreasing failure rate is given. An approximation method is proposed. The methods are illustrated with numerical results.

We consider general queueing models dealing with multiple classes of customers and address the question under what conditions and in what (stochastic) sense the marginal increase in various performance measures, resulting from the addition of a new class of customers to an existing system, is larger than if the same class were added to a system dealing with only a subset of its current customer base.

Our results enhance our understanding of the dependence of various performance measures with respect to the composition of the customer base. In addition they translate readily into convexity results in an (appropriately defined) arrival rate.

This paper examines a general performance measure for queueing systems. This criterion reflects both the mean and the variance of sojourn times; the standard deviation is a special case. The measure plays a key role in certain production models, and it should be useful in a variety of other applications.

We focus here on convexity properties of an approximation of the measure for the M/G/c queue. For c ≧ 2 we show that this quantity is convex in the arrival rate. Assuming the service rate acts as a scale factor in the service-time distribution, the measure is convex in the service rate also.

In this paper, the extremal properties of the ergodic sojourn times in G/G/1queues under various service disciplines are studied in terms of the convex ordering. It is shown that among work-conserving non-preemptive service disciplines that are service time independent, the FIFO and the LIFO service disciplines provide the minima and the maxima, respectively, of the ergodic sojourn times for any G/G/1 queue. For G/M/1 queues, this class of work-conserving service disciplines is extended to include preemptive/resume disciplines. In this case the FIFO and LIFO-P (preemptive/resume LIFO) service disciplines attain the minima and maxima, respectively. These extend results of Durr (1971), Kingman (1962) and a recent result of Ramaswami (1984). Further results are obtained for G/Em/1 and G/D/1 queues.

For a GI/G/1 queue we derive new lower and uper bounds on the expected stationary waiting time which are a function of more than the first two moments of the inter-arrival and service times. When the probability for a delay is low, the bounds tend to be better than other bounds. This is illustrated in an example of a Uniform/Uniform/1 queue.

This paper studies the GI/G/1 queueing system assuming that customers have service times depending on the queue size and also that they are served in accordance with the preemptive-resume last-come–first-served queue discipline. Expressions are given for the limiting distribution of the queue size and the remaining durations of the corresponding services, when the system is considered at arrival epochs, at departure epochs and continuously in time. Also these results are applied to some particular cases of the above queueing system.

Let where {Zn, ℱn} is a non-negative submartingale satisfying Ei(Zn log Zn) →∞. It is shown that When {Zn} is a simple critical Galton–Watson process and is slowly varying at∞, conditions are given ensuring that This gives an alternative proof of a result recently established by Kammerle and Schuh.

For optimal stopping problems in which the player is allowed to choose the order of the random variables as well as the stopping rule, a notion of order equivalence is introduced. It is shown that different (non-degenerate) distributions cannot be order-equivalent.

This result unifies and generalizes two theorems of a similar nature recently obtained by Hill and Hordijk (1985).

A continuum structure function is a non-decreasing mapping from the unit hypercube to the unit interval. A definition of the reliability importance, ℛi(α) say, of component i at system level α(0 < α ≦ 1) is proposed. Some properties of this function are deduced, in particular conditions under which and conditions under which ℛi(α) is positive (0 < α < 1).