Skip to yearly menu bar Skip to main content


On Mixtures of Markov Chains

Rishi Gupta · Ravi Kumar · Sergei Vassilvitskii

Area 5+6+7+8 #93

Keywords: [ (Other) Unsupervised Learning Methods ]


We study the problem of reconstructing a mixture of Markov chains from the trajectories generated by random walks through the state space. Under mild non-degeneracy conditions, we show that we can uniquely reconstruct the underlying chains by only considering trajectories of length three, which represent triples of states. Our algorithm is spectral in nature, and is easy to implement.

Live content is unavailable. Log in and register to view live content