2
$\begingroup$

I have $n$ independent random variables $X_i$. Can I use Chernoff's bound to find a bound on $P(X>\epsilon)$ where $X=\sum_i X_i$?

Assume that I know $E[X_i]$ and $0<X_i<U_i, \forall i$, but I don't know the distribution of $X_i$.

Is there any constraint on $n$? (I don't have any control on $n$. it can be small $n<10$ or large $n>100$.)

[EDIT] [This]1 was my motivation for choosing Chernoff. In page 1, it discusses using Chernoff's bound for any distribution where $ 0\leq X_i\leq 1$. Later in page 3, it talks about when $X_i>1$. But how can I apply that for my case? and what will be its implication? Is the bound get looser as $U_i$s get larger?

$\endgroup$
3
  • $\begingroup$ Assuming $X_i$'s are iid, you can apply Chebychev's inequality to bound: $$\mathbb{P}\left[ |\frac{1}{n} X - \mathbb{E}[X]| \leq \epsilon \right] \geq \frac{\mathbb{V}[X]}{n\epsilon^2}$$ $\endgroup$
    – David Simmons
    Commented Sep 9, 2013 at 22:33
  • $\begingroup$ Just to clarify, both inequalities should infact be reversed for the above expression to be valid. $\endgroup$
    – David Simmons
    Commented Sep 9, 2013 at 22:43
  • $\begingroup$ Thanks Dave. But I don't know the variance and the variables are not identically distributed. Actually their mean can be different. $\endgroup$
    – Masood_mj
    Commented Sep 9, 2013 at 22:52

1 Answer 1

Reset to default
1
$\begingroup$

This is an example of Hoeffding’s inequality. For a tutorial like introduction, please take a look at Terry Tao's lecture on concentration inequalities, especially Exercise 4 (Hoeffding’s inequality).

There is no constraint on $n$; as usual, the concentration rate is exponential in terms of $n$.

$\endgroup$
4
  • $\begingroup$ Why the formulation of Hoeffding's inequality depends on n but the formulation of Chernoff's inequality is independent of it? is Hoeffding's tighter? $\endgroup$
    – Masood_mj
    Commented Sep 10, 2013 at 3:31
  • $\begingroup$ Also the Hoeffding's inequality bound does not depend on $\mu$ but Chernoff's does. For my case $\frac{U_i}{\mu_i}$ is about 1000 which is much larger than $n$. $\endgroup$
    – Masood_mj
    Commented Sep 10, 2013 at 3:37
  • $\begingroup$ My short answer is "I don't know". But an implication of your comments is that Hoeffding's inequality is very loose, which is well-known. I hope you are not using it in non-theoretical work. $\endgroup$
    – Taha
    Commented Sep 10, 2013 at 4:32
  • $\begingroup$ Thanks Taha. Actually I'm using that in practice. Before, people were using Markov inequality which is much looser! $\endgroup$
    – Masood_mj
    Commented Sep 10, 2013 at 5:08

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .