随机算法 (Spring 2014)/Problem Set 4: Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
imported>Etone
imported>Etone
 
Line 1: Line 1:
== Problem 1 ==
== Problem 1 ==
A proper <math>q</math>-coloring of a graph <math>G(V,E)</math> is a mapping <math>f:V\to [q]</math> such that for any edge <math>uv\in E</math> we have <math>f(u)\neq f(v)</math>.
A '''proper <math>q</math>-coloring''' of a graph <math>G(V,E)</math> is a mapping <math>f:V\to [q]</math> such that for any edge <math>uv\in E</math> we have <math>f(u)\neq f(v)</math>.


Consider the following Markov chain for proper <math>q</math>-colorings of a graph <math>G(V,E)</math> whose maximum degree is <math>\Delta</math>:
Consider the following Markov chain for proper <math>q</math>-colorings of a graph <math>G(V,E)</math> whose '''maximum degree''' is <math>\Delta</math>:
{{Theorem|Markov Chain for Graph Coloring|
{{Theorem|Markov Chain for Graph Coloring|
:Start with a proper <math>q</math>-coloring of <math>G(V,E)</math>. At each step:
:Start with a proper <math>q</math>-coloring of <math>G(V,E)</math>. At each step:

Latest revision as of 00:57, 3 June 2014

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] whose maximum degree is [math]\displaystyle{ \Delta }[/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:
  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.

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.

Problem 2

Let [math]\displaystyle{ G(V,E) }[/math] be an undirected connected graph with known maximum degree [math]\displaystyle{ \Delta }[/math]. You want to design random walks over the vertices in [math]\displaystyle{ V }[/math] such that at each step only adjacent vertices are allowed to walk to (i.e., the transition matrix [math]\displaystyle{ P }[/math] is defined on [math]\displaystyle{ V\times V }[/math] and [math]\displaystyle{ P(u,v)\gt 0 }[/math] only if [math]\displaystyle{ uv\in E }[/math]). You are allowed to design the transition matrix [math]\displaystyle{ P }[/math] for your random walk to achieve certain stationary distributions.

  • Suppose that [math]\displaystyle{ G }[/math] is not necessarily regular (every vertex has the same degree). Design a time-reversible lazy random walk which is ergodic and always converges to uniform stationary distribution.
  • Given an arbitrary distribution [math]\displaystyle{ \pi }[/math] over [math]\displaystyle{ V }[/math], design a time-reversible lazy random walk which is ergodic and always converges to the stationary distribution [math]\displaystyle{ \pi }[/math].
  • (bonus question) Try to give sufficient conditions in terms of [math]\displaystyle{ G }[/math] and [math]\displaystyle{ \pi }[/math] for the rapid mixing of the above two random walks.

Problem 3

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 on [math]\displaystyle{ G }[/math] 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?