随机算法 (Fall 2011)/Problem set 4: Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
imported>Etone
No edit summary
imported>Etone
 
(5 intermediate revisions by the same user not shown)
Line 2: Line 2:
Let <math>p</math> and <math>q</math> be two probability distributions over <math>\Omega</math>. Give an explicit construction of a coupling <math>\mu</math> of <math>p</math> and <math>q</math> such that  
Let <math>p</math> and <math>q</math> be two probability distributions over <math>\Omega</math>. Give an explicit construction of a coupling <math>\mu</math> of <math>p</math> and <math>q</math> such that  
::<math>\Pr_{(X,Y)\sim\mu}[X\neq Y]=\|p-q\|_{TV}</math>.
::<math>\Pr_{(X,Y)\sim\mu}[X\neq Y]=\|p-q\|_{TV}</math>.
== Problem 2 ==
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 3 ==
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.
== Problem 4==
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(n\log k)</math>.

Latest revision as of 06:55, 28 November 2011

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:
  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 3

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.

Problem 4

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(n\log k) }[/math].