Urn model with numbered balls, expected value Consider the following urn model. There are n balls in an urn. Each has a unique number from 1 to n. You take out k balls. For $j<k~ X_j$ is the number of the ball you draw on your jth attempt. I managed to calculate that $E[X_j]=\frac{n+1}{2}$. Now I'm trying to calculate $ E[X_1*X_2]$ but I'm not really sure how to do it. So far I tried using the law of total probability to calculate $ P(X_1*X_2=k)$ without any success. Can anyone help?
 A: Let's iterate $x_1 \cdot x_2$ and find the expected value the traditional way: By summing up probability times value.
Say, we fixed two numbers $a, b$ as $x_1, x_2$. What is the probability that $x_1 = a, x_2 = b$? This equals $$\frac{1}{(n)(n - 1)}$$
So, we need to find $$\frac{1}{(n)(n - 1)} (1(2 + 3 + \cdots + n) + 
\cdots + n (1 + 2 + \cdots + (n - 1)))$$
This equals $$\frac{1}{n(n - 1)}(\sum ij - \sum i^2)$$
$$=\frac{1}{n(n - 1)}\bigg(\frac{n^2(n + 1)^2}{4} - \frac{n(n + 1)(2n + 1)}{6}\bigg)$$
$$=\frac{1}{n - 1}\bigg(\frac{n (n+1)^2}{4} - \frac{(n + 1)(2n + 1)}{6}\bigg)$$
$$=\boxed{\frac{(n + 1)(3n + 2)}{12}}$$
A: We have $$E[X_1] = \frac1n \sum_{k=1}^n  k =\frac1n \frac{n(n+1)}{2}= \frac{n+1}{2}$$
$$E[X_1^2] = \frac1n \sum_{k=1}^n  k^2 =\frac1n \frac{n(n+1)(2n+1)}{6}=\frac{(n+1)(2n+1)}{6}$$
(ref).
Also $$E[X_2 | X_1] = \frac{1}{n-1} \left( \sum_{k=1}^n  k -X_1 \right )=\frac{1}{n-1}\left( \frac{n(n+1)}{2} -X_1\right)$$
Putting all together
$$
\begin{align}
E[X_1 X_2 ] &= E[E[ X_1 X_2 | X_1]] \\
&= E[X_1 E[X_2 | X_1]]\\
&= E[ X_1 ] \frac{n(n+1)}{2(n-1)} - \frac{E[X_1^2]}{n-1}\\
&= \frac{(n+1)(3n +2)}{12}
\end{align}
$$
Some quick sanity checks : for $n=2$ , $E[X_1 X_2 ] =2$. For large $n$, $E[X_1 X_2 ] \sim (n/2)^2$
