Let $X\_k$ be a sequence of *iid* Bernoulli random variables of parameter $p$ and let $\hat{X}\_n=\frac1n\sum\_{k=1}^nX\_k$. Hoeffding's inequality states that for any $n$:
$$\mathbb{P}(\hat{X}\_n - p \ge \epsilon) \le e^{-2n\epsilon^2},$$
or said otherwise:
$$\mathbb{P}(\hat{X}\_n - p \ge \frac{\epsilon}{\sqrt{n}}) \le e^{-2\epsilon^2}.$$


The above holds if $n$ is deterministic. My question is: does it still hold if $n$ is a bounded stopping time? By bounded, I mean that there exists $T$ such that $n\le T$ a.s.



Hoeffing inequality is not true for stopping time
In fact, the answer is indeed contained in the question:


Let $N$ be the stopping time:
$$ N = \inf\{n : \hat{X}\_n - p \ge \frac{\epsilon}{\sqrt{n}}\}.$$
$N$ is finite almost surely (for instance, this is a consequence of the law of iterated logarithm). This shows that $$P( \hat{X}\_N - p \ge \frac{\epsilon}{\sqrt{N}} ) = 1,$$
which violates Hoeffding’s inequality for all $\epsilon$ such that $e^{-2\varepsilon^2}<1$.


Simulation indicates that the result is similar for $\tilde{N} = \min(N, T)$, when $T$ is large enough (e.g. when $p=0.5$, $\epsilon=1$ and $T=100$).


