# Chernoff-type bound for sum of Bernoulli random variables, with outcome-dependent success probabilities

Let $$X = (X_1, X_2, \ldots, X_n)$$ be a sequence of (not necessarily independent) Bernoulli random variables where for each $$i$$, the success probability $$\Pr[X_i = 1]$$ itself is a random variable depending on the sequence $$(X_1, \ldots, X_{i-1})$$. For any assignment $$X'=(X'_1, \ldots, X'_n)$$ define $$\mu^\star(X') = \sum_{i=1}^n \Pr[X_i = 1 \mid X_1=X'_1, \ldots, X_{i-1}=X'_{i-1}].$$

Is it possible to show that with probability $$1-\epsilon$$, $$\sum_{i=1}^n X_i = \mu^\star(X) \pm \Theta\left(\sqrt{\mu^\star(X) \log \epsilon^{-1}}\right)?$$

Note that if the success probabilities were fixed a priori, this would be implied by Chernoff bound. On the other hand, using Azuma's inequality on an appropriate martingale, a bound of $$\sum_{i=1}^n X_i = \mu^\star(X) \pm \Theta\left(\sqrt{n \log \epsilon^{-1}}\right)$$ could be proved (see this relevant question) which unfortunately depends on the sequence's length. Any ideas about how to get the dimension-free variant?

• Won't be dimension independent due to the log under the square root in your aimed result Mar 8, 2020 at 19:52
• That's because of the success probability. I'll change it to avoid confusion. Mar 8, 2020 at 20:11
• Perhaps answers and comments to this question contain useful references? For example, version 4 of Bernstein's inequality on Wikipedia might give the desired bound, but unfortunately I have no time to check this now. Mar 8, 2020 at 22:23
• I think the bound as stated will likely fail to hold in general, even though I don't have a counterexample at this point. However, if under the square root $\mu^*(X)$ is replaced by a real number $m>\mu^*(X)$ such that $\ln\epsilon^{-1}=O(m)$, then the resulting bound can be proved, I think. Mar 9, 2020 at 0:16
• @MateuszKwaśnicki Thanks for the references. I did look at the question you linked before posting this question. I don't think the methods mentioned in the answers there or the martingale variant of Bernstein's inequality can be used to prove this since in our case we don't really have a useful bound on the variance of the entries as the probabilities are revealed along the way and worst-case estimates seem far off. Mar 9, 2020 at 0:58

$$\newcommand\ep{\delta}\newcommand\de{\epsilon}$$For $$j=0,\dots,n$$, let $$S_j:=\sum_1^j d_i$$, where $$d_i:=X_i-E_{i-1}X_i$$ and $$E_{i-1}$$ is the conditional expectation given $$X_1,\dots,X_{i-1}$$, with $$E_0:=E$$ and $$S_0:=0$$. Clearly, $$(S_j)$$ is a martingale.
By Theorem 8.7, if $$|d_i|\le a$$ and $$\sum_1^n E_{i-1}d_i^2\le b^2$$ for some real $$a,b>0$$ and all $$i$$, then $$\begin{equation} P(|S_n|\ge r)\le2\exp\Big\{-\frac{b^2}{a^2}\,\psi\Big(\frac{ra}{b^2}\Big)\Big\} \tag{1} \end{equation}$$ for $$r\ge0$$, where $$\psi(u):=(1+u)\ln(1+u)-u$$.
In our case, recalling that the $$X_i$$'s take values in the set $$\{0,1\}$$, we have $$|d_i|\le1$$, so that we can take $$a=1$$, and also $$E_{i-1}d_i^2=E_{i-1}(X_i-E_{i-1}X_i)^2\le E_{i-1}X_i^2=E_{i-1}X_i,$$ whence $$\sum_1^n E_{i-1}d_i^2\le\sum_1^n E_{i-1}X_i=\mu^*(X).$$
We now assume that for some real $$m>0$$ and $$\ep\in(0,1)$$ we have $$\mu^*(X)\le m\quad\text{and}\quad\ln\frac1\ep\ll m;\tag{2}$$ as usual, we write $$u\ll v$$ or $$v\gg u$$ to mean $$|u|=O(v)$$, where the constant in $$O(\cdot)$$ is universal. Then we may take $$b^2=m$$. Also, in (1), take $$r=\sqrt{m\ln\frac1\ep}$$. Then $$\frac{ra}{b^2}=\frac rm=\sqrt{\frac1m\,\ln\frac1\ep}\ll1$$ by (2), and hence $$\frac{b^2}{a^2}\,\psi\big(\frac{ra}{b^2}\big)\gg\frac{b^2}{a^2}\,\big(\frac{ra}{b^2}\big)^2=\frac{r^2}{b^2}=\ln\frac1\ep$$. Now (1) yields $$P\Big(\Big|\sum_1^n X_i-m^*(X)\Big|\ge\sqrt{m\ln\frac1\ep}\Big) =P(|S_n|\ge r)\le2\ep^c$$ for some universal real constant $$c>0$$. Finally, letting $$\de:=2\ep^c$$, we get the result that, as you said in your comment, suits the application you had in mind.