随机算法 (Spring 2014)/Problem Set 4

Problem 1

A proper [math]\displaystyle{ q }[/math]-coloring of a graph [math]\displaystyle{ G(V,E) }[/math] is a mapping [math]\displaystyle{ f:V\to [q] }[/math] such that for any edge [math]\displaystyle{ uv\in E }[/math] we have [math]\displaystyle{ f(u)\neq f(v) }[/math].

Consider the following Markov chain for proper [math]\displaystyle{ q }[/math]-colorings of a graph [math]\displaystyle{ G(V,E) }[/math]:

Markov Chain for Graph Coloring

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

Show that the Markov chain is:

1. ergodic (i.e., aperiodic);
2. irreducible if [math]\displaystyle{ q\ge \Delta+2 }[/math];
3. with uniform stationary distribution.