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

Question

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?

Answer 1

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