0
$\begingroup$

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}}. $$

$\endgroup$

1 Answer 1

2
$\begingroup$

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$).

$\endgroup$
1
  • $\begingroup$ Thanks. I formalized my question in a bad indirect way. I posted another question and am accepting this one. $\endgroup$
    – Mathman
    Commented Mar 1, 2020 at 23:08

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .