In the mathematical

Mathematics

Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

 discipline of graph theory

Graph theory

In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...

, the expander walk sampling theorem states that sampling

Sampling (statistics)

In statistics and survey methodology, sampling is concerned with the selection of a subset of individuals from within a population to estimate characteristics of the whole population....

 vertices in an expander graph

Expander graph

In combinatorics, an expander graph is a sparse graph that has strong connectivity properties, quantified using vertex, edge or spectral expansion as described below...

 by doing a random walk is almost as good as sampling the vertices independently

Statistical independence

In probability theory, to say that two events are independent intuitively means that the occurrence of one event makes it neither more nor less probable that the other occurs...

 from a uniform distribution.
The earliest version of this theorem is due to , and the more general version is typically attributed to .

Statement

Let be an expander graph with normalized second-largest eigenvalue . Let denote the number of vertices in . Let be a function on the vertices of . Let denote the true mean of , i.e. . Then, if we let denote the vertices encountered in a -step random walk on starting at a random vertex , we have the following for all :


Here the hides an absolute constant . An identical bound holds in the other direction:

Uses

This theorem is useful in randomness reduction in the study of derandomization. Sampling from an expander walk is an example of a randomness-efficient sampler

Sample (statistics)

In statistics, a sample is a subset of a population. Typically, the population is very large, making a census or a complete enumeration of all the values in the population impractical or impossible. The sample represents a subset of manageable size...

. Note that the number of bits

BITS

BITS or bits may refer to:* Plural of bit* Background Intelligent Transfer Service, a file transfer protocol* Birla Institute of Technology and Science, a technology school in Pilani, Rajasthan, India, with campuses in Goa, Hyderabad, and Dubai...

 used in sampling independent samples from is , whereas if we sample from an infinite family of constant-degree expanders this costs only . Such families exist and are efficiently constructible, e.g. the Ramanujan graph

Ramanujan graph

A Ramanujan graph, named after Srinivasa Ramanujan, is a regular graph whose spectral gap is almost as large as possible . Such graphs are excellent spectral expanders....

s of Lubotzky

Alexander Lubotzky

Professor Alexander Lubotzky is an Israeli academic and former politician. A former head of the Mathematics Institute at the Hebrew University of Jerusalem, he served as a member of the Knesset for The Third Way party between 1996 and 1999.-Education:...

-Phillips-Sarnak.

External links

• Proofs of the expander walk sampling theorem. http://citeseer.ist.psu.edu/gillman98chernoff.html http://projecteuclid.org/Dienst/UI/1.0/Summarize/euclid.aoap/1028903453