随机算法 (Spring 2013)/Mixing Time and Coupling
Mixing Time
The mixing time of a Markov chain gives the rate at which a Markov chain converges to the stationary distribution. To rigorously define this notion, we need a way of measuring the closeness between two distributions.
Total Variation Distance
In probability theory, the total variation distance measures the difference between two probability distributions.
Definition (total variation distance) - Let and be two probability distributions over the same finite state space , the total variation distance between and is defined as
- ,
- where is the -norm of vectors.
- Let and be two probability distributions over the same finite state space , the total variation distance between and is defined as
It can be verified (left as an exercise) that
- ,
thus the total variation distance can be equivalently defined as
- .
So the total variation distance between two distributions gives an upper bound on the difference between the probabilities of the same event according to the two distributions.
Mixing Time
Definition (mixing time) - Let be the stationary of the chain, and be the distribution after steps when the initial state is .
- is the distance to stationary distribution after steps, started at state .
- is the maximum distance to stationary distribution after steps.
- is the time until the total variation distance to the stationary distribution, started at the initial state , reaches .
- is the time until the total variation distance to the stationary distribution, started at the worst possible initial state, reaches .
- Let be the stationary of the chain, and be the distribution after steps when the initial state is .
We note that is monotonically non-increasing in . So the definition of makes sense, and is actually the inverse of .
Definition (mixing time) - The mixing time of a Markov chain is .
The mixing time is the time until the total variation distance to the stationary distribution, starting from the worst possible initial state , reaches . The value is chosen just for the convenience of calculation. The next proposition says that with general can be estimated from .
Proposition - for any integer .
- .
So the distance to stationary distribution decays exponentially in multiplications of .
Both the formal proofs of the monotonicity of and the above proposition uses the coupling technique and is postponed to next section.
Coupling
We will discuss how to bound the mixing time by coupling two Markov chains. Before that, we will first formally introduce the coupling of two probability distributions.
Coupling of Two Distributions
Coupling is a powerful proof technique in probability theory. It allows us to compare two unrelated variables (or processes) by forcing them to share some randomness.
Definition (coupling) - Let and be two probability distributions over . A probability distribution over is said to be a coupling if its marginal distributions are and ; that is
- Let and be two probability distributions over . A probability distribution over is said to be a coupling if its marginal distributions are and ; that is
The interesting case is when and are not independent. In particular, we want the probability that to be as large as possible, yet still maintaining the respective marginal distributions and . When and are different it is inevitable that with some probability, but how small this probability can be, that is, how well two distributions can be coupled? The following coupling lemma states that this is determined by the total variation distance between the two distributions.
Lemma (coupling lemma) - Let and be two probability distributions over .
- For any coupling of and , it holds that .
- There exists a coupling of and such that .
Proof. - 1.
Suppose follows the distribution over . Due to the definition of coupling,
Then for any , , thus
Therefore,
- 2.
We can couple and so that for each , with probability . The remaining follows as above.
The proof is depicted by the following figure, where the curves are the probability density functions for the two distributions and , the colored area is the diference between the two distribution, and the "lower envelope" (the red line) is the .
Monotonicity of
Consider a Markov chain on state space . Let be the stationary distribution, and be the distribution after steps when the initial state is . Recall that is the distance to stationary distribution after steps, started at state .
We will show that is non-decreasing in . That is, for a Markov chain, the variation distance to the stationary distribution monotonically decreases as time passes. Although this is rather intuitive at the first glance, the proof is nontrivial. A brute force (algebraic) proof can be obtained by analyze the change to the 1-norm of by multiplying the transition matrix . The analysis uses eigen decomposition. We introduce a cleverer proof using coupling.
Proposition - is non-decreasing in .
Proof. Let and follow the stationary distribution . Two chains and can be defined by the initial distributions and . The distributions of and are and , respectively.
For any fixed , we can couple and such that . Due to the Coupling Lemma, such coupling exists. We then define a coupling between and as follows.
- If , then following the transition matrix of the Markov chain.
- Otherwise, do the transitions and independently, following the transitin matrix.
It is easy to see that the marginal distributions of and both follow the original Markov chain, and
In conclusion, it holds that
where the first inequality is due to the easy direction of the Coupling Lemma.
Rapid Mixing by Coupling
Consider an ergodic (irreducible and aperiodic) Markov chain on finite state space . We want to upper bound its mixing time. The coupling technique for bounding the mixing time can be sumerized as follows:
- Consider two random walks starting at state and in . Each individual walk follows the transition rule of the original Markov chain. But the two random walks may be "coupled" in some way, that is, may be correlated with each other. A key observation is that for any such coupling, it always holds that
- where we recall that .
Definition (coupling of Markov chain) - A coupling of a Markov chain with state space and transition matrix , is a Markov chain with state space , satisfying
- each of and viewed in isolation is a faithful copy of the original Markov chain, i.e.
- ;
- once and reaches the same state, they make identical moves ever since, i.e.
- if .
Lemma (coupling lemma for Markov chains) - Let be a coupling of a Markov chain with state space . Then for is bounded by
- .
- Let be a coupling of a Markov chain with state space . Then for is bounded by
Proof. Due to the coupling lemma (for probability distributions),
where are distributions of the Markov chain at time , started at states .
Therefore,
Corollary - Let be a coupling of a Markov chain with state space . Then for is bounded as follows:
- .
- Let be a coupling of a Markov chain with state space . Then for is bounded as follows:
Geometric convergence
Consider a Markov chain on state space . Let be the stationary distribution, and be the distribution after steps when the initial state is . Recall that
- ;
- ;
- ;
- ;
- .
We prove that
Proposition - for any integer .
- .
Proof. - 1.
We denote that . We construct a coupling of the Markov chain as follows. Suppose for some integer .
- If then for .
- For the case that for some , we couple the and so that . Due to the Coupling Lemma, such coupling does exist.
For any that ,
Thus by the law of total probability. Therefore, for any ,
Then by induction,
and this holds for any . By the Coupling Lemma for Markov chains, this means .
- 2.
By the definition of , the inequality is straightforwardly implied by (1).
Application: Random Walk on the Hypercube
A -dimensional hypercube is a graph on vertex set . For any , there is an edge between and if and differ at exact one coordinate (the hamming distance between and is 1).
We use coupling to bound the mixing time of the following simple random walk on a hypercube.
Random Walk on Hypercube - At each step, for the current state :
- with probability , do nothing;
- else, pick a coordinate uniformly at random and flip the bit (change to ).
This is a lazy uniform random walk in an -dimensional hypercube. It is equivalent to the following random walk.
Random Walk on Hypercube - At each step, for the current state :
- pick a coordinate uniformly at random and a bit uniformly at random;
- let .
It is easy to see the two random walks are the same. The second form hint us to couple the random choice of and in each step. Consider two copies of the random walk and , started from arbitrary two states and , the coupling rule is:
- At each step, and choose the same (uniformly random) coordinate and the same (uniformly random) bit .
Obviously the two individual random walks are both faithful copies of the original walk.
For arbitrary , started at , the event occurs if everyone of the coordinates on which and disagree has been picked at least once. In the worst case, and disagree on all coordinates. The time that all coordinates have been picked follows the coupon collector problem collecting coupons, and we know from the coupon collector problem that for ,
Thus for any , if , then . Due to the coupling lemma for Markov chains,
which implies that
- .
So the random walk achieves a polynomially small variation distance to the stationary distribution in time .
Note that the number of states (vertices in the -dimensional hypercube) is . Therefore, the mixing time is exponentially small compared to the size of the state space.
Card Shuffling
We consider the Markov chain of shuffling a deck of cards, and prove the rapid mixing of the chain by coupling.
Riffle Shuffle
The following is the Gilbert-Shannon-Reeds model of riffle shuffle introduced by Gilbert and Shannon in 1955 and independently by Reeds in 1985.
Riffle Shuffle (Gilbert-Shannon 1955; Reeds 1985) - Given a deck of cards, at each round, do as follows.
- Split the original deck into two decks according to the binomial distribution .
- Cut off the first cards with probability , put into the left deck, and put the rest cards into the right deck.
- Drop cards in sequence, where the next card comes from one of the two decks with probability proportional to the size of the deck at that time.
- Suppose at a step there are cards in the left deck and cards in the right deck. A card is dropped from left with probability , and from right otherwise.
The second step actually samples a uniform interleaving of left and right deck. The magician and mathematician Diaconis in 1988 found evidence showing that this mathematical model reasonably approximate the riffle shuffling acted by human.
The above model is equivalent to the following model of inverse riffle shuffle.
Inverse Riffle Shuffle - Label each card with a bit from uniformly and independently at random.
- Place all cards labeled with 0 above all cards labeled with 1, keeping the cards with the same label in the same the relative order as before.
The process of inverse riffle shuffle is depicted as follows.
For each card, the random bits used for labeling the card compose a binary code , with the -th bit (from lower to higher radix) being the random bit chosen in round to label the card.
Lemma - After every round of the inverse riffle shuffle, the cards are sorted in non-decreasing order of their corresponding binary codes.
Proof. By induction. After the first round, all are above all s. Assume that the hypothesis is true for the first rounds. After the -th round, all cards with the highest coordinate are above all cards with , and by the definition of inverse riffle shuffle, cards with the same highest bit are kept in the same relative order as they are after the -th round of the shuffling, which due to the hypothesis, means that the cards with the same highest bit are sorted in the non-decreasing order of . By the definition of binary representation, all cards are sorted.
Rapid Mixing of Riffle Shuffle by Coupling
Theorem - The mixing time of inverse riffle shuffle of a deck of cards is .
Consider two instance of shuffling, started with two decks, each in an arbitrary order. We couple the two shuffling processes by coupling their random choices of labelings:
- In each round, we label the same cards (same content, not the same order) in the two decks with the same random bit.
Formally, for each , we uniformly and independently choose a random as the label of the card in each of the two decks in that round. It is easy to see that, each of the two shuffling processes viewed individually follows exactly the rules of inverse riffle shuffle.
Lemma - With the above coupling rule, started with arbitrary two decks of cards, the two decks are the same once all cards in the first (or the second) deck have distinct labels.
Proof. By the definition of the coupling rule, any two identical cards in the two decks always have the same label, since in every round they choose the same random bit. And we have shown that after each round, the labels are sorted in non-decreasing order. Thus, we can conclude:
- after each round, the sequences of the labels of the two decks are identical (and sorted in non-decreasing order).
Therefore, when all cards in the first deck have distinct labels, the second deck have the same set of distinct labels, and the cards are sorted increasingly in their labels in the respective decks. Since any two identical cards have the same labels, the cards in the two decks must be in the same order.
We denote by the random variable representing the time that in an inverse riffle shuffle, all cards in the deck have distinct labels. Due to the coupling lemma for Markov chains,
- .
This bound can be deduced from the birthday problem. After round, each of the cards is randomly assigned one of the possible labels. We know that for some , i.e. , the probability that no two cards have the same label is , i.e. , thus
- .
Note that the state space is the set of all permutations, which is of size , whose logarithm is still as large as due to Stirling's approximation. Thus the riffle shuffle is mixing extremely fast.
This estimation of mixing time is fairly tight. For the case that , the real mixing rate is as follows.
1 2 3 4 5 6 7 8 9 1.000 1.000 1.000 1.000 0.924 0.614 0.334 0.167 0.003
Graph Colorings
A proper coloring of a graph is a mapping for some integer , satisfying that for all .
We consider the problem of sampling a uniformly random proper coloring of a given graph. We will later see that this is useful for counting the number of proper colorings of a given graph, which is a fundamental combinatorial problem, having important applications in statistic physics.
Let's first consider the decision version of the problem. That is, given as input a graph , decide whether there exists a proper -coloring of . Denote by the maximum degree of .
- If , there always exists a proper coloring. Moreover, the proper coloring can be found by a simple greedy algorithm.
- If , has a proper coloring unless it contains a -clique or it is an odd cycle. (Brooks Theorem)
- If , the problem is NP-hard.
Sampling a random coloring is at least as hard as deciding its existence, so we don't expect to solve the sampling problem when . The decision problem for the case is also nontrivial. Thus people are interested only in the case when .
The following is a natural Markov chain for sampling proper colorings.
Markov Chain for Graph Coloring - Start with a proper coloring of . At each step:
- Pick a vertex and a color uniformly at random.
- Change the color of to if the resulting coloring is proper; do nothing if otherwise.
For a fixed graph , the state space of the above Markov chain is the set of all proper colorings of with colors.
Lemma The followings hold for .
- Aperiodic.
- The transition matrix is symmetric.
- Irreducible if .
The followings are the two most important conjectures regarding the problem.
Conjecture - has mixing time whenever .
- Random sampling of proper graph colorings can be done in polynomial time whenever .
These two conjectures are still open. People approach them by relax the requirement for the number of colors . Intuitively, the larger the is, the more freedom we have, the less dependency are there between non-adjacent vertices.
Rapid mixing of the case
We couple the two copies of , and , by the following coupling rule:
- At each step, let and choose the same vertex and same color .
Note that by this coupling, it is possible that is recolored to in both chains, in one of the two chains, or in no chain. We may separate these cases by looking at the Hamming distance between two colorings.
Let be the number of vertices whose colors in and disagree. For each step, for any choice of vertex and color , there are three possible cases:
- "Good move" ( decreases by 1): disagree with at , and is not used in the colors of in both and .
- "Bad move" ( increases by 1):
- "Neutral move" ( is unchanged):