How can I calculate $\mathrm{E}\!\left[\sum _{i=1}^X I_{\{Y_i\leq Y_{n+1}\}}\right]$? Suppose that $Y_1,\dots,Y_{n+1}$ is a random sample from a continuous distribution function $F$. Let$X\sim\mathrm{Uniform}\{1,\dots,n\}$ be independent of the $Y_i$'s. How can I compute $\mathrm{E}\!\left[\sum _{i=1}^X I_{\{Y_i\leq Y_{n+1}\}}\right]$?
 A: Here is an alternative answer to @Lucas' using the law of iterated expectations:
$$ \begin{align} 
E\left[\sum_{i=1}^X1_{(Y_i \leq Y_{n+1})}\right] & = E\left[E\left[\sum_{i=1}^X1_{(Y_i \leq Y_{n+1})}|X\right]\right] 
\\
& = E\left[\sum_{i=1}^XE[1_{(Y_i \leq Y_{n+1})}|X]\right]
\\
& = E\left[\sum_{i=1}^XE[1_{(Y_i \leq Y_{n+1})}]\right] 
\\
& = E\left[\sum_{i=1}^XE\left[E[1_{(Y_i \leq Y_{n+1})}|Y_{n+1}]\right]\right]
\\
& = E\left[\sum_{i=1}^XE[F(Y_{n+1})]\right] 
\\[12pt]
& = E[X]E\left[F(Y_{n+1})\right]
\\[12pt]
& =\frac{n+1}{2}E[F(Y_{n+1})] 
\end {align}$$
The third step follows from independence of $Y_i$ and $Y_{n+1}$ from $X$; the fourth step is again an application of the law of iterated expectations; the last step is simply an application of the formula for the expectation of a discrete uniform random variable.
By inverting the order of integration, we derive the remaining expectation:
$$ \begin{align}
E[F(Y_{n+1})] & = \int_{-\infty}^{\infty}F(y)dF(y)
\\ 
& = \int_{-\infty}^{\infty} \int_{-\infty}^y dF(x)dF(y)
\\
& = \int_{-\infty}^{\infty} \int_{x}^{\infty} dF(y)dF(x) 
\\
& = \int_{-\infty}^{\infty} (1-F(x))dF(x)
\\[10pt]
& = 1-E[F(Y_{n+1})]
\end{align} $$
which implies $E[F(Y_{n+1})] = \frac{1}{2}$. Hence:
$$ E\left[\sum_{i=1}^X1_{(Y_i \leq Y_{n+1})}\right] = \frac{n+1}{4} $$
A: By distributional symmetry, $\Pr\{Y_i\leq Y_{n+1}\}=\Pr\{Y_{n+1}\leq Y_i\}$, for each $i=1,\dots,n$. Since $F$ is continuous, we have
$$
  \Pr\{Y_i\leq Y_{n+1}\} = 1-\Pr\{Y_{n+1}< Y_i\}=1-\Pr\{Y_{n+1}\leq Y_i\}.
$$
Therefore, $\mathrm{E}\left[I_{\{Y_i\leq Y_{n+1}\}}\right]=\Pr\{Y_i\leq Y_{n+1}\}=1/2$. Now, we have
$$
  \mathrm{E}\!\left[\sum_{i=1}^X I_{\{Y_i\leq Y_{n+1}\}}\;\Bigg\vert\; X=x\right] = \mathrm{E}\!\left[\sum_{i=1}^x I_{\{Y_i\leq Y_{n+1}\}}\;\Bigg\vert\; X=x\right]
= \sum_{i=1}^x\;\mathrm{E}\!\left[I_{\{Y_i\leq Y_{n+1}\}}\;\Bigg\vert\; X=x\right] 
$$
$$
  = \sum_{i=1}^x\;\mathrm{E}\!\left[I_{\{Y_i\leq Y_{n+1}\}}\right] = \frac{x}{2},
$$
in which we used the linearity of the conditional expectation and the independence of $X$ and the $Y_i$'s. Hence,
$$
  \mathrm{E}\!\left[\sum_{i=1}^X I_{\{Y_i\leq Y_{n+1}\}}\right] = \mathrm{E}\!\left[\mathrm{E}\!\left[\sum_{i=1}^X I_{\{Y_i\leq Y_{n+1}\}}\;\Bigg\vert\; X\right]\right] = \mathrm{E}\left[\frac{X}{2}\right] = \frac{n+1}{4}.
$$
A: We have 
\begin{align}
E\left[ \sum_{i = 1}^X I[Y_i \leq Y_{n + 1}] \right]
&= E\left[ \sum_{i = 1}^n I[i \leq X] I[Y_i \leq Y_{n + 1}] \right] \\
&= \sum_{i = 1}^n  E\left[ I[i \leq X] I[Y_i \leq Y_{n + 1}] \right] \\
&= \sum_{i = 1}^n  E\left[ I[i \leq X] \right] \cdot E\left[ I[Y_i \leq Y_{n + 1}] \right] \\
&= \sum_{i = 1}^n \frac{i}{n} \cdot E[I[Y_i \leq Y_{n + 1}]] \\
&= \sum_{i = 1}^n \frac{i}{n} \cdot E\left[ F(Y_{n + 1})] \right] \\
&= \sum_{i = 1}^n \frac{i}{n} \cdot \frac{1}{2} \\
&= \frac{n + 1}{4}
\end{align}
The second step follows from the linearity of expectations, the third step from the independence of $X$ and $Y_1, ..., Y_{n + 1}$, and the fifth step from the fact that 
$$F(y) = P(Y \leq y) = E[I[Y \leq y]].$$
To prove the sixth step, you can use partial integration. For the final step, you use the formula for partial sums.
