Tail estimates for sums of variables sampled from a random walk
| dc.creator | Wagner, Roy | |
| dc.date | 2006-08-30 | |
| dc.date | 2007-12-25 | |
| dc.date.accessioned | 2026-07-07T08:50:59Z | |
| dc.date.available | 2026-07-07T08:50:59Z | |
| dc.description | We prove tail estimates for variables $\sum_i f(X_i)$, where $(X_i)_i$ is the trajectory of a random walk on an undirected graph (or, equivalently, a reversible Markov chain). The estimates are in terms of the maximum of the function $f$, its variance, and the spectrum of the graph. Our proofs are more elementary than other proofs in the literature, and our results are sharper. We obtain Bernstein and Bennett-type inequalities, as well as an inequality for subgaussian variables. | |
| dc.description | V4: published version; theorems 1&2 slightly revised V3: Improved Bennett inequality V2: Corrected version. Confusion concerning definition of $β$ resolved. Results given both in terms of sepctral gap and second largest absolute value of an eigenvalue. Sign error in statement of Theorem 4 corrected. Other minor and cosmetic corrections included as well | |
| dc.identifier | https://arxiv.org/abs/math/0608740 | |
| dc.identifier | http://arxiv.org/abs/math/0608740 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/144785 | |
| dc.subject | Probability | |
| dc.subject | 60F10 | |
| dc.title | Tail estimates for sums of variables sampled from a random walk | |
| dc.type | text |