## EE Student Information

### The Department of Electrical Engineering supports Black Lives Matter. Read more.

• • • • •

EE Student Information, Spring Quarter through Academic Year 2020-2021: FAQs and Updated EE Course List.

Updates will be posted on this page, as well as emailed to the EE student mail list.

As always, use your best judgement and consider your own and others' well-being at all times.

# Probability Seminar presents "Speeding up Markov chains with deterministic jumps"

Topic:
Speeding up Markov chains with deterministic jumps
Monday, April 27, 2020 - 4:00pm
Speaker:
Persi Diaconis (Stanford Mathematics and Statistics)
Abstract / Description:

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.