2
$\begingroup$

I've been looking at Gabor Lugosi's wonderful notes on concentration of measure inequalities. On page 7 of the notes the exercise asks you to show that

$$ min_q\mathbb{E}(X^q)t^{-q} \leq inf_{s\geq 0}\mathbb{E}(e^{s(X-t)})$$.

In other words the best moment bound (left hand side) always is at least as good as the best Chernoff bound (right hand side).

This sounds like a wonderful result but I'm wondering how practically useful is the bound? To better understand this I'm asking for the quantified gap for any distribution you like (pick your favorite). Let's define the gap as the difference of the right hand side subtract the left hand side of the inequality. In other words:

$$Gap(t| X) = inf_{s\geq 0}\mathbb{E}(e^{s(X-t)})- min_q\mathbb{E}(X^q)t^{-q}.$$

Any distribution is fair game, but preference to common ones over obscure ones (i.e. exponential family ones, over others). Suggestions would be Gamma, Normal, Poisson, Negative Binomial, Binomial. I'd also be interested in a couple heavy tail ones too: Weibull, Frechet, Pareto, Yule-Simon.

$\endgroup$

1 Answer 1

0
$\begingroup$

I'll post an answer to the question to get things started-but I will not mark mine as correct.

Take the one of the simplest possible random variables

$X\sim \texttt{Bernoulli}(p).$

Then the Moment part of the question is:

$$\mathbb{E}(X^q)t^{-q} =pt^{-q}, q\in \mathbb{Z}_+$$

Now call the function $f(q,t)$. If $t>1$ then the $q$ that gives a minimal moment bound is $q=\infty$ which gives a bound of $0$. If $0\leq t \leq 1$ then the optimal $q=0$ which gives $p$ for the moment bound. This gives

$$p\mathbb{1}(0 < t<1)=min_{q\in\mathbb{Z_+}}\mathbb{E}(X^q)t^{-q}.$$

Now the Chernoff bound for a Bernoulli is

$$e^{-tlog(t/p) +plog(t/p)-p},$$

which is derived in many places online or you can do the optimization in $s$ yourself. The gap is then:

$g(t,p) =e^{-tlog(t/p) +plog(t/p)-p} - p\mathbb{1}(0 < t<1).$ However, by choosing any value of $p\in (0,1)$ I get that this function $g$, the gap function is not always greater than zero. Did I make an error somewhere?

$\endgroup$

Your Answer

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

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