随机算法 (Fall 2011)/Chernoff Bound for Expander Walks

Random Walks Resemble Independent Sampling

Theorem (Ajtai-Komlós-Szemerédi 1987, Alon-Feige-Wigderson-Zuckerman 1995)

Let [math]\displaystyle{ G(V,E) }[/math] be an [math]\displaystyle{ n }[/math]-vertex graph, and [math]\displaystyle{ B\subseteq V }[/math] with [math]\displaystyle{ |B|=\beta n }[/math]. Pick [math]\displaystyle{ X_0\in V }[/math] uniformly at random and start a random walk [math]\displaystyle{ X_0,X_1,\ldots,X_t }[/math] on [math]\displaystyle{ G }[/math]. The probability that the random walk is confined in [math]\displaystyle{ B }[/math] is bounded by [math]\displaystyle{ \Pr[\forall 0\le i\le t, X_i\in B]\le(\beta+\frac{\lambda_2}{d})^t }[/math].