Let $x=(z_1,\ldots,z_n)$ be real vector and $(p_1,\ldots,p_n)$ be a probability vector.


$\log(\sum_{i=1}^n p_ie^{z_i})-\sum_{i=1}^np_iz_i \le ???$


This paper allows us to upper-bound things like $\Delta_f(z,p):=f(\sum_{i}z_i p_i) - \sum_i f(p_iz_i)$, thus providing a kind of reversed Jensen's inequality.

Indeed, it was shown that

If $f$ is concave, $a:=\min_i z_i$ and $b := \max_i z_i$, then $$ \Delta_f(z,p) \le \max_{p,q \ge 0,\;p+q=1} pf(b)+qf(a) - f(pb+qa). $$

I could probably use this with $f=\log$ to bound $\Delta_{\log} (z,p)$.

  • 1
    $\begingroup$ What is $z_i{}$? $\endgroup$ – Bullet51 Feb 15 at 13:54
  • $\begingroup$ Sorry that was a typo. Fixed. $\endgroup$ – dohmatob Feb 15 at 13:58
  • $\begingroup$ Any obvious why reason this question got downvoted ? A comment from the downvoter would be particularly appreciated. Thanks! $\endgroup$ – dohmatob Feb 15 at 17:12
  • $\begingroup$ It may look too simple as a research-level problem. $\endgroup$ – Bullet51 Feb 15 at 19:01
  • $\begingroup$ Ya, indeed. I thought I'd posted it on stackexchange. When I noticed it was on MO, it was already too late. But still... $\endgroup$ – dohmatob Feb 15 at 19:09

One answer - subgaussian variables generalize this property.

Let $\mu = \sum_i p_i z_i$, then the distribution is considered $\sigma^2$-subgaussian if for all $\lambda \in \mathbb{R}$,

$$ \log\left(\sum_i p_i e^{\lambda(z_i - \mu)}\right) \leq \frac{\lambda^2 \sigma^2}{2} $$


$$ \log\left(e^{-\lambda \mu} \sum_i p_i e^{\lambda z_i}\right) \leq \frac{\lambda^2 \sigma^2}{2} $$


$$ \log\left(\sum_i p_i e^{\lambda z_i}\right) - \lambda \mu \leq \frac{\lambda^2 \sigma^2}{2} . $$

Your expression is the case $\lambda=1$.

In a sense this is not an answer, just a definition for when and how your inequality can be satisfied, but hopefully useful because we know ways to show variables are subgaussian:

  1. Any random variable bounded in $[a,b]$ is $\left(\frac{b-a}{2}\right)^2$-subgaussian.
  2. If $X$ is $\sigma^2$-subgaussian, then $cX$ is $c^2\sigma^2$-subgaussian.
  3. If $X$ and $Y$ are independent and $\sigma_1^2,\sigma_2^2$ subgaussian, then $X+Y$ is $\sigma_1^2 + \sigma_2^2$ subgaussian.
  • $\begingroup$ I should'have thought of that. Thanks! Unfortunately the question got downvoted without any comment on why.... $\endgroup$ – dohmatob Feb 15 at 17:02
  • $\begingroup$ @dohmatob, agree, that is too bad (would have liked to see other approaches). $\endgroup$ – usul Feb 16 at 12:13

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.