随机算法 (Spring 2013)/Problem Set 4

From EtoneWiki
Jump to: navigation, search

Problem 1

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 2

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.

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 .

Hint.2: When constructing the coupling, consider using a cyclic permutation of disagreeing positions.

Problem 3

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 by coupling.

Hint.1: Considering a coupling , the is partitioned into . Design a coupling rule to adopt different cases (regarding which parts the random and 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 to achieve the above goal.

Problem 4

Let be a connected undirected simple graph (no self-loops and parallel edges) defined on vertices. Let be the expansion ratio of . is NOT necessarily regular. For any , let be the degree of vertex .

  • What is the largest possible value for ? Construct a graph with this expansion ratio and explain why it is the largest.
  • What is the smallest possible value for ? Construct a graph with this expansion ratio and explain why it is the smallest.
  • Run a lazy random walk on . What is the stationary distribution? Starting from an arbitrary vertex in an arbitrary unknown , 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 from the stationary distribution? Give an upper bound of the time in terms of and .
  • Suppose that the maximum degree of is known but the graph is not necessarily regular. Design a random walk on with uniform stationary distribution. How long should you run the random walk to be within -close to the uniform distribution in the worst case?