Waiting Time Problems in a Two-State Markov Chain

Let F₀ be the event that l₀ 0-runs of length k₀ occur and F₁ be the event that l₁ 1-runs of length k₁ 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₀ and F₁ 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.