Expected Value of $[|X-Y|]$

Question

$\newcommand{\Ex}{\operatorname{Ex}}\newcommand{\Pr}{\operatorname{Pr}}$Given Two independent random variables, $X$ and $Y$, are each drawn uniformly from $\{1, 2, . . . ,n\}$, where $n\ge 1$ is an integer. What is $\Ex[|X−Y|]$?

I have figured out that $$ \Ex[|X−Y|] = \Pr[X \ge Y] \cdot (\Ex[X] - \Ex[Y]) + \Pr[Y > X] \cdot (\Ex[Y] - \Ex[X]).$$

But I am struggling to find values for $\Pr[X \ge Y]$ and $\Pr[Y > X]$. I played around with using the sum of a cumulative distribution function, but that lead me to a probability of over 100% oops!

Any advice on where to go from here?

Answer 1

Guide:\begin{align} Pr(X \ge Y) &= \sum_{y=1}^n Pr(X \ge y)Pr(Y=y) \\ &= \frac1n \sum_{y=1}^nPr(X \ge y) \\ &= \frac1n \sum_{y=1}^n \frac{n-y+1}{n} \\ &=\frac{1}{n^2}\sum_{y=1}^n (n-y+1) \\ &=\frac{1}{n^2} \left[n(n+1)-\frac{n(n+1)}{2}\right]\\ &=\frac{n(n+1)}{2n^2} \\ &= \frac{n+1}{2n} \end{align}

For the other quantity, you can either compute $P(X>Y)$ directly or subtract $P(X=Y)$ from $P(X \ge Y)$.

Answer 2

$\require{cancel}\mathsf E(\lvert X-Y\rvert) ~{={\mathsf P(X>Y)~\mathsf E(X-Y\mid X>Y)+\cancelto{0}{\mathsf P(X=Y)~\mathsf E(X-Y\mid X=Y)}+\mathsf P(X<Y)~\mathsf E(Y-X\mid X<Y)}\\=2~\mathsf P(X<Y)\cdot \mathsf E(Y-X\mid X<Y)\qquad\text{by symmetry}}$

Now $\mathsf P(X<Y) = \tfrac 12(1-\mathsf P(X=Y)) = \tfrac {n-1}{2n}$

However, $\mathsf E(X-Y\mid X<Y)\neq \mathsf E(X)-\mathsf E(Y)$.

What you need is: $\displaystyle 2\,\mathsf P(X<Y)~\mathsf E(Y-X\mid X<Y) ~{= 2\sum_{y=2}^n\sum_{x=1}^{y-1}\frac {y-x}{n^2} \\=\sum_{y=2}^n\frac{y(y-1)}{n^2}\\=\frac{(n-1)(n+1)}{3n}}$