2
$\begingroup$

I tried to prove the following Chernoff-type bound when doing research, and found that it is of indepent interest.

Let $X_1, \dots, X_n$ be independent random varibles such that each $X_i$ is a Bernoulli random varible with parameter $p$, i.e., $\Pr[X = 1] = 1 - \Pr[X = 0] = p$. Moreover, we have weights $a_1, \dots, a_n \in [0, \tau]$, and write $S := \sum_{i = 1}^n a_iX_i$. I tried to show that
$$ \Pr[S > \mathbf{E}[S] + t] \leq \exp\left(-\frac{Ct^2}{np\tau^2}\right), \forall t > 0 $$ where $C$ is a constant.

One can surely apply Hoeffding bound here, which yields $$ \Pr[S > \mathbf{E}[S] + t] \leq \exp\left(-\frac{2t^2}{n\tau^2}\right), \forall t > 0. $$ The drawback is that Hoeffding bound only uses the range of the random variables, however, it does not exploit the property that $X_i$'s are Bernoulli variables, and hence a $p$ factor is missing.

I tried to adapt the proof of Chernoff bound, but unfortunately failed. I would apprecaite it if anyone have some idea on it.

$\endgroup$
3
  • $\begingroup$ How does your bound relate to the following standard multiplicative variant of the Chernoff bound? $$\Pr[S > (1+\epsilon) E[S]] \le \exp(-\epsilon^2 E[S]/3)$$ (assuming here by scaling that $\tau=1$) $\endgroup$
    – Neal Young
    Jan 16 at 1:29
  • $\begingroup$ When all $a_i$'s equal to $1$, this is exactly Chernoff bound. To see this, let $\epsilon = t / \mathbf{E}[S] = t / np$, the inequality can be rewrite as $\Pr[S > (1 + \epsilon)\mathbf{E}[S]] \leq \exp(-C(\epsilon np)^2 / (np)) = \exp(- C\epsilon^2 \mathbf{E}[S] )$. $\endgroup$
    – Xinyu Mao
    Jan 16 at 2:50
  • $\begingroup$ I'm not asking about the case when all $a_i$'s equal 1. I'm suggesting you consider the general case (which reduces by scaling to the case $\tau=1$). Note that the bound I cite makes no assumptions on the $X_i$'s other than that they are independent and in $[0,1]$. $\endgroup$
    – Neal Young
    Jan 16 at 3:42

1 Answer 1

2
$\begingroup$

Your bound (at least when $t\le E[S]$) seems to follow from the standard multiplicative Chernoff bound, as follows.

Lemma 1. (a standard multiplicative Chernoff bound) Let $S$ be the sum of independent random variables in $[0,1]$. Then $\forall \epsilon\in (0,1)$ we have $\Pr[S \ge (1+\epsilon)E[S]]$ is at most $\exp(-\epsilon^2 \mu/3)$.

To use this to prove your bound, let $S$, $a$, $n$, $\tau$, and $t$ be as in your question. Assume WLOG by scaling that $\tau=1$. Then, letting $\epsilon = t/E[S] \le 1$, $$\begin{aligned} \Pr[S \ge E[S] + t] & {} = \Pr[ S \ge (1+\epsilon) E[S]] \\ & {} \le \exp(-\epsilon^2 E[S]/3) && \text{(Lemma 1)}\\ & {} = \exp(-(t/E[S])^2 E[S]/3) \\ & {} = \exp(-t^2 / (3E[S])) \\ & {} \le \exp(-t^2/(3np)), && \text{(see below)} \end{aligned} $$ where the last line follows from $E[S] = \sum_{i=1}^n a_i p \le np$.

My guess is you can handle the case when $t>E[S]$ similarly but using the less simplified form of the upper bound in the standard multiplicative Chernoff bound (as one does to handle the case $\epsilon>1$ when using that bound).

$\endgroup$
3
  • $\begingroup$ Thank you! It's a very neat proof and works perfectly when $\tau = 1$. However, when $\tau < 1$, it seems that the above argument gives $\exp(-t^2 / (3np\tau))$, while the bound using Hoeffding inequality has $\tau^2$ in the denominator, which is particularly useful when $\tau$ is very small. So my anticipated bound also has $\tau^2$ in it. $\endgroup$
    – Xinyu Mao
    Jan 16 at 4:31
  • $\begingroup$ @XinyuMao “Assume WLOG by scaling that $τ=1$” means $\Pr[S\ge E[S]+t]=\Pr[\frac1\tau S\ge E[\frac1\tau S]+\frac t\tau]\le\exp(-(t/\tau)^2/3np)$ for arbitrary $\tau>0$. $\endgroup$ Jan 16 at 7:47
  • $\begingroup$ @EmilJeřábek Thanks! I think the question is then fully resolved. $\endgroup$
    – Xinyu Mao
    Jan 16 at 8:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.