A Gaussian upper bound for martingale small-ball probabilities
James R. Leea b c d e f g, Yuval Peresb c d e f g h, Charles K. Smartb c d e f g i
- aCOMPUTER SCIENCE UNIVERSITY OF WASHINGTON BOX 352350 185 STEVENS WAY SEATTLE , WASHINGTON 98195 USA
- bUniversity of Washington , Microsoft Research and University of Chicago
- cCOMPUTER SCIENCE UNIVERSITY OF WASHINGTON BOX 352350 185 STEVENS WAY SEATTLE, WASHINGTON 98195 USA
- dS UNIVERSITY AVE CHICAGO, ILLINOIS 60637 USA
- eSMART MATHEMATICS UNIVERSITY OF CHICAGO 5734
- fTHEORY GROUP MICROSOFT RESEARCH ONE MICROSOFT WAY REDMOND, WASHINGTON 98052 USA
- gUniversity of Washington, Microsoft Research and University of Chicago
- hSMART MATHEMATICS UNIVERSITY OF CHICAGO 5734 S UNIVERSITY AVE CHICAGO , ILLINOIS 60637 USA
- iTHEORY GROUP MICROSOFT RESEARCH ONE MICROSOFT WAY REDMOND , WASHINGTON 98052 USA
Papers open inside SciRah from the original publisher or repository; SciRah never hosts them.
Abstract
Consider a discrete-time martingale $\{X_{t}\}$ taking values in a Hilbert space $\mathcal{H}$. We show that if for some $L\geq1$, the bounds $\mathbb{E}[\|X_{t+1}-X_{t}\|_{\mathcal{H}}^{2}\vert X_{t}]=1$ and $\|X_{t+1}-X_{t}\|_{\mathcal{H}}\leq L$ are satisfied for all times $t\geq0$, then there is a constant $c=c(L)$ such that for $1\leq R\leq\sqrt{t}$, \[\mathbb{P}(\|X_{t}-X_{0}\|_{\mathcal{H}}\leq R)\leq c\frac{R}{\sqrt{t}}.\] Following Lee and Peres [Ann. Probab. 41 (2013) 3392–3419], this estimate has applications to small-ball estimates for random walks on vertex-transitive graphs: We show that for every infinite, connected, vertex-transitive graph $G$ with bounded degree, there is a constant $C_{G}>0$ such that if $\{Z_{t}\}$ is the simple random walk on $G$, then for every $\varepsilon>0$ and $t\geq1/\varepsilon^{2}$, \[\mathbb{P}(\mathsf{dist}_{G}(Z_{t},Z_{0})\leq \varepsilon \sqrt{t})\leq C_{G}\varepsilon,\] where $\mathsf{dist}_{G}$ denotes the graph distance in $G$.