Let $x=(z\_1,\ldots,z\_n)$ be real vector and $(p\_1,\ldots,p\_n)$ be a probability vector.


Question
========


$\log(\sum\_{i=1}^n p\_ie^{z\_i})-\sum\_{i=1}^np\_iz\_i \le ???$


Observation
===========


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)$.



Good UPPER bounds for $\log(\sum_{i=1}^n p_ie^{z_i})-\sum_{i=1}^np_iz_i$ where $(p_i)_i$ is a probability vector
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} $$


i.e.


$$ \log\left(e^{-\lambda \mu} \sum\_i p\_i e^{\lambda z\_i}\right) \leq \frac{\lambda^2 \sigma^2}{2} $$


i.e.


$$ \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.


