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?

5more comments