[FrontPage] [TitleIndex] [WordIndex

Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

/Solutions

1. String evolution

A scribe repeatedly copies a string of bits. Whenever he recopies the string, he either copies it correctly (with probability 1/2), deletes the last bit (with probability 1/3; if the string has length 0, he copies it correctly in this case); or adds a new bit (with probability 1/12 each for adding a 0 or adding a 1).

The sequence of bit strings generated by the scribe can easily be seen to be a Markov chain, since each string depends only on its immediate predecessor.

  1. Compute the stationary distribution of this Markov chain, and show whether it is or is not reversible.
  2. Suppose we start with the empty string. Compute a bound on the rate of convergence to the stationary distribution, showing an upper bound on the expected time until the total variation distance drops below some small constant ε.

2. Perturbing a chain

Let P be the transition matrix of a reversible Markov chain with conductance ΦP and diameter d, where the diameter is the maximum number of steps needed to reach any state from any other state.

Suppose we replace P with a new Markov chain Q where ε ≤ qij ≤ pij for some constant ε ≥ 0, and suppose that Q is also reversible.

  1. Let x be some state of P and Q. Compute the best upper and lower bounds you can on πQ(x) as a function of πP(x), d, and ε. Hint: First compute bounds on πQ(y)/πQ(x) as a function of πP(y)/πP(x),,, d, and ε.

  2. Compute the best upper and lower bounds you can on the conductance ΦQ of Q.

  3. Suppose that you are not told ΦP, but are told τ2(P). What can you say about τ2(Q), using your previous bound on ΦQ?

3. A sticky chain

Consider a random walk on a cycle of n nodes, where at each step we remain on node i with probability f(i), where 1/2 ≤ f(i) ≤ 1-δ, for some constant δ > 0, and move to node i-1 or i+1 with probability (1-f(i))/2 each.

  1. Compute the stationary distribution of this walk as a function of the f(i).
  2. Give the best bound you can as a function of n and δ on the time to converge to within some fixed ε of the stationary distribution, starting from an arbitrary node.

2014-06-17 11:58