1
$\begingroup$

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?

$\endgroup$
10
  • 1
    $\begingroup$ Won't be dimension independent due to the log under the square root in your aimed result $\endgroup$ – kodlu Mar 8 '20 at 19:52
  • 1
    $\begingroup$ That's because of the success probability. I'll change it to avoid confusion. $\endgroup$ – Mathman Mar 8 '20 at 20:11
  • 2
    $\begingroup$ 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. $\endgroup$ – Mateusz Kwaśnicki Mar 8 '20 at 22:23
  • 1
    $\begingroup$ 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. $\endgroup$ – Iosif Pinelis Mar 9 '20 at 0:16
  • $\begingroup$ @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. $\endgroup$ – Mathman Mar 9 '20 at 0:58
2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Thank you so much far taking the time to write this. It turns out that @MateuszKwaśnicki was right. $\endgroup$ – Mathman Mar 9 '20 at 20:18

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.