# Randomized Algorithms (Spring 2010)/Problem Set 4

## Contents

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