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 X_{1}, X_{2}, … 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 P_{i} = “a_{i,1}a_{i,2} ⋯ a_{i,k_{i}}” the pattern of some length k_{i}, and E_{i} denotes the event that the pattern P_{i} occurs in the sequence X_{1}, X_{2}, . . .. 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 {E_{i}}_{i=0}^{∞}. 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.