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 *n*^{2} steps to get random. Now make a slight modification: *X*(*k*+1) = 2*X*(*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.