Dec 01:  Learning Mixtures of Markov Chains.
               Sudipto Guha
                   Univ. of Penn.
 
We consider the problem of inferring a ``mixture of Markov chains'' based on
observing a stream of interleaved outputs from these chains. In the
first of several possible variants, one we consider, the mixing process
chooses one of the Markov chains independently according to a fixed set of
probabilities at each step, and only that chain makes a transition and
outputs its new state. For this case, when the individual Markov chains have
disjoint state sets we show that a polynomially-long stream of observations
is sufficient to infer arbitrarily good approximations to the correct chains.

We also explore a generalization where the mixing probabilities are
determined by the chain of the last output state. When the state sets are not
disjoint, for the case of two Markov chains, we show how we can infer them
under a technical condition.

Joint work with T. Batu, S. Kannan

--------------------------------------------------------------------------