Convergence rate of random walk on integers mod p
Consider a random walk on the integers mod p. At each step, you either take a step forward or a step back, with equal probability. After just a few steps, you'll have to be near where you started. After a few more steps, you could be far from your starting point, but you're probably not. But eventually, every point is essentially equally likely.
How many steps would you have to take before your location is uniformly distributed? There's a theorem that says you need about p^2 steps. We'll give the precise statement of the theorem shortly, but first let's do a simulation.
We'll take random walks on the integers mod 25. You could think of this as a walk on a 24-hour clock, with one extra hour squeezed in. Suppose we want to take N steps. We would generate a +1 or -1 at random, add that to our current position, and reduce mod 25, doing that N times. That would give us one outcome of a random walk with N steps. We could do this over and over, keeping track of where each random walk ended up, to get an idea how the end of the walk is distributed.
We will do an optimization to speed up the simulation. Suppose we generated all our +1s and -1s at once. Then we just need to add up the number of +1's and subtract the number of -1's. The number n of +1's is a binomial(N, 1/2) random variable, and the number of +1's minus the number of -1's is 2n - N. So our final position will be
(2n - N) mod 25.
Here's our simulation code.
from numpy import zeros from numpy.random import binomial import matplotlib.pyplot as plt p = 25 N = p*p//2 reps = 100000 count = zeros(p) for _ in range(reps): n = 2*binomial(N, 0.5) - N count[n%p] += 1 plt.bar(range(p), count/reps) plt.show()
After doing half of p^2 steps the distribution is definitely not uniform.
But after p^2 steps the distribution is close to uniform, close enough that you start to wonder how much of the lack of uniformity is due to simulation.
Now here's the theorem I promised, taken from Group Representations in Probability and Statistics by Persi Diaconis.
For n a p^2 with p odd and greater than 7, the maximum difference between the random walk density after n steps and the uniform density is no greater than exp(- I^2n / 2p^2).
There is no magic point at which the distribution suddenly becomes uniform. On the other hand, the difference between the random walk density and the uniform density does drop sharply at around p^2 steps. Between p^2/2 steps and p^2 steps the difference drops by almost a factor of 12.
More random walk posts- A knight's random walk
- Random walk on quaternions
- Random walks and the arcsine law
- Rapidly mixing random walks
- Per stirpes inheritance and random walks