随机算法 (Fall 2011)/Card Shuffling and 随机算法 (Fall 2011)/Graph Coloring: Difference between pages

From TCS Wiki
(Difference between pages)
Jump to navigation Jump to search
VisualWikitext
imported>WikiSysop
m (Protected "随机算法 (Fall 2011)/Card Shuffling" ([edit=sysop] (indefinite) [move=sysop] (indefinite)))
 
imported>WikiSysop
No edit summary
 
Line 1: Line 1:
=Riffle Shuffle=
=Graph Colorings=
The following is the Gilbert-Shannon-Reeds model of riffle shuffle introduced by Gilbert and Shannon in 1955 and independently by Reeds in 1985.
A '''proper coloring''' of a graph <math>G(V,E)</math> is a mapping <math>f:V\rightarrow[q]</math> for some integer <math>q</math>, satisfying that <math>f(u)\neq f(v)</math> for all <math>uv\in E</math>.
{{Theorem| Riffle Shuffle (Gilbert-Shannon 1955; Reeds 1985)|
 
:Given a deck of <math>n</math> cards, at each round, do as follows.
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.
# Split the original deck into two decks according to the binomial distribution <math>\mathrm{Bin}(n,1/2)</math>.  
 
#: Cut off the first <math>k</math> cards with probability <math>\frac{{n\choose k}}{2^n}</math>, put into the left deck, and put the rest <math>n-k</math> cards into the right deck.
Let's first consider the decision version of the problem. That is, given as input a graph <math>G(V,E)</math>, decide whether there exists a proper <math>q</math>-coloring of <math>G</math>. Denote by <math>\Delta</math> the maximum degree of <math>G</math>.
# 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.
* If <math>q\ge \Delta+1</math>, there always exists a proper coloring. Moreover, the proper coloring can be found by a simple greedy algorithm.
#: Suppose at a step there are <math>L</math> cards in the left deck and <math>R</math> cards in the right deck. A card is dropped from left with probability <math>\frac{L}{L+R}</math>, and from right otherwise.
* If <math>q=\Delta</math>, <math>G</math> has a proper coloring unless it contains a <math>(\Delta+1)</math>-clique or it is an odd cycle. ([http://en.wikipedia.org/wiki/Brooks'_theorem Brooks Theorem])
}}
* If <math>q<\Delta</math>, the problem is NP-hard.
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.
 
Sampling a random coloring is at least as hard as deciding its existence, so we don't expect to solve the sampling problem when <math>q<\Delta</math>. The decision problem for the case <math>q=\Delta</math> is also nontrivial. Thus people are interested only in the case when <math>q\ge \Delta+1</math>.
 
The following is a natural Markov chain for sampling proper colorings.


The above model is equivalent to the following model of inverse riffle shuffle.
{{Theorem|Markov Chain for Graph Coloring <math>\mathcal{M}_c</math>|
{{Theorem|Inverse Riffle Shuffle|
:Start with a proper coloring of <math>G(V,E)</math>. At each step:
# Label each card with a bit from <math>\{0,1\}</math> uniformly and independently at random.
# Pick a vertex <math>v\in V</math> and a color <math>c\in[q]</math> uniformly 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.  
# Change the color of <math>v</math> to <math>c</math> if the resulting coloring is proper; do nothing if otherwise.
}}
}}


The process of inverse riffle shuffle is depicted as follows.
For a fixed graph <math>G(V,E)</math>, the state space of the above Markov chain is the set of all proper colorings of <math>G</math> with <math>q</math> colors.
:[[image:Riffle.png|800px]]
 
For each card, the random bits used for labeling the card compose a binary code <math>x</math>, with the <math>t</math>-th bit (from lower to higher radix) <math>x_t</math> being the random bit chosen in round <math>t</math> to label the card.


{{Theorem|Lemma|
{{Theorem|Lemma|
:After every round of the inverse riffle shuffle, the cards are sorted in non-decreasing order of their corresponding binary codes.
The followings hold for <math>\mathcal{M}_c</math>.
}}
# Aperiodic.
{{Proof|
# The transition matrix is symmetric.
By induction. After the first round, all <math>0</math> are above all <math>1</math>s. Assume that the hypothesis is true for the first <math>t-1</math> rounds. After the <math>t</math>-th round, all cards with the highest coordinate <math>x_t=0</math> are above all cards with <math>x_t=1</math>, and by the definition of inverse riffle shuffle, cards with the same highest bit <math>x_t</math> are kept in the same relative order as they are after the <math>(t-1)</math>-th round of the shuffling, which due to the hypothesis, means that the cards with the same highest bit <math>x_t</math> are sorted in the non-decreasing order of <math>x_{t-1}x_{t-2}\cdots x_1</math>. By the definition of binary representation, all cards are sorted.
# Irreducible if <math>q\ge \Delta+2</math>.
}}
}}


=Rapid Mixing of Riffle Shuffle by Coupling=
The followings are the two most important conjectures regarding the problem.
{{Theorem|Theorem|
{{Theorem|Conjecture|
:The mixing time of inverse riffle shuffle of a deck of <math>n</math> cards is <math>\tau_{\mathrm{mix}}=O(\log n)</math>.
#<math>\mathcal{M}_c</math> has mixing time <math>O(n\ln n)</math> whenever <math>q\ge\Delta+2</math>.
# Random sampling of proper graph colorings can be done in polynomial time whenever <math>q\ge\Delta+1</math>.
}}
}}


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:
These two conjectures are still open. People approach them by relax the requirement for the number of colors <math>q</math>. Intuitively, the larger the <math>q</math> is, the more freedom we have, the less dependency are there between non-adjacent vertices.
* 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 <math>i\in[n]</math>, we uniformly and independently choose a random <math>b_i\in\{0,1\}</math> as the label of the card <math>i</math> 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.
=Coupling: <math>q\ge 4\Delta+1</math>=
We couple the two copies of <math>\mathcal{M}_c</math>, <math>X_t</math> and <math>Y_t</math>, by the following coupling rule:
* At each step, let <math>X_t</math> and <math>Y_t</math> choose the same vertex <math>v</math> and same color <math>c</math>.


{{Theorem|Lemma|
Note that by this coupling, it is possible that <math>v</math> is recolored to <math>c</math> 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.
: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 <math>T</math> 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,
Let <math>d(X_t,Y_t)</math> be the number of vertices whose colors in <math>X_t</math> and <math>Y_t</math> disagree. For each step, for any choice of vertex <math>v</math> and color <math>c</math>, there are three possible cases:
:<math>\Delta(t)\le\Pr[T\ge t]</math>.
* '''"Good move"''' (<math>d(X_t,Y_t)</math> decreases by 1): <math>X_t</math> disagree with <math>Y_t</math> at <math>v</math>, and <math>c</math> is not used in the colors of <math>v</math> in both <math>X_t</math> and <math>Y_t</math>.
This bound can be deduced from the birthday problem. After <math>t</math> round, each of the <math>n</math> cards is randomly assigned one of the <math>2^t</math> possible labels. We know that for some <math>2^t=O(n^2)</math>, i.e. <math>t=2\log n+O(1)</math>, the probability that no two cards have the same label is <math>>1-1/2\mathrm{e}</math>, i.e. <math>\Delta(t)<1/2\mathrm{e}</math>, thus
* '''"Bad move"''' (<math>d(X_t,Y_t)</math> increases by 1):
:<math>\tau_{\mathrm{mix}}\le 2\log n+O(1)</math>.
* '''"Neutral move"''' (<math>d(X_t,Y_t)</math> is unchanged):
Note that the state space is the set of all permutations, which is of size <math>n!</math>, whose logarithm is still as large as <math>\log (n!)=O(n\ln n)</math> 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 <math>n=52</math>, the real mixing rate is as follows.
=Path Coupling: <math>q\ge 2\Delta+1</math> =
:{|border="2" cellspacing="4" cellpadding="3" rules="all" style="margin:1em 1em 1em 0; border:solid 1px #AAAAAA; border-collapse:collapse;empty-cells:show;"
|-
|<math>t</math>||1||2||3||4||5||6||7||8||9
|-
|<math>\Delta(t)</math>||1.000|| 1.000|| 1.000|| 1.000|| 0.924|| 0.614|| 0.334|| 0.167|| 0.003
|}

Revision as of 06:20, 27 August 2011

Graph Colorings

A proper coloring of a graph [math]\displaystyle{ G(V,E) }[/math] is a mapping [math]\displaystyle{ f:V\rightarrow[q] }[/math] for some integer [math]\displaystyle{ q }[/math], satisfying that [math]\displaystyle{ f(u)\neq f(v) }[/math] for all [math]\displaystyle{ uv\in E }[/math].

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 [math]\displaystyle{ G(V,E) }[/math], decide whether there exists a proper [math]\displaystyle{ q }[/math]-coloring of [math]\displaystyle{ G }[/math]. Denote by [math]\displaystyle{ \Delta }[/math] the maximum degree of [math]\displaystyle{ G }[/math].

  • If [math]\displaystyle{ q\ge \Delta+1 }[/math], there always exists a proper coloring. Moreover, the proper coloring can be found by a simple greedy algorithm.
  • If [math]\displaystyle{ q=\Delta }[/math], [math]\displaystyle{ G }[/math] has a proper coloring unless it contains a [math]\displaystyle{ (\Delta+1) }[/math]-clique or it is an odd cycle. (Brooks Theorem)
  • If [math]\displaystyle{ q\lt \Delta }[/math], 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 [math]\displaystyle{ q\lt \Delta }[/math]. The decision problem for the case [math]\displaystyle{ q=\Delta }[/math] is also nontrivial. Thus people are interested only in the case when [math]\displaystyle{ q\ge \Delta+1 }[/math].

The following is a natural Markov chain for sampling proper colorings.

Markov Chain for Graph Coloring [math]\displaystyle{ \mathcal{M}_c }[/math]
Start with a proper coloring of [math]\displaystyle{ G(V,E) }[/math]. At each step:
  1. Pick a vertex [math]\displaystyle{ v\in V }[/math] and a color [math]\displaystyle{ c\in[q] }[/math] uniformly at random.
  2. Change the color of [math]\displaystyle{ v }[/math] to [math]\displaystyle{ c }[/math] if the resulting coloring is proper; do nothing if otherwise.

For a fixed graph [math]\displaystyle{ G(V,E) }[/math], the state space of the above Markov chain is the set of all proper colorings of [math]\displaystyle{ G }[/math] with [math]\displaystyle{ q }[/math] colors.

Lemma

The followings hold for [math]\displaystyle{ \mathcal{M}_c }[/math].

  1. Aperiodic.
  2. The transition matrix is symmetric.
  3. Irreducible if [math]\displaystyle{ q\ge \Delta+2 }[/math].

The followings are the two most important conjectures regarding the problem.

Conjecture
  1. [math]\displaystyle{ \mathcal{M}_c }[/math] has mixing time [math]\displaystyle{ O(n\ln n) }[/math] whenever [math]\displaystyle{ q\ge\Delta+2 }[/math].
  2. Random sampling of proper graph colorings can be done in polynomial time whenever [math]\displaystyle{ q\ge\Delta+1 }[/math].

These two conjectures are still open. People approach them by relax the requirement for the number of colors [math]\displaystyle{ q }[/math]. Intuitively, the larger the [math]\displaystyle{ q }[/math] is, the more freedom we have, the less dependency are there between non-adjacent vertices.

Coupling: [math]\displaystyle{ q\ge 4\Delta+1 }[/math]

We couple the two copies of [math]\displaystyle{ \mathcal{M}_c }[/math], [math]\displaystyle{ X_t }[/math] and [math]\displaystyle{ Y_t }[/math], by the following coupling rule:

  • At each step, let [math]\displaystyle{ X_t }[/math] and [math]\displaystyle{ Y_t }[/math] choose the same vertex [math]\displaystyle{ v }[/math] and same color [math]\displaystyle{ c }[/math].

Note that by this coupling, it is possible that [math]\displaystyle{ v }[/math] is recolored to [math]\displaystyle{ c }[/math] 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 [math]\displaystyle{ d(X_t,Y_t) }[/math] be the number of vertices whose colors in [math]\displaystyle{ X_t }[/math] and [math]\displaystyle{ Y_t }[/math] disagree. For each step, for any choice of vertex [math]\displaystyle{ v }[/math] and color [math]\displaystyle{ c }[/math], there are three possible cases:

  • "Good move" ([math]\displaystyle{ d(X_t,Y_t) }[/math] decreases by 1): [math]\displaystyle{ X_t }[/math] disagree with [math]\displaystyle{ Y_t }[/math] at [math]\displaystyle{ v }[/math], and [math]\displaystyle{ c }[/math] is not used in the colors of [math]\displaystyle{ v }[/math] in both [math]\displaystyle{ X_t }[/math] and [math]\displaystyle{ Y_t }[/math].
  • "Bad move" ([math]\displaystyle{ d(X_t,Y_t) }[/math] increases by 1):
  • "Neutral move" ([math]\displaystyle{ d(X_t,Y_t) }[/math] is unchanged):

Path Coupling: [math]\displaystyle{ q\ge 2\Delta+1 }[/math]

Retrieved from "https://tcs.nju.edu.cn/wiki/index.php?title=随机算法_(Fall_2011)/Card_Shuffling&oldid=4703"