随机算法 (Fall 2011)/Problem set 4

Problem 1

Let [math]\displaystyle{ p }[/math] and [math]\displaystyle{ q }[/math] be two probability distributions over [math]\displaystyle{ \Omega }[/math]. Give an explicit construction of a coupling [math]\displaystyle{ \mu }[/math] of [math]\displaystyle{ p }[/math] and [math]\displaystyle{ q }[/math] such that

[math]\displaystyle{ \Pr_{(X,Y)\sim\mu}[X\neq Y]=\|p-q\|_{TV} }[/math].

Problem 2

Consider the Markov chain of graph coloring

Markov Chain for Graph Coloring

Start with a proper 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. aperiodic;
2. irreducible if [math]\displaystyle{ q\ge \Delta+2 }[/math];
3. with uniform stationary distribution.