Skip to content Skip to navigation

Speeding up Markov chains with deterministic jumps

Monday, April 27, 2020 - 4:00pm

Speaker:   Persi Diaconis, Stanford Mathematics and Statistics

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