随机算法 (Fall 2015)/Mixing Time and Coupling

From EtoneWiki
Jump to: navigation, search

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.

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 .

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
  1. for any integer .
  2. .

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

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 .
  1. For any coupling of and , it holds that .
  2. 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 .

Coupling.png

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
  1. each of and viewed in isolation is a faithful copy of the original Markov chain, i.e.
    ;
  2. 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
.
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:
.

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
  1. for any integer .
  2. .
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 :
  1. with probability , do nothing;
  2. 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 :
  1. pick a coordinate uniformly at random and a bit uniformly at random;
  2. 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.
  1. 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.
  2. 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
  1. Label each card with a bit from uniformly and independently at random.
  2. 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.

Riffle.png

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