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

From TCS Wiki
Jump to navigation Jump to search
imported>Etone
imported>Etone
 
(14 intermediate revisions by the same user not shown)
Line 23: Line 23:
* Analyze the mixing time of the random walk by coupling.
* 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.
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 a cyclic permutation of disagreeing positions.
Hint.2: When constructing the coupling, consider using a cyclic permutation of disagreeing positions.


== Problem 3==
== Problem 3==
Line 37: Line 37:
* Show that the random walk is ergodic
* Show that the random walk is ergodic
* Give the stationary distribution of the random walk.
* Give the stationary distribution of the random walk.
* Prove that the mixing time is <math>O(n\log k)</math> by coupling.
* 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 ==
== Problem 4 ==
Line 44: Line 48:
* 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.
* 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>.
* 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 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?
* 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?

Latest revision as of 19:52, 8 June 2013

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:
  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. aperiodic;
  2. irreducible if [math]\displaystyle{ q\ge \Delta+2 }[/math];
  3. 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]:
  1. pick an [math]\displaystyle{ i\in\{0,1,2,\ldots,n\} }[/math] uniformly at random;
  2. 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.

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]\displaystyle{ 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]\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]:
  1. with probability [math]\displaystyle{ p }[/math], do nothing;
  2. 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(k\log k) }[/math] by coupling.

Hint.1: Considering a coupling [math]\displaystyle{ (S,T) }[/math], the [math]\displaystyle{ [n] }[/math] is partitioned into [math]\displaystyle{ 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]\displaystyle{ x }[/math] and [math]\displaystyle{ 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]\displaystyle{ S\oplus T }[/math] to achieve the above goal.

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 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?