<p>For insight, consider a distribution concentrated on two values; say, with equal probabilities of 1/2 that it equal 1 or 3, whence  $\textbf{E}[x] = 2$.  Take $N >> 0$ and $\epsilon > 0$.  Consider functions $f$ for which $f(1) = f(3)= N\epsilon$ and $f(\textbf{E}[x]) = f(2) = \epsilon$.  By making $\epsilon$ sufficiently small and connecting $f$ continuously among these three points we can make the curvature of $f$ as small as desired.  Then</p>

<p>$\textbf{E}[f(x)] = N\epsilon$, yet</p>

<p>$N = N\epsilon / \epsilon = \textbf{E}[f(x)] / f(\textbf{E}[x]) \le \varphi(f)$.</p>

<p>This shows $\varphi(f)$ must be arbitrarily large.</p>

CC BY-SA 2.5
2010-08-27T20:40:53.587Z
2010-08-27T20:40:53.587Z
whuber
<p>EDIT: original version missed an absolute value.  sorry!!</p>

<p>Hi Ian.  I will briefly outline two sample inequalities, one using a Lipschitz bound, the other using a bound on the second derivative, and then discuss some difficulties in this problem.  Although I'm being redundant, since an approach using one derivative explains what happens with more derivatives (via Taylor), it turns out that the second derivative version is quite nice.</p>

<p>First, with a Lipschitz bound: simply re-work the standard Jensen inequality.  The same trick applies: compute the Taylor expansion at the expected value.</p>

<p>Specifically, Let $X$ have corresponding measure $\mu$, and set $m := \textrm E(x)$.
If $f$ has Lipschitz constant $L$, then by Taylor's theorem</p>

<p>$$
f(x) = f(m) + f'(z)(x-m) \leq f(m) + L|x-m|,
$$</p>

<p>where $z \in [m, x]$ (note that $x\leq m$ and $x&gt; m$ are possible). Using this and re-working the Jensen proof (I am paranoid and checked that the standard one is indeed on wikipedia),</p>

<p>\begin{align}
\operatorname{E}(f(X)) &amp; = 
\int f(x) \, d\mu(x) 
\leq f(m) \int d\mu(x) + L\int |x-m| \, d\mu(x) \\[6pt]
&amp; = f(\operatorname{E}(X)) + L \operatorname{E} (|X-\operatorname{E}(X)|).
\end{align}</p>

<p>Now, suppose $|f''(x)| \leq \lambda$.  In this case,</p>

<p>\begin{align}
f(x) &amp; = f(m) + f'(m)(x-m) + f''(z) \frac{(x-m)^2} 2 \\[6pt]
&amp; \leq f(m) + f'(m)(x-m) + \lambda \frac{(x-m)^2} 2,
\end{align}</p>

<p>and so</p>

<p>\begin{align}
\operatorname{E}(f(X))
&amp; \leq f(m) + f'(m)(\operatorname{E}(X) - m) + \frac {\lambda \operatorname{E}((X-m)^2)}{2} \\[6pt]
&amp; = f(\operatorname{E}(X)) + \frac {\lambda \operatorname{Var}(X)}2.
\end{align}</p>

<p>I'd like to briefly mention a few things.  Sorry if they are obvious.</p>

<p>One is that, you can't merely say "wlog $\operatorname{E}(X) = 0$" by shifting the distribution, because you are changing the relationship between $f$ and $\mu$.</p>

<p>Next is that the bound <em>must</em> depend on the distribution in some way.  To see this, imagine that $X \sim \textrm{Gaussian}(0, \sigma^2)$ and $f(x) = x^2$.  Whatever the value of $\sigma$, you still get $f(\operatorname{E}(X)) = f(0) = 0$.  On the other hand, $\operatorname{E}(f(X)) = \operatorname{E}(X^2) = \sigma^2$.  Thus, by changing $\sigma$, you can make the gap between the two quantities arbitrary!  Intuitively, more mass is pushed away from the mean, and thus, for any strictly convex function, $\operatorname{E} (f(X))$ will increase.</p>

<p>Lastly, I don't see how to get a multiplicative bound like you suggest.  Everything I have used in this post is standard: Taylor's theorem and derivative bounds are bread&amp;butter in statistics bounds, and they automatically give additive, not multiplicative errors.</p>

<p>I will think about it though, and post something.  Vague intuition is it will need very strenous conditions on both the function and the distribution, and that the additive bound is actually at the heart of it.</p>

