Expectation of a minimum Assume that $c_{ij}(W)$ is a simple function of a random variable W. (This comes is Dynamic Programming where we are currently at node i and we want to go to node j in the shortest path problem and W is the random variable denoting the time that we wish to minimize)
What does the following expression mean?
$$\mathbb{E} \{\min_{j} \quad c_{ij}(W)\}$$
Intuitively, I understand that we are minimizing the expectation of the minimum possible of all possible functions of $W$ but is there more?
 A: You have a random variable $W$ and simple functions $c_{ij}$, for, say, $i=1,\dots,I$, and $j=1,\dots,J$. 
Each $c_{ij}(W)$ is also a random variable (easy to prove), and
$$
  Y_i = \min_{1\leq j\leq J} c_{ij}(W) = \min \, \{ c_{i1}(W), \dots, c_{iJ}(W) \}
$$
is a random variable for each $i=1,\dots,I$ (easy to prove).
Hence, the expectations $\mathbb{E}\left[Y_i\right]=\mathbb{E}\left[ \min_{1\leq j\leq J} c_{ij}(W) \right]$, for $i=1,\dots,I$, are well defined.
Think in terms of simulations. Draw independent values $w_1,\dots,w_N$ from the distribution of $W$. For each $k=1,\dots,N$ and each $i=1,\dots,I$, compute the numbers
$$
  c_{i1}(w_k), \dots, c_{iJ}(w_k)
$$
and determine their minimum value $y_i^{(k)}$. By the law of large numbers,
$$
  \frac{1}{N}\sum_{k=1}^N y_i^{(k)}
$$
will approach $E[Y_i]$ as $N$ grows.
A: The expression would return a column vector. The value at position $i$ in the vector is the index for the node $j^*$ which minimizes the W function with respect to that particular node $i$, by comparing the W values for all possible $j$. In other words, if we are sitting on node $i$ and want to know on average which node $j$ we will go to next, the optimum according to the W function is $j^*$.
