SOONER AND LATER WAITING TIME PROBLEMS IN A TWO-STATE MARKOV CHAIN

MASAYUKI UCHIDA AND SIGEO AKI

Department of Mathematical Science, Faculty of Engineering Science, Osaka University, Machikaneyama-cho, Toyonaka, Osaka 560, Japan

(Received August 31, 1994; revised February 8, 1995)

Abstract. Let X_{1}, X_{2}, … be a time-homogeneous {0, 1}-valued Markov chain. Let F_{0} be the event that l runs of “0” of length r occur and let F_{1} be the event that m runs of “1” of length k occur in the sequence X_{1}, X_{2}, . . .. We obtained the recurrence relations of the probability generating functions of the distributions of the waiting time for the sooner and later occurring events between F_{0} and F_{1} by the non-overlapping way of counting and overlapping way of counting. We also obtained the recurrence relations of the probability generating functions of the distributions of the sooner and later waiting time by the non-overlapping way of counting of “0”-runs of length r or more and “1”-runs of length k or more.

Key words and phrases: Sooner and later problems, discrete distribution, Markov chain, recurrence relations, overlapping, non-overlapping, non-over-lapping “0”-runs of length r or more, generalized probability generating function.