随机算法 (Spring 2013)/Problem Set 4
Problem 1
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:
- aperiodic;
- irreducible if [math]\displaystyle{ q\ge \Delta+2 }[/math];
- with uniform stationary distribution.
Problem 2
Consider the following random walk on hypercube:
Yet another random Walk on Hypercube - At each step, for the current state [math]\displaystyle{ x\in\{0,1\}^n }[/math]:
- pick an [math]\displaystyle{ i\in\{0,1,2,\ldots,n\} }[/math] uniformly at random;
- flip [math]\displaystyle{ x_i }[/math] (let [math]\displaystyle{ x_i=1-x_i }[/math]) if [math]\displaystyle{ 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.
Problem 3
Consider the following random walk over all subsets [math]\displaystyle{ S\in{[n]\choose k} }[/math] for some [math]\displaystyle{ k\le \frac{n}{2} }[/math]:
Random walk over [math]\displaystyle{ k }[/math]-subsets - At each step, for the current state [math]\displaystyle{ S\in{[n]\choose k} }[/math]:
- with probability [math]\displaystyle{ p }[/math], do nothing;
- else pick an [math]\displaystyle{ x\in S }[/math] and a [math]\displaystyle{ y\in[n]\setminus S }[/math] independently and uniformly at random, and change the current set to be [math]\displaystyle{ S\setminus\{x\}\cup\{y\} }[/math].
You are allowed to choose a self-loop probability [math]\displaystyle{ 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]\displaystyle{ O(n\log k) }[/math] by coupling.
Problem 4
Let [math]\displaystyle{ G(V,E) }[/math] be a connected undirected simple graph (no self-loops and parallel edges) defined on [math]\displaystyle{ n }[/math] vertices. Let [math]\displaystyle{ \phi(G) }[/math] be the expansion ratio of [math]\displaystyle{ G }[/math]. [math]\displaystyle{ G }[/math] is NOT necessarily regular. For any [math]\displaystyle{ v\in V }[/math], let [math]\displaystyle{ d_v }[/math] be the degree of vertex [math]\displaystyle{ v }[/math].
- What is the largest possible value for [math]\displaystyle{ \phi(G) }[/math]? Construct a graph [math]\displaystyle{ G }[/math] with this expansion ratio and explain why it is the largest.
- What is the smallest possible value for [math]\displaystyle{ \phi(G) }[/math]? Construct a graph [math]\displaystyle{ G }[/math] with this expansion ratio and explain why it is the smallest.
- Run a lazy random walk on [math]\displaystyle{ G }[/math]. What is the stationary distribution? Starting from an arbitrary vertex in an arbitrary unknown [math]\displaystyle{ 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]\displaystyle{ \epsilon }[/math] from the stationary distribution? Give an upper bound of the time in terms of [math]\displaystyle{ n }[/math] and [math]\displaystyle{ \epsilon }[/math].
- Suppose that the maximum degree of [math]\displaystyle{ G }[/math] is known but the graph is not necessarily regular. Design a random walk with uniform stationary distribution. How long should you run the random walk to be within [math]\displaystyle{ \epsilon }[/math]-close to the uniform distribution in the worst case?