View source for Randomized Algorithms (Spring 2010)/Problem Set 4

== Problem 1 (10 points) ==
Consider the following queuing model. Customers are waiting in a line for some service. Let <math>p</math> and <math>q</math> be some nonnegative reals with <math>p+q\le 1</math>. At each time step, exactly one of the following occurs.
#If the queue has fewer than <math>n</math> customers, then with probability <math>p</math> a new customer joins the queue.
#If the queue is not empty, then with probability <math>q</math> the head of the line is served and leaves the queue.
#With remaining probability, the queue is unchanged.

*Represent this model by a Markov chain. Define the state space and the transition matrix <math>P</math>.
*What is the stationary distribution <math>\pi</math>? Try to explain what the <math>\pi</math> means in the queuing model.


== Problem 2 (10 points) ==
Let <math>G(V,E)</math> be an arbitrary connected undirected simple graph (no self-loops and parallel edges) defined on <math>n</math> vertices. 
Let <math>\pi</math> be an arbitrary distribution over <math>V</math>. Design a time-reversible irreducible aperiodic random walk on <math>G</math> whose stationary distribution is <math>\pi</math>. Prove that the random walk is time-reversible, irreducible, aperiodic, and has stationary distribution <math>\pi</math>.

('''Note''': <math>G</math> is NOT necessarily regular.)


== Problem 3 (20 points) ==
Let <math>G(V,E)</math> be a connected undirected simple graph (no self-loops and parallel edges) defined on <math>n</math> vertices. Let <math>\phi(G)</math> be the expansion ratio of <math>G</math>. <math>G</math> is NOT necessarily regular. For any <math>v\in V</math>, let <math>d_v</math> be the degree of vertex <math>v</math>.
* What is the largest possible value for <math>\phi(G)</math>? Construct a graph <math>G</math> with this expansion ratio and explain why it is the largest.
* 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 only <math>n</math> and <math>\epsilon</math>.
* Suppose that the maximum degree of <math>G</math> is known. Modify the random walk to have a uniform stationary distribution. How long should run to be within <math>\epsilon</math>-close to uniform distribution in the worst case?


== Problem 4 (10 points) ==
An <math>n</math>-dimensional de Bruijn graph <math>G(V,E)</math> is an undirected graph defined as:
* <math>V=\{0,1\}^n\,</math>;
* <math>uv\in E</math> if <math>u_{i}=v_{i-1}\,</math> for <math>i=2,3,\ldots,n\,</math>.

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.)