WAITING TIME PROBLEMS IN A TWO-STATE MARKOV CHAIN

QING HAN AND SIGEO AKI

Department of Informatics and Mathematical Science, Graduate School of Engineering Science, Osaka University, 1-3 Machikaneyama-cho, Toyonaka, Osaka 560-8531, Japan

(Received May 18, 1998; revised August 6, 1999)

Abstract. Let F_{0} be the event that l_{0} 0-runs of length k_{0} occur and F_{1} be the event that l_{1} 1-runs of length k_{1} occur in a two-state Markov chain. In this paper using a combinatorial method and the Markov chain imbedding method, we obtained explicit formulas of the probability generating functions of the sooner and later waiting time between F_{0} and F_{1} by the non-overlapping, overlapping and “greater than or equal” enumeration scheme. These formulas are convenient for evaluating the distributions of the sooner and later waiting time problems.

Key words and phrases: Waiting time problems, discrete distributions of order k, Markov chain, Markov chain imbedding method, probability generating function.