6.856 — Randomized Algorithms David Karger Handout #22, November 20, 2000 — Homework 11, Due 11/27 1. For basic Markov chain practice, we prove three criteria for showing a given distribution is stationary. Note that when the stationary distribution is unique, these criteria become “if and only if” characterizations of the stationary distribution. Answers to some of these problems are in textbooks. Don’t use them. (a) Suppose that a Markov chain is doubly stochastic (all rows and columns sum to 1). Prove that the uniform distribution is stationary. (b) A Markov chain is time reversible if pij = pji (it follows the probability of a given state sequence occurring is equal to the probability of the reversal of that state sequence, so running time backwards doesn’t affect the distribution at all). Prove that the uniform distribution is stationary for any time-reversible Markov chain. (c) Prove that any distribution π satisfying πipij = πj pji (that is, the probability that the state starts at i and moves to j is equal to the probability of the reverse) is stationary. 2. The 3-coloring problem is to color the vertices of a graph with 3 colors such that the no edge has both endpoints the same color. This problem is NP-complete, so the focus has been on approximation algorithms. We will devise a partial solution. Any triangle in a 3-colorable graph must have all 3 vertices colored differently. Develop an algorithm to color the vertices of a 3-colorable graph with 2 colors, such that no triangle has all 3 vertices the same color. This allows you to break the graph into 2 pieces with no triangles, and thus reduce the coloring problem to one on graphs with no triangles. 3. An apocryphal story says that the first two cars in New York city were involved in a fender bender. To explain this phenomenon, consider a model of an undirected graph in which two particles (starting at arbitrary positions) follow a random walk. Prove that the expected time until they collide is polynomial in the graph size. Hint: consider a state space capturing the positions of both cars. 4. MR 6.16. To show that the previous model does not properly reflect new york’s one-way streets, prove that cover time of certain strongly-connected directed graphs cannot be bounded by any polynomial in the number of vertices. Do so by exhibiting a strongly connected nonbipartite graph (not a multi-graph) for which the cover time is super-polynomial. 1 M. R. refers to this text:Motwani, Rajeez, and Prabhakar Raghavan. Randomized Algorithms. Cambridge: Cambridge University Press, 1995.125. optional, linear algebra required. Prove that for any stochastic matrix P , there is a vector π with πP = π (this shows that every Markov chain has at least one stationary distribution). 6. optional. Construct a universal traversal sequence for 4-vertex cycles.