The Taub Faculty of Computer Science Events and Talks

A fundamental quantity associated with a Markov chain is its mixing time. Can we estimate this quantity empirically from a single long sample path? This might appear to present an impossible circularity, since the mixing time controls our ability to infer global properties of the chain from a single path -- and this is the very unknown quantity we're trying to estimate! We present a way out of this conundrum, providing a fully empirical procedure, with efficiently computable confidence intervals.Now suppose we want to learn the full Markov chain -- that is, estimate the transition probabilities. The minimax sample complexity is well-understood in the i.i.d. case, but for Markov chains, almost nothing was known until very recently. I'll present some of our latest results in this area. Finally, suppose we wanted to test the identity of a Markov chain against a known reference chain. This problem is simpler than learning; in fact, it requires no assumptions on the unknown chain whatsoever! Here too we give minimax rates. Joint work with Daniel Hsu, Csaba SzepesvᲩ, David Levin, Yuval Peres, and Geoffrey Wolfer.

Bio:
Dr. Kontorovich is an associate professor at Computer Science Department in Ben-Gurion University. He received his B.Sc in Mathematics, Applied and Computational Mathematics from Princeton University (with Honors) and his M.Sc. in Computer Science from Carnegie Mellon University. Dr. Kontorovich received his Ph.D.in Computer Science from Carnegie Mellon University under the supervision of Prof. John Lafferty. Currently, his main area of research is theoretical machine learning: probability, statistics, Markov chains, metric spaces.