Return to the Origin

A simple random walk on the hypercube Q_n starts at 000…0 and takes ℓ steps, each flipping one coordinate chosen uniformly at random. How often is it home at the end?

dimension n

steps ℓ

steps per second 8

walks

returned

expected returns

0.0

observed frequency

—

no walks yet

expected probability

—

p_{ℓ} = \frac{1}{2^{n} n^{ℓ}} \sum_{i = 0}^{n} (\binom{n}{i}) {(n - 2 i)}^{ℓ}

Observed frequency against walks sampled

hover for values

Made for Math 372: Combinatorics at Reed College, fall 2026. The closed form is the spectral count of closed walks on the cube, divided by the number of walks: tr A^ℓ / (2ⁿ n^ℓ). Part of e-infinity.space/viz.