Let $X_1, X_2, X_3, \ldots, X_n$ be a sequence of i.i.d. Bernoulli independent random variables each being 1 with probability $p$. For each $t \geq 0$ define $$ S_t := \sum_{i=1}^t X_i. $$ Is my intuition correct that $$ \Pr\left[\exists t : |S_t - pt| \geq \lambda \right] \leq e^{-\frac{C\lambda^2}{pn}}? $$ Note that a simple application of Chernoff bound only gives $$ \Pr\left[|S_n - pn| \geq \lambda \right] \leq e^{-\frac{C\lambda^2}{pn}}. $$
1 Answer
$\begingroup$
$\endgroup$
1
Since $$P(\exists t : |S_t - pt| \ge \lambda) \ge P(|X_1 - p| \ge \lambda) = \begin{cases}0 & \lambda > \max\{p, 1-p\} \\ p & 1-p \ge \lambda > p \\ 1-p & p > \lambda \ge 1-p\\ 1 & \lambda \le \min\{p, 1-p\}\end{cases}$$ you cannot expect your claim to hold without further assumptions (such as a restriction on $\lambda$).
-
$\begingroup$ Thanks. I formalized my question in a bad indirect way. I posted another question and am accepting this one. $\endgroup$– MathmanCommented Mar 1, 2020 at 23:08