A Sharp Tail Bound for the Expander Random Sampler

Shravas Rao, Oded Regev

Consider an expander graph in which a $\mu$ fraction of the vertices are marked. A random walk starts at a uniform vertex and at each step continues to a random neighbor. Gillman sho…