Randomized Algorithms (Spring 2010)/Problem Set 4: Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
imported>WikiSysop
imported>WikiSysop
 
(One intermediate revision by the same user not shown)
Line 20: Line 20:
* 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 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.
* 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 <math>n</math> and <math>\epsilon</math>.
* 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 <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 you run the random walk to be within <math>\epsilon</math>-close to the uniform distribution in the worst case?
* Suppose that the maximum degree of <math>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>\epsilon</math>-close to the uniform distribution in the worst case?


== Problem 4 (10 points) ==
== Problem 4 (10 points) ==
An <math>n</math>-dimensional de Bruijn graph <math>G(V,E)</math> is an undirected graph defined as:
An <math>n</math>-dimensional [http://en.wikipedia.org/wiki/De_Bruijn_graph de Bruijn graph] <math>G(V,E)</math> is an undirected graph defined as:
* <math>V=\{0,1\}^n\,</math>;
* <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>.
* <math>uv\in E</math> if <math>u_{i}=v_{i-1}\,</math> for <math>i=2,3,\ldots,n\,</math>.

Latest revision as of 12:38, 19 May 2010

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