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 and be some nonnegative reals with . At each time step, exactly one of the following occurs.
- If the queue has fewer than customers, then with probability a new customer joins the queue.
- If the queue is not empty, then with probability 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 .
- 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.)