Waiting Time Distribution for Pattern Occurrence in a Constrained Sequence: an Embedding Markov Chain Approach
Gregory Nuel
Abstract
In this paper we consider the distribution of a pattern of interest
in a binary random $(d,k)$-sequence generated by a Markov
source. Such constrained sequences are frequently encountered in
communication systems. Unlike previous approach based on generating
function we have chosen here to use Markov chain embedding
techniques. Doing so, we get both previous results (sequence
constrained up to the $r^\text{th}$ occurrence) and new ones
(sequence constrained up to its end). We also provide in both cases
efficient algorithms that use only basic linear algebra. We then
compare our numerical results to previous ones and finally propose
several interesting extensions of our method which further
illustrate the usefulness of our approach: higher order Markov
chains, renewal occurrences rather than overlapping ones,
heterogeneous models, more complex patterns of interest and
multistate trial sequences.
Full Text: PDF PostScript