Timeline for Adaptive version of the Azuma–Hoeffding inequality
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 4, 2016 at 16:02 | comment | added | Douglas Zare | @Aaron: I'm not sure what the right bounds are that depend on $N$. To get good bounds, I think you want an effective version of the law of the iterated logarithm. I've seen an effective version on one side for a simple $\pm 1$ random walk but not both sides in general, so I would have to go back to the proof of the law of the iterated logarithm to try to make that effective. | |
| Jan 4, 2016 at 12:44 | vote | accept | Aaron | ||
| Jan 4, 2016 at 1:31 | comment | added | Iosif Pinelis | Douglas: On another thought, I see now that your $c_k$ depends only on $B_1,\dots,B_{k-1}$, since $c_k=1-I\{\tau\le k-1\}$ -- if indeed $c_k=I\{k\le\tau\}$ is your definition of $c_k$. My problem was to understand, not the law of the iterated logarithm or its consequences, but mainly what your definitions of $\tau$ and $c_k$ were. | |
| Jan 4, 2016 at 0:35 | history | edited | Douglas Zare | CC BY-SA 3.0 |
Fixed typo. Made some trivial changes and clarifications responding to comments..
|
| Jan 4, 2016 at 0:17 | comment | added | Douglas Zare | @Iosif Pinelis: If the first time $t$ so that $X_t \gt s\sqrt{t}$ is $t=5$, then we say $\tau=5$. This sets $c_6=0$, not $c_5=0$. The weight $c_k$ only depends on $B_1,...B_{k-1}$. The fenceposting isn't the point. The point is that you can choose to stop at any number of standard deviations away from the mean with high probability, a weak corollary of the law of the iterated logarithm. Is that part unclear? | |
| Jan 3, 2016 at 22:40 | comment | added | Iosif Pinelis | Can you rewrite this answer in a more formal way? It is difficult for me to follow. In particular, what is the upper limit of the summation in the definition of $\tau$? What is the definition of $c_k$? If $\tau=N\wedge\min\{k\colon\sum_1^k B_i>s\}$ (I guess you meant $s\sqrt k$ here in place of $s$) and $c_k=I\{k\le\tau\}$, then $c_k$ will depend on $B_k$, which was not allowed in the question. | |
| Jan 3, 2016 at 21:36 | comment | added | Aaron | Excellent example. Can you elaborate on your last point? In the special case of choosing a stopping rule, it seems we can give the bound: $\Pr[X_{\tau} \geq s\sqrt{\tau \log n/\delta}] \leq \delta$. Might a similar bound be possible in the general case -- i.e. $\Pr[X_n \geq s\cdot \sqrt{\sum_k c_k^2 \log n/\delta}] \leq \delta$ ? | |
| Jan 3, 2016 at 21:22 | history | answered | Douglas Zare | CC BY-SA 3.0 |