# 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, 2020 at 18:09
• @NateEldredge Correct. Mar 4, 2020 at 18:49

## 3 Answers

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, 2020 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, 2020 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, 2020 at 4:59
• In the above comment, I have already answered your question with the deterministic lower bound on the sum. Mar 5, 2020 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, 2020 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, 2020 at 13:57

The two answers so far may give the impression that bounds in the desired spirit (Chernoff-like bounds for sums with stopping times) are not possible. But useful bounds in this spirit can indeed be shown. Here is one such bound.

It differs from the requested bound in that it allows an additional additive difference between the two sums. Perhaps counterintuitively, it holds not just for a stopping time $$T$$, but for all $$T$$.

Request: If anybody knows of published results similar to Theorems 1 or 2 below, please leave a reference in the comments, thanks.

Chernoff-like bound for super-martingales

Suppose a discrete-time system goes through a random sequence of states $$S_1, S_2, S_3, \ldots$$, where each state $$S_t$$ determines two values $$x_t$$ and $$y_t$$, each in $$[0,1]$$, such that the expectation of $$x_t$$ is at most that of $$y_t$$: $$E[x_t - y_t\, |\, S_{t-1}] \,\le\, 0.$$ Then it is unlikely that, for any $$T$$, the sum $$\sum_{t=1}^T x_t$$ significantly exceeds $$\sum_{t=1}^T y_t$$:

Theorem 1. Given the conditions above, fix $$\epsilon,\mu\ge 0$$ arbitrarily with $$\epsilon \le 1$$. The probability of the event $$\textstyle\exists T.~~ \sum_{t=1}^T x_t/(1+\epsilon) - \sum_{t=1}^T y_t/(1-\epsilon) \,\ge\, \epsilon \mu$$ is less than $$\exp(-\epsilon^2\mu)$$.

Note that $$\mu$$ can be chosen arbitrarily and the event is that the desired inequality fails for any $$T$$ (not just at a single stopping time).

Application to the scenario in the post

For the scenario in your post, applying the theorem twice and abusing notation slightly, the probability that $$\textstyle \forall T.~~ \sum_{t=1}^T Y_t \in \big[(1\pm O(\epsilon)) \sum_{t=1}^T X_t\big]~ \pm (1+O(\epsilon))\epsilon \mu$$ is at least $$1-2\exp(-\epsilon^2\mu)$$.

If, say $$S$$ is a stopping time with finite expectation you could, for example, choose $$\mu = p E[S] = E[\sum_{t=1}^S X_t]$$ and conclude that the desired relation holds at all times $$t$$, including $$S$$, with probability at least $$1-2\exp(-\epsilon^2 E[\sum_{t=1}^S X_S])$$, that is, $$1-2\exp(-\epsilon^2 p E[S])$$. In the desired relation, the "additive error" $$\epsilon\mu$$ is then $$\epsilon E[\sum_{t=1}^S X_t]$$.

Proof of bound

A proof of Theorem 1, and other theorems in a similar spirit, are currently available here, and hopefully will be available in some citable publication within a few years, but for completeness I will include a proof here. The proof is just a careful adaptation of the techniques underlying standard Chernoff bounds.

Proof. For $$t\in\{0,1,2,\ldots\}$$ define $$\phi_t = (1+\epsilon)^{\sum_{s=1}^t x_s} (1-\epsilon)^{\sum_{s=1}^t y_s}.$$ Then $$\phi_0 = 1$$, while, if the event in question happens, then for the $$T$$ in question, by calculation $$\phi_T$$ exceeds $$e^{-\epsilon^2\mu}$$. (Here is the calculation:

1. Let $$X = \sum_{t=1}^T x_t$$ and $$Y=\sum_{t=1}^T y_t$$.
2. Then $$\exp(X\epsilon/(1+\epsilon)-Y\epsilon/(1-\epsilon)) \ge \exp(\epsilon^2\mu)$$.
3. Using $$e^{z/(1+z)} < 1+z$$ for $$z\in\{-\epsilon,+\epsilon\}$$ we get
4. $$\phi_T = (1+\epsilon)^X(1-\epsilon)^Y > \exp(\mu\epsilon^2)$$.)

Next, note that $$1=\phi_0, \phi_1, \ldots$$ is a non-negative super-martingale. (Indeed, for $$t\ge 1$$, $$\frac{\phi_t}{\phi_{t-1}} =(1+\epsilon)^{x_t}(1-\epsilon)^{y_t} \le(1 +\epsilon x_t) (1-\epsilon y_t) \le 1+\epsilon x_t - \epsilon y_t,$$ and (using $$E[x_t - y_t | S_t] \le 0$$), the expectation of the right-hand side (conditioned on $$S_{t-1}$$) is at most 1.)

By Theorem 2, below, it follows that the probability of the event $$\exists T.~\phi_T \ge \exp(\epsilon^2\mu)$$ is less than $$\exp(-\epsilon^2\mu)$$. $$~~~\Box$$

A Markov-like bound for super-martingale maxima

The next theorem is a sort of Markov bound for super-martingale maxima.

Theorem 2. Let $$\phi_0, \phi_1, \ldots$$ be a non-negative super-martingale. Fix any $$c > 0$$.

(i) The probability of the event $$(\exists t)~ \phi_t \ge c$$ is at most $$E[\phi_0] / c$$.

(ii) The probability of the event $$(\exists t)~ \phi_t > c$$ is less than $$E[\phi_0] / c$$.

Proof sketch. We prove Part (i). Part (ii) can be shown similarly, with suitable additional limit argument.

Assume WLOG that $$\phi_0$$ is constant (independent of the outcome of the random experiment). (If not, apply the argument to the modified sequence $$E[\phi_0], \phi_0, \phi_1, \ldots$$.)

Define r.v. $$T_\infty$$ to be the first time $$t$$ such that $$\phi_t \ge c$$, if any, and otherwise $$T_\infty = \infty$$. Fix any $$n\ge 0$$ and define $$T_n = \min\{T_\infty, n\}$$.

Then $$T_n$$ is a stopping time with finite expectation, and $$\phi_t\in [0, c]$$ for $$t\in [0, T_n]$$. So Wald's equation implies $$E[\phi_{T_n}] \le \phi_0$$. So the Markov bound implies that $$\Pr[\phi_{T_n} \ge c]$$ is at most $$\phi_0/c$$. The event $$\phi_{T_n}\ge c$$ happens iff $$T_\infty \le n$$, so $$\Pr[T_\infty \le T_n]$$ is at most $$\phi_0/c$$. This holds for all $$n$$, so $$\Pr[T_\infty < \infty] = \lim_{n\rightarrow \infty} \Pr[T_\infty \le n] \le \phi_0/c.$$ Finally, the event $$T_\infty < \infty$$ happens iff $$(\exists t)~ \phi_t \ge c$$. $$~~~\Box$$