Random walks mix faster on some graphs than on others. Rapid mixing is one of the ways to characterize **expander graphs**.

By rapid mixing we mean that a random walk approaches its limiting (stationary) probability distribution quickly relative to random walks on other graphs.

Here’s a graph that supports rapid mixing. Pick a prime *p* and label nodes 0, 1, 2, 3, …, *p* − 1. Create a circular graph by connecting each node *k* to (*k *+ 1) mod *p*. Then add an edge between each non-zero *k* to its multiplicative inverse mod *p*. If an element is its own inverse, add a loop connecting the node to itself. For the purpose of this construction, consider 0 to be its own inverse. This construction comes from [1].

Here’s what the graph looks like with *p* = 23.

This graph doesn’t show the three loops from a node to itself, nodes 1, 0, and 22.

At each node in the random walk, we choose an edge uniformly and follow it. The stationary distribution for a random walk on this graph is uniform. That is, in the long run, you’re equally likely to be at any particular node.

If we pick an arbitrary starting node, 13, and take 30 steps of the random walk, the simulated probability distribution is nearly flat.

By contrast, we take a variation on the random walk above. From each node, we move left, right, or stay in place with equal probability. This walk is not as well mixed after 100 steps as the original walk is after only 30 steps.

You can tell from the graph that the walk started around 13. In the previous graph, evidence of the starting point had vanished.

The code below was used to produce these graphs.

To investigate how quickly a walk on this graph converges to its limiting distribution, we could run code like the following.

from random import random import numpy as np import matplotlib.pyplot as plt m = 23 # Multiplicative inverses mod 23 inverse = [0, 1, 12, 8, 6, 14, 4, 10, 3, 18, 7, 21, 2, 16, 5, 20, 13, 19, 9, 17, 15, 11, 22] # Verify that the inverses are correct assert(len(inverse) == m) for i in range(1, m): assert (i*inverse[i] % 23 == 1) # Simulation num_reps = 100000 num_steps = 30 def take_cayley_step(loc): u = random() * 3 if u < 1: # move left newloc = (loc + m - 1) % m elif u < 2: # move right newloc = (loc + 1) % m else: newloc = inverse[loc] # or newloc = loc return newloc stats = [0]*m for i in range(num_reps): loc = 13 # arbitrary fixed starting point for j in range(num_steps): loc = take_cayley_step(loc) stats[loc] += 1 normed = np.array(stats)/num_reps plt.plot(normed) plt.xlim(1, m) plt.ylim(0,2/m) plt.show()

## Related posts

* * *

[1] Shlomo Hoory, Nathan Linial, Avi Wigderson. “Expander graphs and their applications.” Bulletin of the American Mathematical Society, Volume 43, Number 4, October 2006, pages 439–561.