ON GENERATING FUNCTIONS OF WAITING TIME PROBLEMS
FOR SEQUENCE PATTERNS OF DISCRETE RANDOM
VARIABLES

MASAYUKI UCHIDA

The Institute of Statistical Mathematics,
4-6-7 Minami-Azabu, Minato-ku, Tokyo 106-8569, Japan

(Received July 31, 1996; revised August 28, 1997)

Abstract.    Let X1, X2,... be a sequence of independent and identically distributed random variables, which take values in a countable set S = { 0,1,2, ... }. By a pattern we mean a finite sequence of elements in S. For every i =0,1,2,..., we denote by Pi = ``ai,1ai,2 ··· ai,ki'' the pattern of some length ki, and Ei denotes the event that the pattern Pi occurs in the sequence X1, X2, .... In this paper, we have derived the generalized probability generating functions of the distributions of the waiting times until the r-th occurrence among the events {Ei}i=0\infty. We also have derived the probability generating functions of the distributions of the number of occurrences of sub-patterns of length l (l < k) until the first occurrence of the pattern of length k in the higher order Markov chain.

Key words and phrases:    Sequence patterns, runs, sooner and later problems, r-th occurrence problem, discrete distribution of order k, generalized probability generating function, higher order Markov chain.

Source ( TeX , DVI , PS )