Suppose I have $n$ ball slots numbered $1$ to $n$. In the first try, I throw $k$ balls with uniform probability that land in indices $f(1),f(2), ..., f(k)$. Then, I remove the balls, and throw them again uniformly and they land in $g(1), g(2), ..., g(k)$.
My question is, what is the expectation $$\mathbb{E}(\sum_{i=1}^k |f(i)-g(i)|)$$
For $k=1$, this is just the expected distance between two random points, which would be $\frac{n+1}{3}$, but for $k=2$, it gets a bit complicated with the relative ordering in each throw. Any help?