View source for 随机算法 (Spring 2013)/Problem Set 4

== Problem 1 ==
Consider the Markov chain of graph coloring
{{Theorem|Markov Chain for Graph Coloring|
:Start with a proper coloring of <math>G(V,E)</math>. At each step:
# Pick a vertex <math>v\in V</math> and a color <math>c\in[q]</math> uniformly at random.
# Change the color of <math>v</math> to <math>c</math> if the resulting coloring is proper; do nothing if otherwise.
}}

Show that the Markov chain is:
# aperiodic;
# irreducible if <math>q\ge \Delta+2</math>;
# with uniform stationary distribution.

== Problem 2 ==
Consider the following random walk on hypercube:
{{Theorem|Yet another random Walk on Hypercube|
: At each step, for the current state <math>x\in\{0,1\}^n</math>:
# pick an <math>i\in\{0,1,2,\ldots,n\}</math> uniformly at random;
# flip <math>x_i</math> (let <math>x_i=1-x_i</math>) if <math>i\neq 0</math>.
}}
* Show that the random walk is ergodic.
* Give the stationary distribution of the random walk.
* Analyze the mixing time of the random walk by coupling.

Hint.1: Construct a coupling rule such that the Hamming distance between two states never increases, and decreases much faster than the naive coupling which forces the two chains to use the same <math>i</math>.

Hint.2: When constructing the coupling, consider using a cyclic permutation of disagreeing positions.

== Problem 3==
Consider the following random walk over all subsets <math>S\in{[n]\choose k}</math> for some <math>k\le \frac{n}{2}</math>:
{{Theorem|Random walk over <math>k</math>-subsets|
: At each step, for the current state <math>S\in{[n]\choose k}</math>:
# with probability <math>p</math>, do nothing;
# else pick an <math>x\in S</math> and a <math>y\in[n]\setminus S</math> independently and uniformly at random, and change the current set to be <math>S\setminus\{x\}\cup\{y\}</math>.
}}
You are allowed to choose a self-loop probability <math>p</math> for your convenience.
* Show that the random walk is ergodic
* Give the stationary distribution of the random walk.
* Prove that the mixing time is <math>O(k\log k)</math> by coupling.

Hint.1: Considering a coupling <math>(S,T)</math>, the <math>[n]</math> is partitioned into <math>S\cap T,S\setminus T,T\setminus S,\overline{S\cup T}</math>. Design a coupling rule to adopt different cases (regarding which parts the random <math>x</math> and <math>y</math> belong to) so that the difference between two states never increases.

Hint.2: Use a cyclic permutation (with some desirable property) of elements in the symmetric difference <math>S\oplus T</math> to achieve the above goal.

== Problem 4 ==
Let <math>G(V,E)</math> be a connected undirected simple graph (no self-loops and parallel edges) defined on <math>n</math> vertices. Let <math>\phi(G)</math> be the expansion ratio of <math>G</math>. <math>G</math> is NOT necessarily regular. For any <math>v\in V</math>, let <math>d_v</math> be the degree of vertex <math>v</math>.
* What is the largest possible value for <math>\phi(G)</math>? Construct a graph <math>G</math> with this expansion ratio and explain why it is the largest.
* What is the smallest possible value for <math>\phi(G)</math>? Construct a graph <math>G</math> with this expansion ratio and explain why it is the smallest.
* Run a lazy random walk on <math>G</math>. What is the stationary distribution? Starting from an arbitrary vertex in an arbitrary unknown <math>G</math>, how long in the worst case should you run the random walk to guarantee the distribution of the current position is within a total variation distance of <math>\epsilon</math> from the stationary distribution? Give an upper bound of the time in terms of <math>n</math> and <math>\epsilon</math>.
* Suppose that the maximum degree of <math>G</math> is known but the graph is not necessarily regular. Design a random walk on <math>G</math> with uniform stationary distribution. How long should you run the random walk to be within <math>\epsilon</math>-close to the uniform distribution in the worst case?