There’s a theorem that says you need about p² 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² steps the distribution is definitely not uniform.
But after p² 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 ≥ p² 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(- π²n / 2p²).
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² steps.
Between p²/2 steps and p² 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.