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](https://en.wikipedia.org/wiki/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](https://mathoverflow.net/questions/354271/sum-of-sequences-of-random-variables-with-variable-success-probabilities)) which unfortunately depends on the sequence's length. Any ideas about how to get the dimension-free variant?



Chernoff-type bound for sum of Bernoulli random variables, with outcome-dependent success probabilities
$\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](https://projecteuclid.org/euclid.aop/1176988477), 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. 


