# Chernoff-type bounds for a stopped sum of independent random variables

Let $$Y_1, \ldots, Y_n$$ and $$X_1, \ldots, X_n$$ be i.i.d. $$p$$-Bernoulli random variables and let $$T \in \{0, \ldots, n\}$$ be a stopping time for the process. From Wald's equation, we know $$E\left[\sum_{i=1}^T Y_i \right] = E\left[\sum_{i=1}^T X_i \right] = p \times E[T].$$ On the other hand, if $$T$$ was not itself a random variable, a standard Chernoff bound would give that for $$\mu = pT$$ and any $$0 < \delta < 1$$, with probability $$\geq 1-\exp(-\delta^2 \mu/3)$$ we have $$\sum_{i=1}^T Y_i \in (1\pm \delta) \sum_{i=1}^T X_i.$$ Now going back to $$T$$ being a stopping time and not known a priori, can we get a similar concentration bound? That is, letting $$\mu$$ be a given lower bound for the expected* actual value of $$\sum_{i=1}^T X_i$$, does the statement above still hold?

Note: One could try to apply Chernoff bound over all $$n$$ choices of $$T$$ and set the failure probability small enough that with high probability, no matter the value of $$T$$, sum of the two sequences are close up to any point. Unfortunately, though, to be able to do this, the error probability would have to depend on $$n$$ whereas the original bound is dimension-free. Is there any better way to do this?

*For $$\mu$$ being a lower bound for the expected value of the sum instead of its actual value, the statement is wrong. See Iosif Pinelis's answer.

• What does the notation $U \in (1\pm \delta)V$ mean? Is it $(1-\delta)V \le U \le (1+\delta)V$? Mar 4 '20 at 18:09
• @NateEldredge Correct. Mar 4 '20 at 18:49

The desired statement will not hold. E.g., suppose that $$n\ge2$$; $$X_1,\dots,X_n,Y_1,\dots,Y_n$$ are independent; $$p=1/2$$; $$T=1_{X_1\ne Y_1}+n1_{X_1=Y_1}$$; and $$\delta=1/2$$. Then $$\mu:=p\,ET>n/4\to\infty$$ (as $$n\to\infty$$), so that $$1-\exp(-c\delta^2\mu )\to1$$ for any fixed $$c>0$$. However, $$P\Big(\sum_{i=1}^TY_i\notin(1\pm\delta)\sum_{i=1}^TX_i\Big) \ge P(T=1)=1/2\not\to0;$$ so, it is not true that $$P\Big(\sum_{i=1}^TY_i\in(1\pm\delta)\sum_{i=1}^TX_i\Big)\to1.$$

• Great point. I should have emphasized that $\mu$ is a lower bound on the actual value of $\sum_{i=1}^T X_i$, not on its expected value. Edited the question. Mar 4 '20 at 23:54
• For more reasons than one, you should not change your question so as to invalidate a valid answer. In such cases, you may want to post the new question separately. Anyhow, concerning your changed question: if now $\mu$ is defined as the exact lower bound on the sum $\sum_{i=1}^T X_i$ itself, then $\mu$ is always $0$: this lower bound on $\sum_{i=1}^T X_i$ is attained when all the $X_i$'s take value $0$. So, then your desired lower bound $1-\exp(-\delta^2 \mu/3)$ on the probability is just the trivial bound $0$. Mar 5 '20 at 4:33
• That is a valid point. I am thinking about the answer of user36212 at the same time. If it doesn't already answer the question with the deterministic lower bound on the sum, I'm going to post a new question. Thanks again. Mar 5 '20 at 4:59
• In the above comment, I have already answered your question with the deterministic lower bound on the sum. Mar 5 '20 at 5:30
• Oh I see. I was going to say that we condition on $\mu$ being large, but that also can't hold because then we can condition on a very rare event. Thanks. Mar 5 '20 at 13:56

What you’re asking isn’t quite true. To see this, let p=1/2 and the stopping rule for $$T$$ be the first time that $$T>n/2$$ and the sum of the $$X_i$$ exceeds T/2 by $$c\sqrt{n}\log n$$. Choosing $$c>0$$ sensibly, this event likely occurs; when it does then with probability at least 1/2 the sum of the $$X_i$$ exceeds the sum of the $$Y_i$$ by at least $$c\sqrt{n}\log n$$. But your formula says this should happen with probability going (slowly) to zero.

The point is basically that you need to take the $$n$$ steps into account in your probability bound.

• Thanks, this was also a very good answer, wish I could accept two answers. Mar 5 '20 at 13:57