Speeding up Markov chains with deterministic jumps

Abstract:   A striking example of the phenomenon: Consider simple random walk on the integers mod n [X(k+1)] = X(k) + epsilon(k+1)(mod n) where epsilon takes values {0,1,-1} with probability 1/3 each. This walk takes order n^2 steps to get random. Now make a slight modification: X(k+1) = 2X(k) + epsilon(k+1) (mod n). This has the same amount of randomness BUT, for almost all n, the walk gets random in order log(n) steps.

In joint work with Sourav Chatterjee we show this as quite a general phenomenon. For any doubly stochastic Markov chain on n states and any permutation f(x) on the state space, the walk that goes from x to f(x) to y, where y is one step of the chain, mixes in order log (n) states for almost all permutations f. Since it happens for most f, this raises the problem of finding specific f for real problems. Some progress will be reported.