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

## 1.1. Solution

1. Organize the strings into a binary tree, where each string x is the parent of x0 and x1. The process then describes a random walk on this tree, with a probability of 1/3 of going up and 1/12 of going down to each child. Let's guess that the process is reversible; then we have π(x)(1/12) = π(xb)(1/3) for b=0,1, giving π(xb) = π(x)/3 and in general π(x) = π(<>) 3^{-x} where π(<>) is the stationary probability of the empty string. Summing over all strings gives ∑_{n} π(<>) 2^{n}3^{-n} = π(<>) ∑_{n} (2/3)^{n} = 3π(<>) = 1. This gives π(<>) = 1/3, and so in general we have π(x) = 3^{-|x|-1}. Because this distribution satisfies the detailed balance equations (we proved it using them), it is a stationary distribution and the process is reversible.

2. We'll set up a coupling in the simplest way imaginable: given X_{t} and Y_{t}, we either delete a bit from both (probability 1/3), add the same bit to both (probability 1/6), or do nothing. We will then argue that X_{t} and Y_{t} are linked as soon as |X_{t}| = |Y_{t}| = 0. To analyze when this occurs, observe that Z_{t} = max(|X_{t}|, |Y_{t}|) moves as a biased random walk with a reflecting barrier at 0, and probability 1/3 of dropping and 1/6 of rising, for an expected change of -1/6 per time unit. It follows that Z_{t}+min(t,τ)/6 is a martingale, where τ is the stopping time at which Z_{τ} = 0. Since we have bounded increments, the optional stopping theorem applies, and E[Z_{τ}] = E[Z_{0}], giving E[τ] = 6 E[Z_{0}].

We now need to compute E[Z_{0}]. We have |X_{0}| = 0, but for |Y_{0}| we have a probability distribution that assigns probability 2^{n}3^{-n-1} to |Y_{0}| = n. So we have E[Z_{0}] = ∑_{n=0..∞} n 2^{n}3^{-n-1} = (2/9) ∑ n (2/3)^{n-1} = (2/9) (1/(1-(2/3))^{2} = 2. This gives E[τ] = 12, and using Markov's inequality we get d_{TV}(X_{24}, π) ≤ 1/2.

# 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}?

## 2.1. Solution

Consider some shortest path x = x0 x1 x2 ... xk = y from x to y; here k≤d. Because P is reversible, we have π

_{P}(y) = π_{P}(x) ∏_{i}p_{x(i) x(i+1)}/p_{x(i+1) x(i)}. Similarly π_{Q}(y) = π_{Q}(x) ∏_{i}q_{x(i) x(i+1)}/q_{x(i+1) x(i)}. But then ε^{d}π_{P}(y) / π_{P}(x) ≤ π_{Q}(y)/π_{Q}(x) ≤ ε^{-d}π_{P}(y)/π_{P}(x). Since we have 1 = ∑ π_{Q}(y) = π_{Q}(x) ∑ π_{Q}(y)/π_{Q}(x), we can compute π_{Q}(x) = 1/(∑ π_{Q}(y)/π_{Q(x)}) = c / (∑ π_{P}(y)/π_{P}(x)) where ε^{d}≤ c ≤ ε^{-d}. So this gives ε^{d}π_{P}(x) ≤ π_{Q}(x) ≤ ε^{-d}π_{P}(x).Let S be such that Φ

_{Q}= Φ_{Q}(S) = (1/π_{Q}(S)) ∑_{x∈S,y∉S}π_{Q}(x) q_{xy}. We have that ε p_{xy}≤ q_{xy}≤ p_{xy}, ε^{d}π_{P}(S) ≤ ε^{-d}π_{P}(S), and for each x, ε^{d}π_{P}(x) ≤ π_{Q}(x) ≤ ε^{-d}π_{P}(x). Multiplying all these ε's together gives Φ_{Q}= Φ_{Q}(S) ≥ (1/ε^{-d}π_{P}(S)) ∑_{x∈S y∉S}ε^{d}π_{P}(x) ε p_{xy}= ε^{2d+1}Φ_{P}(S) ≥ ε^{2d+1}Φ_{P}. Reversing the argument gives Φ_{P}= Φ_{P}(S') = (1/π_{P}(S')) ∑_{x∈s,y∉s}π_{P}(x) p_{xy}≥ (1/ε^{-d}π_{Q}(S')) ∑_{x∈S' y∉S'}ε^{d}π_{Q}(x) q_{xy}= ε^{2d}Φ_{Q}(S') ≥ ε^{2d}Φ_{Q}. Combining the two bounds gives ε^{2d+1}Φ_{P}≤ Φ_{Q}≤ ε^{-2d}Φ_{P}.We have 1/2Φ

_{P}≤ τ_{2}(P) ≤ 2/Φ^{2}(P), which gives 1/2τ_{2}(P) ≤ Φ_{P}≤ √(2/τ_{2}(P)). Applying the previous bound gives ε^{2d+1}/2τ_{2}(P) ≤ Φ_{Q}≤ ε^{-2d}√(2/τ_{2}(P)). Plugging this back in to the bound on τ_{2}(Q) gives (ε^{2d}/2√2) (τ_{2}(P))^{1/2}≤ τ_{2}(Q) ≤ 8ε^{-4d-2}(τ_{2}(P))^{2}.

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

## 3.1. Solution

Let's guess that the chain is reversible. Then we have π(i+1) = π(i) (1-f(i))/(1-f(i+1)) and in general π(i) = π(0) ∏

_{j<i}(1-f(j))/(1-f(j+1)). We can check that this is consistent by computing π(0) = (1-f(n-1))/(1-f(0)) π(0) ∏_{j<n-1}(1-f(j))/(1-f(j+1)) = π(0) ∏_{j}(1-f(j)) / ∏_{j}(1-f(j)) = π(0).We use a coupling based on the standard coupling for a lazy uniform walk on the cycle. If X

_{t}= Y_{t}, we move both together. Otherwise, given X_{t}= i, Y_{t}= j, we move X_{t}only with probability 1-f(i) and Y_{t}only with probability 1-f(j) (these probabilities sum to at most 1 because f(i) ≥ 1/2 for all i). So now Z_{t}= X_{t}- Y_{t}(mod n) satisfies E[Z_{t+1}] = E[Z_{t}], |Z_{t+1}-Z_{t}| ≤ 1, and Pr[Z_{t+1}≠Z_{t}|Z_{t}≠0 (mod n)] ≥ 2δ. It follows that Z_{t∧τ}^{2}- 2δ(t∧τ) is a submartingale, where τ = min_{t}Z_{t}= 0 or n. Optional stopping applies because of bounded increments, so we have E[Z_{τ}^{2}- 2δτ] ≥ E[Z_{0}^{2}], giving E[τ] ≤ n^{2}/2δ (the constant can probably be improved a bit). So taking τ_{1}= n^{2}/δ gives d_{TV}(X_{τ₁},π) ≤ 1/2.