RUNS, SCANS AND URN MODEL DISTRIBUTIONS: A UNIFIED MARKOV CHAIN APPROACH

M. V. KOUTRAS AND V. A. ALEXANDROU

Department of Mathematics, University of Athens, Panepistemiopolis, Athens 157 84, Greece

(Received June 6, 1994; revised December 2, 1994)

Abstract. This paper presents a unified approach for the study of the exact distribution (probability mass function, mean, generating functions) of three types of random variables: (a) variables related to success runs in a sequence of Bernoulli trials (b) scan statistics, i.e. variables enumerating the moving windows in a linearly ordered sequence of binary outcomes (success or failure) which contain prescribed number of successes and (c) success run statistics related to several well known urn models. Our approach is based on a Markov chain imbedding which permits the construction of probability vectors satisfying triangular recurrence relations. The results presented here cover not only the case of identical and independently distributed Bernoulli variables, but the non-identical case as well. An extension to models exhibiting Markov dependence among the successive trials is also discussed in brief.

Key words and phrases: Success runs, scan statistics, urn models, Markov chains, triangular multidimensional recurrence relations, distributions of order k.