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

- Compute the stationary distribution of this Markov chain, and show whether it is or is not reversible.
- 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 ε ≤ q_{ij} ≤ p_{ij} for some constant ε ≥ 0, and suppose that Q is also reversible.

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 ε.Compute the best upper and lower bounds you can on the conductance Φ

_{Q}of Q.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.

- Compute the stationary distribution of this walk as a function of the f(i).
- 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.