3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What does the notation $U \in (1\pm \delta)V$ mean? Is it $(1-\delta)V \le U \le (1+\delta)V$? $\endgroup$ – Nate Eldredge Mar 4 at 18:09
  • $\begingroup$ @NateEldredge Correct. $\endgroup$ – Mathman Mar 4 at 18:49
3
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Mathman Mar 4 at 23:54
  • $\begingroup$ 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$. $\endgroup$ – Iosif Pinelis Mar 5 at 4:33
  • $\begingroup$ 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. $\endgroup$ – Mathman Mar 5 at 4:59
  • $\begingroup$ In the above comment, I have already answered your question with the deterministic lower bound on the sum. $\endgroup$ – Iosif Pinelis Mar 5 at 5:30
  • $\begingroup$ 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. $\endgroup$ – Mathman Mar 5 at 13:56
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks, this was also a very good answer, wish I could accept two answers. $\endgroup$ – Mathman Mar 5 at 13:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.