20
$\begingroup$

It is well known that expectation preserves convexity: If $f(x)$ is convex and $Y$ is a random variable, then $\mathbb E[f(x-Y)]$ is convex. This property arises in, for example, inventory theory.

I have not been able to find a good source to cite for this well-known fact. Can anyone suggest one?

(For what it's worth, Boyd and Vandenberghe's book proves another well known property, namely, minimization preserves convexity, but I don't think they prove it for expectation.)

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ If $f(x)$ is convex, then $f''(x) \succeq 0$ is known. We can write the expectation in the closed form: $\mathbb{E} [f(x - Y)] = \sum_{i \in \mathcal{I}} p_i f(x - y_i)$ where $p_i$ is the probability of $y_i$ to be realized and $\mathcal{I}$ is the set of indices $Y$ can take (if continuous replace with an integration). We can use the property that sum of convex functions is convex as well. Therefore, we need to show $p_i f(x-y_i)$ is convex. The second derivative of this function is $f''(x - y_i) \succeq 0 $ since $f$ is a convex function. This concludes the statement if I'm not wrong. $\endgroup$
    – independentvariable
    May 30, 2019 at 22:16
  • 1
    $\begingroup$ @aslv95 Agree. My question is just where I can find that written in a book or article, so I can cite it when I use it. (All else fails, I guess I can cite you. :) ) $\endgroup$
    – LarrySnyder610
    May 30, 2019 at 22:20
  • 3
    $\begingroup$ I hope I am not wrong, but this seems like something we can really skip citing. Otherwise, we would need to cite 'linear function is a convex/concave' function all the time since this is easy to see but there is definitely someone who said this first :) But that's interesting because I face this all the time as well. Usually, you can see something is pretty straightforward but also doubt much like 'what if I need to cite this but I don't know if it is online or too low level to cite'... There should be some threshold of the complexity of proof to skip citing, but idk :) $\endgroup$
    – independentvariable
    May 30, 2019 at 22:27
  • 2
    $\begingroup$ You might be right. If someone knows of a reference, I'll gladly use it, but if not, your comment puts me at ease a bit. $\endgroup$
    – LarrySnyder610
    May 30, 2019 at 22:31

2 Answers 2

Reset to default
16
$\begingroup$

Reference "Convex Optimization" by Boyd and Vandenberghe https://web.stanford.edu/~boyd/cvxbook/, section 3.2.1, p. 79.

These properties extend to infinite sums and integrals. For example if $f(x, y)$ is convex in $x$ for each $y\in A$, and $w(y) \ge 0$ for each $y\in A$, then the function $g$ defined as $$g(x) = \int_A w(y)f(x, y)\, dy$$ is convex in $x$ (provided the integral exists).

Of course, this extends to Lebesgue-Stieltjes integrals (not mentioned in the referenced book), so should cover any expectation.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ That will work. I swear I looked through that whole book a few years ago looking for this. :/ Thanks. $\endgroup$
    – LarrySnyder610
    May 30, 2019 at 23:58
  • 2
    $\begingroup$ @LarrySnyder610 As a side note, you need to assume that $f(x - Y)$ is a continuous random variable for the above to be applicable. $\endgroup$
    – Pantelis Sopasakis
    May 31, 2019 at 0:32
  • 2
    $\begingroup$ @Pantelis Sopasaki I mentioned the extension to Lebesgue-Stieltjes integrals, even though that is not mentioned in the Boyd and Vandenberghe book. $\endgroup$
    – Mark L. Stone
    May 31, 2019 at 0:44
7
$\begingroup$

$\newcommand{\E}{\mathbb{E}}\newcommand{\R}{\mathbb{R}}$Define $\phi(x) = \E[f(x-Y)]$ and assume that for all $x\in\R$, $f(x-Y)$ is measurable and integrable. Then, for $x,x'\in\R$ and $\alpha \in [0,1]$

\begin{align} \phi(\alpha x + (1-\alpha)x') {}={}& \E[f(\alpha x + (1-\alpha)x'-Y)] \\ {}={}& \E\left[f\left(\alpha x + (1-\alpha)x'- \alpha Y - (1-\alpha) Y\right)\right] \\ {}={}& \E\left[f\left(\alpha (x-Y) + (1-\alpha)(x'- Y)\right)\right] \\ {}\leq{}& \E\left[\alpha f(x-Y) + (1-\alpha)f(x'- Y)\right] \\ {}={}& \alpha \E[f(x-Y)] + (1-\alpha)\E[f(x'- Y)] \\ {}={}& \alpha \phi(x) + (1-\alpha)\phi(x'), \end{align}

where we have used the linearity of the expectation, the fact that if $Z\leq Z'$ (a.s.) then $\E[Z] \leq \E[Z']$, and the convexity of $f$. We have, therefore, shown that $\phi$ is convex.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Beautiful. But: I'm just looking for a reference. :) Maybe this was a poor question. My intent is just: I use this result all the time. When I use it, I say "it's well known". But I'd like to be able to say "it's well known; see, e.g., [ref.]". I don't want to include a proof in what I'm writing, obviously, since it's "well known". $\endgroup$
    – LarrySnyder610
    May 30, 2019 at 23:18
  • 4
    $\begingroup$ @LarrySnyder610 I'll try find something. You could perhaps state that this can be easily verified (if it's for a paper), or give it as an exercise if it's for a course. $\endgroup$
    – Pantelis Sopasakis
    May 30, 2019 at 23:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.