The Chernoff bound for continuous random variables.

644 Views Asked by At

In a paper I am reading, authors apply the Chernoff bound to a continuous random variable $X$ with positive mean: $$\mathbb{P}(X\le 0)\le \mathbb{E}[\exp(\lambda X)]$$ I do not understand it. When I google for the Chernoff bound I get results for a sum of random variables that have values 0 or 1. Could you please provide a reference where I can read about continuous case, or could you explain how to get above inequality. Any thoughts are welcome.

2

There are 2 best solutions below

0
On BEST ANSWER

How to get it: Integrate the pointwise inequality $$\mathbf 1_{X\leqslant0}\leqslant\exp(\lambda X).$$ Note that, for this inequality to be true, one must assume that $\lambda\leqslant0$.

As explained here.

1
On

$\Pr\left[X\geq0\right]=\Pr\left[e^{\lambda x}\geq1\right]\leq\frac{E\left[e^{\lambda x}\right]}{1}=E\left[e^{\lambda x}\right] $ Where the inequality follows from markov's inequality on the positive random variable $e^{\lambda x} $