Computer Science Distinguished Colloquium: Alan Frieze, "Topics in Markov Chains"
Friday, October 5, 2018
Topics in Markov Chains
Professor of Mathematical Sciences
Carnegie Mellon University
Friday, October 5th 2018 11:00am CSIC 2117 Abstract: We give some examples on problems related to finite state Markov chains. Gerrymandering: There are many ways to choose a set of political districts. Let Ω denote the set of possible districtings. Some ω ∈ Ω are more favorable than others to one party. Fairness might dictate that one should try to select (near) uniformly from Ω. If one is presented with ω ∈ Ω, how does one determine whether it is likely that it has been chosen uniformly? We present a one sided test that will recognise when a presented ω is an outlier. It was used in a recent court case in Pennsylvania. Sampling and Counting: Markov chains “typically” have steady state distributions and can thus be used to generate samples from this distribution, provided the “mixing time” is small. Broder pioneered this approach in Computer Science in the context of approximating the permanent. We will do a mini-survey on this area. Cover Time: The cover time of a graph G is the maximum over vertices v ∈ V (G) of the expected time for a simple random walk to visit all vertices ofG, starting at v. We will review what we know about this question and present asymptotic characterizations of the cover time in a few regimes. Various parts of this talk are joint works with subsets of Colin Cooper, Wesley Pegden, and Tomasz Tkocz. Biography: Alan Frieze is a Professor of Mathematical Sciences at Carnegie-Mellon University; he was named a University Professor of CMU in 2017. His main research interest is Probabilistic Combinatorics and its applications in Theoretical Computer Science and Operations Research. He received a Fulkerson Prize in Discrete Mathematics (awarded by the American Mathematical Society and the Mathematical Programming Society), a Guggenheim Fellowship, an IBM Faculty Partnership Award, and a Professor Pazy Memorial Research Award (from the United States-Israel Binational Science Foundation). He is a SIAM Fellow, AMS Fellow, and Simons Fellow. He delivered a plenary talk at the International Congress of Mathematicians in 2014.