Discrete renewal theory is generalized to study the occurrence of a collection of patterns in random sequences, where a renewal is defined to be the occurrence of one of the patterns in the collection which does not overlap an earlier renewal. The action of restriction enzymes on DNA sequences provided motivation for this work. Related results of Guibas and Odlyzko are discussed.

A distribution R is ‘more dispersed' than a distribution P if any two quantiles of R are more widely separated than the corresponding quantiles of P. Lewis and Thompson (1981) prove that a non-degenerate distribution P is strongly unimodal if and only if it is ‘dispersive', i.e. if P∗ Q 1 is more dispersed than P∗ Q 2 whenever Q1 is more dispersed than Q 2 . For P admitting a positive Lebesgue density, we prove that P is strongly unimodal if and only if P ∗ Q is more dispersed than P for every distribution Q. Hence the latter property also characterizes the dispersivity of P.

This paper deals with special cases of stochastic flowshop, no-wait, scheduling. n jobs have to be processed by m machines . The processing time of job Ji on machine Mj is an independent random variable Ti . It is possible to sequence the jobs so that , . At time 0 the realizations of the random variables Ti , (i are known. For m (m ≧ 2) machines it is proved that a special SEPT–LEPT sequence minimizes the expected schedule length; for two (m = 2) machines it is proved that the SEPT sequence minimizes the expected sum of completion times.

It is shown that any phase-type distribution can be represented as a proper mixture of two distinct phase-type distributions. Using different terms, it is shown that the class of phase-type distributions does not include any extreme ones. A similar result holds for the subclass of upper-triangular phase-type distributions.