Topics in Markov Chains

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.