# 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

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

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

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.
• I should'have thought of that. Thanks! Unfortunately the question got downvoted without any comment on why.... – dohmatob Feb 15 at 17:02
• @dohmatob, agree, that is too bad (would have liked to see other approaches). – usul Feb 16 at 12:13