随机算法 (Fall 2011)/Problem set 4

From EtoneWiki
Jump to: navigation, search

Problem 1

Let and be two probability distributions over . Give an explicit construction of a coupling of and such that

.

Problem 2

Consider the Markov chain of graph coloring

Markov Chain for Graph Coloring
Start with a proper coloring of . At each step:
  1. Pick a vertex and a color uniformly at random.
  2. Change the color of to if the resulting coloring is proper; do nothing if otherwise.

Show that the Markov chain is:

  1. aperiodic;
  2. irreducible if ;
  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 :
  1. pick an uniformly at random;
  2. flip (let ) if .
  • 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 for some :

Random walk over -subsets
At each step, for the current state :
  1. with probability , do nothing;
  2. else pick an and a independently and uniformly at random, and change the current set to be .

You are allowed to choose a self-loop probability for your convenience.

  • Show that the random walk is ergodic
  • Give the stationary distribution of the random walk.
  • Prove that the mixing time is .