CC BY-SA 2.5
2010-08-27T21:58:33.310Z
Every time i edit, the answer gets bumped.  So I'll point out: the second derivative bound is tight for the example I gave.
matus
CC BY-SA 2.5
2010-08-28T18:08:22.757Z
I think you're right in that additive bounds are the best possible without much stronger conditions on the function.
Ian
CC BY-SA 2.5
2010-08-28T19:44:47.243Z
Dear Ian, I thought about this problem quite a bit more, but the main difficulty in my mind is hinted at by the example I gave, where $f(\textrm E(X))= 0$, but $\textrm E (f(X)) > 0$. You can constrain both the function family (bounded, bounded derivatives, integrable) and the distribution (smooth, bounded, bounded momemts), and you still have these examples. It suffices to have a symmetric, nonnegative function equal to zero at the mean of the distribution. That said, everything depends on the constraints in your exact problem. In the general case, I think the additive nature is fundamental.
matus
CC BY-SA 2.5
2010-10-04T03:29:53.027Z
@Ian: The proofs of the Chernoff and Azuma-Hoeffding inequalities use arguments reminiscent of this, so you may wish to read those for inspiration. See e.g. Mitzenmacher and Upfal's book on randomization in computing.
Warren Schudy
CC BY-SA 3.0
2010-08-27T20:43:31.857Z
2016-06-29T01:10:04.493Z
2016-06-29T01:10:04.493Z
matus
<p>If $f$ is a convex function then Jensen's inequality states that $f(\textbf{E}[x]) \le \textbf{E}[f(x)]$, and <em>mutatis mutandis</em> when $f$ is concave.  Clearly in the worst case you cannot upper bound $\textbf{E}[f(x)]$ in terms of $f(\textbf{E}[x])$ for a convex $f$, but is there a bound that goes in this direction if $f$ is convex but "not too convex"?  Is there some standard bound that  gives conditions on a convex function $f$ (and possibly the distribution as well, if necessary) that would allow you to conclude that $\textbf{E}[f(x)] \le \varphi(f)f(\textbf{E}[x])$, where $\varphi(f)$ is some function of the curvature/degree of convexity of $f$?  Something akin to a Lipschitz condition, perhaps?</p>

CC BY-SA 2.5
2010-08-27T19:00:22.003Z
Voting to close as off-topic. http://math.stackexchange.com maybe?
Aryabhata
CC BY-SA 2.5
2010-08-27T19:12:56.780Z
I think that this question should stay open; this is the sort of inequality that many working theorists would find useful on a regular basis.
Aaron Roth
CC BY-SA 2.5
2010-08-27T19:13:13.520Z
I know that this is closer to pure math than most of the questions posted so far, but I would argue that this is on-topic since this kind of thing comes up frequently in the analysis of randomized algorithms (which is the application I have in mind).  I think that math that is heavily used in computer science should be considered fair game for questions.
Ian
CC BY-SA 2.5
2010-08-27T19:32:10.160Z
vote to keep open. definitely on topic
Suresh Venkat
CC BY-SA 2.5
2010-08-29T11:05:53.053Z
I also vote to keep open.
Jeffε
<randomness><pr.probability><randomized-algorithms>
Bounds on $E[f(x)]$ in terms of $f(E[x])$ other than Jensen's inequality?
Ian
# Bounds on $E[f(x)]$ in terms of $f(E[x])$ other than Jensen's inequality?

(Asked by: username_0 on 2010-08-27)

If $f$ is a convex function then Jensen's inequality states that $f(\textbf{E}[x]) \le \textbf{E}[f(x)]$, and *mutatis mutandis* when $f$ is concave. Clearly in the worst case you cannot upper bound $\textbf{E}[f(x)]$ in terms of $f(\textbf{E}[x])$ for a convex $f$, but is there a bound that goes in this direction if $f$ is convex but "not too convex"? Is there some standard bound that gives conditions on a convex function $f$ (and possibly the distribution as well, if necessary) that would allow you to conclude that $\textbf{E}[f(x)] \le \varphi(f)f(\textbf{E}[x])$, where $\varphi(f)$ is some function of the curvature/degree of convexity of $f$? Something akin to a Lipschitz condition, perhaps?

**Tags:** randomness, pr.probability, randomized-algorithms

> **Comments:**
> **username_1**: Voting to close as off-topic. http://math.stackexchange.com maybe?  
> **username_2**: I think that this question should stay open; this is the sort of inequality that many working theorists would find useful on a regular basis.  
> **username_0**: I know that this is closer to pure math than most of the questions posted so far, but I would argue that this is on-topic since this kind of thing comes up frequently in the analysis of randomized algorithms (which is the application I have in mind).  I think that math that is heavily used in computer science should be considered fair game for questions.  
> **username_3**: vote to keep open. definitely on topic  
> **username_4**: I also vote to keep open.  

---

## 2 answers

### Answer by username_6 on 2010-08-27. Score: 21 | Accepted answer

EDIT: original version missed an absolute value. sorry!!

