A chernoff bound for random walks on expander graphs
| Author(s) : | David Gillman, |
| Publisher : | N/A |
| Publication Date : | 1998 |
| ISSN : | N/A |
| Abstract : | Abstract. We consider a finite random walk on a weighted graph G; we show that the fraction of time spent in a set of vertices A converges to the stationary probability #(A) with error probability exponentially small in the length of the random walk and the square of the size of the deviation from #(A). The exponential bound is in terms of the expansion of G and improves previous results, |