Are the visited vertices independent?

Generally no; the transition uses the current vertex.

Must the graph be stored in full?

Not necessarily. Explicit constructions can compute neighbors efficiently.

Does rapid mixing mean every sample path is representative?

No. Guarantees bound probabilities of deviations; unusual paths remain possible.

AI Glossary / Statistics and probability / Advanced

Expander walk sampling

Definition

Expander walk sampling is a method of generating useful samples by following a random walk on a suitably well-connected graph called an expander. Under appropriate graph and starting-distribution conditions, averages of bounded functions along the walk can concentrate near their target mean despite dependence between samples. Its central attraction is randomness efficiency: each additional sample may require far fewer new random bits than an independent draw.

What it means

Imagine an enormous set of possible random seeds for an algorithm. Choosing every seed independently can use many random bits. An expander connects each seed to a small number of neighbors, allowing a walk to choose its next seed with relatively few additional bits.
The samples are dependent. The mathematical result is that certain sampling tasks still have useful accuracy guarantees under this structured dependence. It does not say that the entire sequence is indistinguishable from independent draws for every possible purpose.

How it works

Represent the sampling domain by vertices of a graph and assign the quantity of interest to each vertex. For estimating a proportion, the function can be one for vertices having a property and zero elsewhere. More generally, many theorems consider functions bounded between zero and one.
Choose a graph with the required expansion and an efficient way to compute neighbors. For a regular undirected graph, the uniform distribution is stationary. A uniform starting vertex therefore makes each position marginally uniform, even though adjacent positions remain dependent.
If the walk starts at a fixed vertex, account for its initial distribution and mixing before applying a guarantee that assumes a uniform start. Connectivity alone is insufficient. Periodicity can also interfere with convergence; suitable laziness or other construction choices address it.
At each step, use fresh random bits to select an outgoing edge. Evaluate the function at the visited vertices and compute the average. The relevant concentration guarantee depends on the graph's spectral properties, walk length, function bounds, and initialization.
For N vertices and degree d, choosing k independent uniform vertices uses k log₂N bits when these counts are powers of two. A uniform start followed by k − 1 neighbor choices uses log₂N + (k − 1)log₂d bits. Non-power-of-two choices require appropriate unbiased sampling and can change the exact accounting.
Randomness cost is not the same as running time, memory, or statistical efficiency. Constructing or storing a huge graph explicitly can defeat the purpose. Useful constructions provide neighbor access without listing every vertex and edge. Evaluate this implementation cost as well as the theorem's assumptions before claiming practical savings.

Three practical examples

A theoretical randomized algorithm repeats trials using seeds obtained from an expander walk to reduce error with fewer random bits.
A research sampler estimates the fraction of a finite domain satisfying a predicate while using a bounded-degree graph.
A computing team investigates whether an explicitly constructed expander can support a specialized sampling component with documented concentration guarantees.

Think of it this way

Think of exploring a city through a carefully designed network of short connections. A good network lets local moves cover the city effectively, but your route still depends on where you were a moment ago.

Worked example

Suppose an explicitly supplied regular expander has N = 2²⁰ vertices and degree d = 8. Assume a uniform initial vertex, uniform independent edge choices, and an efficient neighbor routine. We want k = 100 visited vertices, including the start.
Independent vertex selection requires 100 × 20 = 2,000 random bits. The walk requires 20 bits for its initial vertex and 99 × 3 = 297 bits for the remaining edge choices: 317 bits altogether.
The difference is 1,683 bits, or 84.15% of the independent-selection total. This is an accounting example, not a construction of that graph or proof that 100 samples meet a chosen tolerance.
If 28 visited vertices satisfy a predicate, the observed proportion is 0.28. An ordinary independent-binomial uncertainty calculation is not automatically justified. A suitable expander-walk bound must incorporate the graph and the sampling scheme.

Illustrative case study

Fictional case: Cedar Algorithms investigates a sampler for a simulation service whose random-seed domain is very large. Engineers first demonstrate the random-bit savings on paper. They then discover that a proposed graph representation consumes too much memory, so they investigate an explicit neighbor algorithm and test its implementation. The team keeps statistical guarantees separate from measured runtime. This invented case illustrates why theoretical savings require a usable construction.

Common misconceptions and mistakes

Do not assume a walk on any sparse graph is an expander sampler. A long chain or a graph with bottlenecks can mix slowly.
Uniform marginal distributions do not imply independent samples. Nor does a stationary distribution guarantee that a fixed starting point already follows it.
A pseudorandom generator and an expander-walk sampler serve related but different purposes. Neither a short random-bit budget nor a concentration theorem alone establishes cryptographic security or suitability for arbitrary AI training procedures.

Business use

The business relevance is mostly indirect, through specialized randomized algorithms and research infrastructure. Teams considering the method should compare random-bit requirements, graph operations, accuracy guarantees, and maintenance costs. It is not a general replacement for ordinary survey sampling or routine machine-learning minibatches, and claimed savings should identify the resource actually reduced.

Check your understanding

Why do 100 visited vertices require only 99 moves?

Answer: The first vertex is selected before the walk begins.

What makes uniformity stationary in the stated setting?

Answer: Regular undirected transitions preserve uniform probability.

What is missing from the numerical example's accuracy claim?

Answer: Graph spectral information and a theorem connecting it to the requested tolerance and failure probability.

Related terms

Random walk
Stationary distribution
Concentration inequality
Expander graph
spectral gap
averaging sampler
pseudorandomness
derandomization

Learn next

Learn finite Markov chains and stationary distributions, then study spectral expansion. Read an expander-walk concentration theorem carefully, especially its initialization and bounded-function assumptions.

Sources

Salil Vadhan, Pseudorandomness, Section 4.2: https://people.seas.harvard.edu/~salil/pseudorandomness/pseudorandomness-published-Dec12.pdf Primary research, “A Sharp Tail Bound for the Expander Random Sampler”: https://arxiv.org/abs/1703.10205

Previous: Expand (pyramid operator) Next: Expectation conditional maximization