CS 263, Spring 2014, Homework 5

Due at the start of class, Thursday, May 8

  1. If $S$ is a subset of the points in an $n\times n$ square grid, define a "three-in-a-row" to be three points in $S$ that lie on a single straight line. Describe a Markov chain whose states are subsets that have no three-in-a-row, and whose stationary distribution is uniform on these states. Your Markov chain should have the additional properties that the number of different transitions that it could make from any state is a polynomial in $n$, that every two states can be connected by a sequence of transitions, and that there is a nonzero probability of remaining in the same state. You do not need to analyze its mixing time.

    (The maximum possible number of points in a state with no three-in-a-row is an open problem: see No-three-in-line problem on Wikipedia.)

  2. Suppose we shuffle an (initially non-random) deck of cards by the following procedure: repeatedly pull a card from a random position in the deck (including the top) and place it on top of the deck.

    1. Use coupling to prove that, once every card has been picked at least once. the permutation is (exactly, not approximately) uniformly random.

    2. Now consider the time-reversed dynamics: repeatedly pull the top card off the top of the deck and place it at a uniformly random position in the deck (including the top again). Prove that, once the card originally on the bottom reaches the top of the deck, the next step produces a deck whose permutation is uniformly random.

    3. What are the mixing times for these shuffling methods?

  3. In the lecture we looked at a Markov chain on $k$-colorings of a graph with maximum degree $\Delta$, in which each step chooses a random vertex $v$ and color $c$, and attempts to set $v$'s color to $c$. We used coupling to show that this chain mixes rapidly (within a polynomial number of steps) when $k > 4\Delta$. The coupling argument we used in the analysis applied the same choice $(v,c)$ to two chains, one initially uniform and the other initially in an arbitrary state, and showed that the number of differences between these two chains decreases in expectation. But as this exercise will show, this analysis is not tight.

    1. Suppose that two chains, with the same coupling as the one in the lecture, are already very close together: they only have one vertex at which their color is different. How big does $k$ need to be to ensure that the expected distance between these two chains becomes smaller after a single step?

    2. Suppose that $k>2\Delta$. Prove that, for any two colorings $X$ and $Y$, there exists a sequence of colorings starting with $X$ and ending with $Y$, with length $O(n)$ (where $n$ is the number of vertices in the graph to be colored), such that each two consecutive colorings in the path differ in the color of at most one vertex.

    By simultaneously coupling all the colorings in the sequence for part (b), rather than just the two colorings at the ends of the sequence, it is possible to show that the expected distance between arbitrary pairs of colorings also decreases whenever $k$ is large enough for parts (a) and (b) to both work.