In the mathematical discipline of graph theory, the expander walk sampling theorem states that sampling vertices in an expander graph by doing a random walk is almost as good as sampling the vertices independently from a uniform distribution. The earliest version of this theorem is due to Ajtai, Komlós & Szemerédi (1987), and the more general version is typically attributed to Gillman (1998).
Let
G
=
(
V
,
E
)
be an expander graph with normalized second-largest eigenvalue
λ
. Let
n
denote the number of vertices in
G
. Let
f
:
V
→
[
0
,
1
]
be a function on the vertices of
G
. Let
μ
=
E
[
f
]
denote the mean of
f
, i.e.
μ
=
1
n
∑
v
∈
V
f
(
v
)
. Then, if we let
Y
0
,
Y
1
,
…
,
Y
k
denote the vertices encountered in a
k
-step random walk on
G
starting at a random vertex
Y
0
, we have the following for all
γ
>
0
:
Pr
[
1
k
∑
i
=
0
k
f
(
Y
i
)
−
μ
>
γ
]
≤
e
−
Ω
(
γ
2
(
1
−
λ
)
k
)
.
Here the
Ω
hides an absolute constant
≥
1
/
10
. An identical bound holds in the other direction:
Pr
[
1
k
∑
i
=
0
k
f
(
Y
i
)
−
μ
<
−
γ
]
≤
e
−
Ω
(
γ
2
(
1
−
λ
)
k
)
.
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. Note that the number of bits used in sampling
k
independent samples from
f
is
k
log
n
, whereas if we sample from an infinite family of constant-degree expanders this costs only
log
n
+
O
(
k
)
. Such families exist and are efficiently constructible, e.g. the Ramanujan graphs of Lubotzky-Phillips-Sarnak.
