Title: Learning mixtures of markov chains
Speaker: Sudipto Guha, University of Pennsylvania
Date: December 1, 2003 3:30-4:30pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
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