A unified methodology for computing distributions associated with patterns in Markov sequences is discussed. An auxiliary Markov chain is developed such that events in an original sequence correspond to the auxiliary chain lying in a class of states. Once the auxiliary chain is set up, probabilities of interest may be computed in a simple recursive fashion. Finite automata are used to help minimize the number of states in the auxiliary chain. We highlight the variety of distributions that may be computed in this manner, including those for statistics of hidden states of probabilistic graphical models used to label observed data. Some future research directions will be given.
Return to Biostatistics Working Group