Hands-on: Walking Randomly, on Purpose
The theory says a blind walker settles onto the degree sequence, and that a bottleneck makes it take much longer to get there. Here you watch both happen.
NoteWhere the code lives
This course keeps its lecture note free of runnable code. Everything you execute lives in a marimo notebook, so it stays interactive and reactive instead of being a wall of output frozen into a web page.
Run this notebook — it runs in your browser, with nothing to install and nothing to sign into. The first load takes a few seconds while Python itself is downloaded.
Prefer to work locally? The notebook is in the repository at notebooks/m07-randomwalks/coding.py. Run it with marimo edit notebooks/m07-randomwalks/coding.py.
What you will build
- Build the transition matrix \mathbf{P} = \mathbf{D}^{-1}\mathbf{A} from an adjacency matrix, and check that every row sums to 1.
- Push a distribution forward one step at a time with
x = x @ P, and confirm it against \mathbf{P}^t computed directly. - Plot how far x(t) is from converged, step by step, on a network with two clear communities.
- Compare the converged distribution against the theoretical \pi_i = k_i / 2m.
- Draw the walker’s distribution on the network at t = 0, 1, 3, 5, 10, 299 and watch it leak out of its starting community.
- Take the eigenvalues of the normalized adjacency matrix \overline{\mathbf{A}}, read off \lambda_2, and turn it into a relaxation time \tau = 1/(1-\lambda_2).
- Reconstruct x(t) from the spectral decomposition x(0)\mathbf{Q}_L \mathbf{\Lambda}^t \mathbf{Q}_R^\top and check it against plain power iteration — the appendix explains what those matrices are.
What to watch for
- How many steps convergence takes on a network with two clear communities, versus one without. That difference is the spectral gap made visible.
- Whether your converged vector really equals k_i/2m, entry by entry. If it does not, check whether your network is connected and non-bipartite — those are the two conditions from the concepts page.
- Whether 1/(1-\lambda_2) predicts the number of steps you actually measured in step 3. It should land within a small factor.