In slide 14 of these lecture notes, I found the following theorem:

Let $X$ be a random vector and let $u \in \underline{u}$ denote the constraint that $u$ is a function of $X$. Also assume that there exists $u^o(x)$ such that, $$\min_u f(x,u) = f(x,u^o(x)),\forall x$$ Then, $$\min_{u \in \underline{u}} E[f(X,u)] = E\left[\min_u f(X,u)\right]$$

To prove this theorem, the author shows that $$\min_{u \in \underline{u}} E[f(X,u)] \leq E\left[\min_u f(X,u)\right]$$ and $$\min_{u \in \underline{u}} E[f(X,u)] \geq E\left[\min_u f(X,u)\right]$$ However, I have a question about one of these proofs. According to these lecture notes, here is the proof that $$\min_{u \in \underline{u}} E[f(X,u)] \leq E\left[\min_u f(X,u)\right]$$ Let $u^o(x)$ minimize $f(x,u)$. Then, \begin{align} \min_u f(x,u) &= f(x,u^o(x)),\forall x \\ \min_u f(X,u) &= f(X,u^o(X)) \\ E\left[\min_u f(X,u)\right] &= E\left[f(X,u^o(X))\right] \tag{1} \label{q1eq1}\\ &\geq \min_{u \in \underline{u}} E[f(X,u)] \tag{2} \label{q1eq2} \end{align} where the author states that they went from \eqref{q1eq1} to \eqref{q1eq2} "because $u^o \in \underline{u}$".

Question: I am not sure what the author means by "because $u^o \in \underline{u}$" to go from \eqref{q1eq1} to \eqref{q1eq2}. Why didn't the author instead write (notice the constraint under the $\min$ changing compared to \eqref{q1eq2}) $$\begin{align}E\left[\min_u f(X,u)\right] &= E\left[f(X,u^o(X))\right] \\ &\geq \min_{u} E[f(X,u)] \end{align}$$

  • $\begingroup$ Have you tested whether Jenson's Inequality holds? $\endgroup$ Jan 26 at 2:03
  • $\begingroup$ @JamieAlizadeh could you elaborate on how it relates here? $\endgroup$
    – mhdadk
    Jan 26 at 2:48
  • 1
    $\begingroup$ Sorry, you actually don't need Jenson's Inequality. $E[f\left(X, u\right)]$ is just a function that maps elements of $\underline{u}$ to $\mathbb{R}$, so for an arbitrary $u^o \in \underline{u},$ you must have that $E\left[f(X,u^o)\right] \geq \min_{u} E[f(X,u)] $ $\endgroup$ Jan 26 at 4:35

1 Answer 1



It turns out that this theorem is a variation of Lemma 3.1 in section 3, chapter 8, of the book Introduction to Stochastic Control Theory by Karl J. Astrom (1970). Its proof can also be found in the same place in the book.

Using @JamieAlizadeh's idea in the comments that

$E[f(X,u)]$ is just a function that maps elements of $\underline{u}$ to $\mathbb R$, so for an arbitrary $u^o \in \underline{u}$, you must have that $$E\left[f(X,u^o)\right] \geq \min_{u} E[f(X,u)]$$

here is an expansion of the proof with some commentary. Suppose that $u^o(x)$ minimizes $f(x,u)$. This would mean that, for every $x$, $$\min_u f(x,u) = f(x,u^o(x))$$ Let $X$ be a random vector. Then, $$\min_u f(X,u) = f(X,u^o(X))$$ This is because every realization of $X$ will satisfy this equality. Next, we can compute the expectation of both sides of this equality with respect to $X$ to get $$E_X\left[\min_u f(X,u)\right] = E_X[f(X,u^o(X))]$$ Now let $$g(u) = E_X[f(X,u(X))]$$ Note that the $u$ appearing in $g(u)$ is a function of $X$, such that the function $g$ maps elements of $\underline{u}$, the set of functions $u$ that are a function of $X$, to a real number. We can see that the equality above becomes $$E_X\left[\min_u f(X,u)\right] = g\left(u^o\right)$$ Then, by definition, \begin{align} g\left(u^o\right) &\geq \min_{u \in \underline{u}} g(u) \\ &= \min_{u \in \underline{u}} E_X[f(X,u(X))] \end{align} which completes the proof that $$E_X\left[\min_u f(X,u)\right] \geq \min_{u \in \underline{u}} E_X[f(X,u(X))]$$ when $u^o(x)$ minimizes $f(x,u)$.

For convenience, here is some commentary on the second part of the proof of the theorem. Namely, the proof that $$ E_X\left[\min_u f(X,u)\right] \leq \min_{u \in \underline{u}} E_X[f(X,u(X))] $$ Let $v \in \underline{u}$, which means that $v$ is a function of the random vector $X$. Then, for every $x$, $$ \min_u f(x,u) \leq f(x,v(x)) $$ Because this inequality is true regardless of the value of $x$, then we can say that $$ \min_u f(X,u) \leq f(X,v(X)) $$ We then take expectations of both sides of this inequality with respect to $X$ (which is a monotone operation) to get $$ E_X\left[\min_u f(X,u)\right] \leq E_X\left[f(X,v(X))\right] $$ As before, let $g(u) = E_X[f(X,u(X))]$, such the inequality above becomes $$ E_X\left[\min_u f(X,u)\right] \leq g(v) $$ Additionally, note that the left-hand side of this inequality is a constant. Therefore, let $c = E_X\left[\min_u f(X,u)\right]$. The inequality above then reduces to $$ c \leq g(v) $$ This inequality states that the constant $c$ on the left-hand side is always less than or equal to $g(v)$, regardless of the function $v \in \underline{u}$. Therefore, if we choose $u$ to be from the set $\underline{u}$, and to minimize $g(u)$ from this set, then the inequality above does not change, which leads to $$ c \leq \min_{u \in \underline{u}} g(u) $$ Replacing $c$ and $g(u)$ with their respective definitions leads to $$ E_X\left[\min_u f(X,u)\right] \leq \min_{u \in \underline{u}} E_X[f(X,u(X))] $$ which completes the proof of the theorem.

Intuitively, what this theorem is stating is that, given that $$\min_u f(x,u)$$ exists, then the minimization of $E_X[f(X,u)]$ with respect to all functions $u$ that are restricted to be a function of the random vector $X$ is equivalent to the minimization of $f(X,u)$ with respect to all functions $u$ averaged over all possible $X$.

For a more general theorem, see:

  1. https://mathoverflow.net/a/108007/311484
  2. https://mathoverflow.net/a/316540/311484
  3. https://mathoverflow.net/a/245303/311484

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .