Chernoff bounds for expander walks

Christopher Beck
Member, School of Mathematics
March 10, 2015
Expander walk sampling is an important tool for derandomization. For any bounded function, sampling inputs from a random walk on an expander graph yields a sample average which is quite close to the true mean, and moreover the deviations obtained are qualitatively similar to those obtained from statistically independent samples. The "Chernoff Bound for Expander Walks" was first described by Ajtai, Komlos, and Szemeredi in 1987, and analyzed in a general form by Gilman in 1988.