Randomized Algorithms (Spring 2010)/Problem Set 4

From EtoneWiki
Jump to: navigation, search

Problem 1 (10 points)

Consider the following queuing model. Customers are waiting in a line for some service. Let and be some nonnegative reals with . At each time step, exactly one of the following occurs.

  1. If the queue has fewer than customers, then with probability a new customer joins the queue.
  2. If the queue is not empty, then with probability the head of the line is served and leaves the queue.
  3. With remaining probability, the queue is unchanged.
  • Represent this model by a Markov chain. Define the state space and the transition matrix .
  • What is the stationary distribution ? Try to explain what the means in the queuing model.


Problem 2 (10 points)

Let be an arbitrary connected undirected simple graph (no self-loops and parallel edges) defined on vertices. Let be an arbitrary distribution over . Design a time-reversible irreducible aperiodic random walk on whose stationary distribution is . Prove that the random walk is time-reversible, irreducible, aperiodic, and has stationary distribution .

(Note: is NOT necessarily regular.)


Problem 3 (20 points)

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. Modify the random walk to have a uniform stationary distribution. How long should you run the random walk to be within -close to the uniform distribution in the worst case?

Problem 4 (10 points)

An -dimensional de Bruijn graph is an undirected graph defined as:

  • ;
  • if for .

Run a lazy random walk on the de Bruijn graph. Apply the canonical paths argument to give an upper bound on the mixing time. Is the random walk rapid mixing?

(Note: Although usually de Bruijn graphs are defined as directed graphs, here we consider the undirected version.)