# Entropy upper bound inequality for Sub-Gaussian Random Variable

We say that the random variable $Z$ is $\sigma^2$-subGaussian if $\mathbb{E} \exp(tZ) \leq \exp(t^2\sigma^2)/2$.

Define the $(x\log x)$-entropy (or simply the entropy) of a nonnegative random variable $Z$ by $\text{Ent}(Z):= \mathbb{E}(Z\log Z)- \mathbb{E}Z \log (\mathbb{E}Z)$. Here $\log$ is the natural logarithm.

I am interested to get the following bound: If $X-\mathbb{E}(X)$ is $\sigma^2$-subGaussian, then $\text{Ent}(\exp (t X))\leq t^2\alpha \;\mathbb{E}(\exp(tX))$ for any $t\geq 0$, and $\alpha$ is some constant depending on $\sigma$.

How do I get the above bound? I have tried using Jensen's inequality and various manipulations but could not get the above.

So if I understand right, if $X-\mathbb EX$ is $\sigma^2$-sub-Gaussian, then $$\forall t\in\mathbb R:\mathbb Ee^{t(X-\mathbb E X)}\le e^{t^2\sigma^2/2}\tag1$$ Taking the logarithm of both sides of (1), we have an expression in terms of the so-called cumulant-generating function of $X$: $$\forall t\in\mathbb R:\log\mathbb Ee^{tX}-\mathbb EtX\le \frac{t^2\sigma^2}2,\tag2$$ Multiplying both sides by $\mathbb E e^{tX}$ (which is always positive and depends only on $t$), we have: $$\forall t\in\mathbb R:\mathbb Ee^{tX}\log\mathbb Ee^{tX}-\mathbb Ee^{tX}\mathbb EtX\le \frac{t^2\sigma^2}2\mathbb E e^{tX}\tag3$$ But if $t\ge 0$, then by Jensen's inequality, $\mathbb Ee^{tX}\mathbb EtX\ge\mathbb E(e^{tX}tX)$, so $$\forall t\ge 0:\mathbb Ee^{tX}\log\mathbb Ee^{tX}-\mathbb E(e^{tX}tX)\le \frac{t^2\sigma^2}2\mathbb E e^{tX}\tag4$$ or in terms of your entropy we would have to take the negative of it to get the bound, $$\forall t\ge 0:-\operatorname{Ent}(e^{tX})\le \frac{t^2\sigma^2}2\mathbb E e^{tX}.\tag5$$

• But that is a useless inequality because it's easy to see that $\text{Ent}(Z)\geq 0$ for any non-negative random variable $Z$. – digiboy1 Apr 16 '15 at 14:11

For any real number $t$, denote $Z=e^{tX}/\mathbb E e^{tX}$. By direct computation we have $$Ent(e^{tX})=\mathbb E(e^{tX} (tX -\log \mathbb E e^{tX})=\mathbb E e^{tX} \mathbb E( Z\log Z ) .$$ Since log is a concave function and $\mathbb E Z =1$, we have $$\mathbb E (Z\log Z ) \leq \log \mathbb E( Z Z ) = \log \mathbb E e^{2tX} - 2\log \mathbb E e^{tX}=\log \mathbb E e^{2t(X-EX)} - 2\log \mathbb E e^{t(X-EX)}.$$

By convexity of exp, we have $\log \mathbb E e^{t(X-EX)}\geq 0$. In the view of the display above, we conclude $$Ent(e^{tX})=\mathbb E e^{tX} \mathbb E (Z\log Z )\leq \mathbb E e^{tX} \times 4\sigma^2 t^2/2,\forall t\in \mathbb R.$$

Let $M(t)= E[e^{tX}]$

Then $$Ent(e^{tX}) = E[e^{tX}tX] - E[e^{tX}]log(E[e^{tX}]) = tM'(t) - M(t)log(M(t)) = Mt^2\frac{d}{dt}\frac{log(M(t))}{t}$$

Given: $$E[e^{t(X-E[X])}] \leq \frac{e^{t^2 \sigma^2}}{2} \implies M(t) \leq e^{\frac{t^2 \sigma^2}{2}+tE[X]} \implies log(M(t)) \leq \frac{t^2 \sigma^2}{2} +tE[X]$$

Thus, for $t \neq 0$ , $$\frac{log(M(t))}{t} \leq \frac{t\sigma^2}{2} + E[X]$$

Consider $$\lim_{t \rightarrow 0} \frac{log(M(t))}{t} = \lim_{t \rightarrow 0} \frac{M'(t)}{M(t)}= E[X]$$

Let's assume: $Ent(\exp (t X))\leq t^2\alpha {E}[\exp(tX)]$ for any $t\geq 0$ $\implies Mt^2\frac{d}{dt}\frac{log(M(t))}{t} \leq t^2\alpha M$ $\implies$ $\frac{d}{dt}\frac{log(M(t))}{t} \leq \alpha$

Integrating both sides and using $\lim_{t \rightarrow 0} \frac{log(M(t))}{t}= E[X]$

we get:

$\frac{log(M(t))}{t} \leq E[X] + \alpha t$

Comparing this with earlier inequality we get: $\alpha \geq \frac{\sigma^2}{2}$

• The line after 'Given:' should read $\log M(t) \leq \frac{t^2 \sigma^2}{2} +t E[X]$. Also, I don't quite understand the part after the Taylor expansion. How do you conclude afterwards that the truncated Taylor series is less than $\frac{\log M(t)}{t}$ for all $t$ ? – digiboy1 Apr 12 '15 at 0:48
• Thanks, your comment made me address the error, the proof should look complete now. – rightskewed Apr 12 '15 at 2:51
• @digiboy1 Does that answer your problem? – rightskewed Apr 12 '15 at 21:18
• I'm still not sure with this part: You said in the beginning that we have $$\frac{\log M(t)}{t} \leq \frac{t\sigma^2}{2}+ tE[X].$$If I understand correctly, after doing the Taylor expansion, you truncate it to get that the first two terms in the expansion is less than $\frac{t\sigma^2}{2}+ tE[X]$. It seems that you are assuming the remainder part is always non-negative for all $t$. Why is this true? Or did I misunderstand some supposedly simple argument? – digiboy1 Apr 13 '15 at 2:23
• @digiboy1 I took a tangential approach and found bounds for α – rightskewed Apr 17 '15 at 7:30