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]\displaystyle{ p }[/math] and [math]\displaystyle{ q }[/math] be some nonnegative reals with [math]\displaystyle{ p+q\le 1 }[/math]. At each time step, exactly one of the following occurs.

1. If the queue has fewer than [math]\displaystyle{ n }[/math] customers, then with probability [math]\displaystyle{ p }[/math] a new customer joins the queue.
2. If the queue is not empty, then with probability [math]\displaystyle{ q }[/math] 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 [math]\displaystyle{ P }[/math].
• What is the stationary distribution [math]\displaystyle{ \pi }[/math]? Try to explain what the [math]\displaystyle{ \pi }[/math] means in the queuing model.

Problem 2 (10 points)

Let [math]\displaystyle{ G(V,E) }[/math] be an arbitrary connected undirected simple graph (no self-loops and parallel edges) defined on [math]\displaystyle{ n }[/math] vertices. Let [math]\displaystyle{ \pi }[/math] be an arbitrary distribution over [math]\displaystyle{ V }[/math]. Design a time-reversible irreducible aperiodic random walk on [math]\displaystyle{ G }[/math] whose stationary distribution is [math]\displaystyle{ \pi }[/math]. Prove that the random walk is time-reversible, irreducible, aperiodic, and has stationary distribution [math]\displaystyle{ \pi }[/math].

(Note: [math]\displaystyle{ G }[/math] is NOT necessarily regular.)

Problem 3 (20 points)

Let [math]\displaystyle{ G(V,E) }[/math] be a connected undirected simple graph (no self-loops and parallel edges) defined on [math]\displaystyle{ n }[/math] vertices. Let [math]\displaystyle{ \phi(G) }[/math] be the expansion ratio of [math]\displaystyle{ G }[/math]. [math]\displaystyle{ G }[/math] is NOT necessarily regular. For any [math]\displaystyle{ v\in V }[/math], let [math]\displaystyle{ d_v }[/math] be the degree of vertex [math]\displaystyle{ v }[/math].

• What is the largest possible value for [math]\displaystyle{ \phi(G) }[/math]? Construct a graph [math]\displaystyle{ G }[/math] with this expansion ratio and explain why it is the largest.
• What is the smallest possible value for [math]\displaystyle{ \phi(G) }[/math]? Construct a graph [math]\displaystyle{ G }[/math] with this expansion ratio and explain why it is the smallest.
• Run a lazy random walk on [math]\displaystyle{ G }[/math]. What is the stationary distribution? Starting from an arbitrary vertex in an arbitrary unknown [math]\displaystyle{ 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]\displaystyle{ \epsilon }[/math] from the stationary distribution? Give an upper bound of the time in terms of [math]\displaystyle{ n }[/math] and [math]\displaystyle{ \epsilon }[/math].
• Suppose that the maximum degree of [math]\displaystyle{ G }[/math] is known. Modify the random walk to have a uniform stationary distribution. How long should you run the random walk to be within [math]\displaystyle{ \epsilon }[/math]-close to the uniform distribution in the worst case?

Problem 4 (10 points)

An [math]\displaystyle{ n }[/math]-dimensional de Bruijn graph [math]\displaystyle{ G(V,E) }[/math] is an undirected graph defined as:

• [math]\displaystyle{ V=\{0,1\}^n\, }[/math];
• [math]\displaystyle{ uv\in E }[/math] if [math]\displaystyle{ u_{i}=v_{i-1}\, }[/math] for [math]\displaystyle{ 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.)