Hi username_0. I will briefly outline two sample inequalities, one using a Lipschitz bound, the other using a bound on the second derivative, and then discuss some difficulties in this problem. Although I'm being redundant, since an approach using one derivative explains what happens with more derivatives (via Taylor), it turns out that the second derivative version is quite nice.

First, with a Lipschitz bound: simply re-work the standard Jensen inequality. The same trick applies: compute the Taylor expansion at the expected value.

Specifically, Let $X$ have corresponding measure $\mu$, and set $m := \textrm E(x)$.
If $f$ has Lipschitz constant $L$, then by Taylor's theorem

$$
f(x) = f(m) + f'(z)(x-m) \leq f(m) + L|x-m|,
$$

where $z \in [m, x]$ (note that $x\leq m$ and $x> m$ are possible). Using this and re-working the Jensen proof (I am paranoid and checked that the standard one is indeed on wikipedia),

\begin{align}
\operatorname{E}(f(X)) & =
\int f(x) \, d\mu(x)
\leq f(m) \int d\mu(x) + L\int |x-m| \, d\mu(x) \\[6pt]
& = f(\operatorname{E}(X)) + L \operatorname{E} (|X-\operatorname{E}(X)|).
\end{align}

Now, suppose $|f''(x)| \leq \lambda$. In this case,

\begin{align}
f(x) & = f(m) + f'(m)(x-m) + f''(z) \frac{(x-m)^2} 2 \\[6pt]
& \leq f(m) + f'(m)(x-m) + \lambda \frac{(x-m)^2} 2,
\end{align}

and so

\begin{align}
\operatorname{E}(f(X))
& \leq f(m) + f'(m)(\operatorname{E}(X) - m) + \frac {\lambda \operatorname{E}((X-m)^2)}{2} \\[6pt]
& = f(\operatorname{E}(X)) + \frac {\lambda \operatorname{Var}(X)}2.
\end{align}

I'd like to briefly mention a few things. Sorry if they are obvious.

One is that, you can't merely say "wlog $\operatorname{E}(X) = 0$" by shifting the distribution, because you are changing the relationship between $f$ and $\mu$.

Next is that the bound *must* depend on the distribution in some way. To see this, imagine that $X \sim \textrm{Gaussian}(0, \sigma^2)$ and $f(x) = x^2$. Whatever the value of $\sigma$, you still get $f(\operatorname{E}(X)) = f(0) = 0$. On the other hand, $\operatorname{E}(f(X)) = \operatorname{E}(X^2) = \sigma^2$. Thus, by changing $\sigma$, you can make the gap between the two quantities arbitrary! Intuitively, more mass is pushed away from the mean, and thus, for any strictly convex function, $\operatorname{E} (f(X))$ will increase.

Lastly, I don't see how to get a multiplicative bound like you suggest. Everything I have used in this post is standard: Taylor's theorem and derivative bounds are bread&butter in statistics bounds, and they automatically give additive, not multiplicative errors.

I will think about it though, and post something. Vague intuition is it will need very strenous conditions on both the function and the distribution, and that the additive bound is actually at the heart of it.

> **Comments:**
> **username_6**: Every time i edit, the answer gets bumped.  So I'll point out: the second derivative bound is tight for the example I gave.  
> **username_0**: I think you're right in that additive bounds are the best possible without much stronger conditions on the function.  
> **username_6**: Dear username_0, I thought about this problem quite a bit more, but the main difficulty in my mind is hinted at by the example I gave, where $f(\textrm E(X))= 0$, but $\textrm E (f(X)) > 0$. You can constrain both the function family (bounded, bounded derivatives, integrable) and the distribution (smooth, bounded, bounded momemts), and you still have these examples. It suffices to have a symmetric, nonnegative function equal to zero at the mean of the distribution. That said, everything depends on the constraints in your exact problem. In the general case, I think the additive nature is fundamental.  
> **username_7**: @username_0: The proofs of the Chernoff and Azuma-Hoeffding inequalities use arguments reminiscent of this, so you may wish to read those for inspiration. See e.g. Mitzenmacher and Upfal's book on randomization in computing.  

---

### Answer by username_5 on 2010-08-27. Score: 3

For insight, consider a distribution concentrated on two values; say, with equal probabilities of 1/2 that it equal 1 or 3, whence $\textbf{E}[x] = 2$. Take $N >> 0$ and $\epsilon > 0$. Consider functions $f$ for which $f(1) = f(3)= N\epsilon$ and $f(\textbf{E}[x]) = f(2) = \epsilon$. By making $\epsilon$ sufficiently small and connecting $f$ continuously among these three points we can make the curvature of $f$ as small as desired. Then

$\textbf{E}[f(x)] = N\epsilon$, yet

$N = N\epsilon / \epsilon = \textbf{E}[f(x)] / f(\textbf{E}[x]) \le \varphi(f)$.

This shows $\varphi(f)$ must be arbitrarily large.


---

