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

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

## Problem 2 (10 points)

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

(Note: ${\displaystyle G}$ is NOT necessarily regular.)

## Problem 3 (20 points)

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

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

## Problem 4 (10 points)

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

• ${\displaystyle V=\{0,1\}^{n}\,}$;
• ${\displaystyle uv\in E}$ if ${\displaystyle u_{i}=v_{i-1}\,}$ for ${\displaystyle i=2,3,\ldots ,n\,}$.

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