Let's take two independent, random variables $X$ and $Y$ from set $\{1,\ldots,n\}$ probability, that $X =i$ AND $Y = j$ is $\frac{1}{n^2}$. I want to determine the expected value, so I started: $E[Z] = E[|X-Y|] = \sum_i (a_i) \cdot P(|X-Y|=a_i),$ (sum is to $n$) but I don't now how to count $P(|X-Y|=a_i)$, cause some values values are repeated. Can anybody give a prompt?
Random variable $Z = |X-Y|$
2 Answers
Draw the $n\times n$ grid of points with coordinates $(i,j)$, where $i$ and $j$ range from $1$ to $n$. The points $(x,y)$ such that $x-y=k$ are the points on the line $x-y=k$. For $k=0$ there are $n$ such points, the points on the diagonal. For $x-y=1$, there are $n-1$ points, for $x-y=2$ there are $n-2$ points, and so on. For positive $k$, we are dealing with the points of the grid which are below the diagonal line $y=x$.
Similarly, there are $n-1$ points such that $x-y=-1$, $n-2$ points such that $x-y=-2$, and so on. These are the points of our grid above the diagonal $y=x$.
So for $2(n-1)$ points, the absolute value of the difference is $1$, for $2(n-2)$ points the absolute value of the difference is $2$, and so on. Finally, there are $2$ points where the absolute value of the difference is $n-1$. In all cases, each point has probability $\frac{1}{n^2}$. It follows that $E(|X-Y|)=\frac{2}{n^2}\left[(1)(n-1)+(2)(n-2)+(3)(n-3)+\cdots +(n-1)(n-(n-1)) \right].$ We next obtain a closed form for the above expression. By expanding, we can see that our sum is equal to $\frac{2}{n^2}n\left[1+2+3+\cdots+n-1\right] -2\left[1^2+2^2+3^2+\cdots+(n-1)^2\right].$ By the usual formula for the sum of the consecutive integers, and the sum of consecutive integers, we get, after some algebra, $\frac{(n-1)(n+1)}{3n}.$
Remark: The standard formulas that were used for the closed form are $1+2+\cdots+k=\frac{k(k+1)}{2}$ and $1^2+2^2+\cdots +k^2=\frac{k(k+1)(2k+1)}{6}$.
-
0now it's like it should be – 2012-11-23
$E[Z] = E[|X - Y|] = \sum_{i = 1}^n \sum_{j = 1}^n |i - j|P(X = i, Y = j) = \frac{1}{n^2}\sum_{i = 1}^n \sum_{j = 1}^n |i - j| = \frac{2}{n^2}\sum_{i = 1}^{n} \sum_{j = 1}^{i - 1} (i - j) = \frac{2}{n^2}\sum_{i = 1}^{n} i(i - 1) - \frac{i(i - 1)}{2} = \frac{2}{n^2}\sum_{i = 1}^{n}\frac{i(i - 1)}{2} = \frac{1}{n^2}\sum_{i = 1}^{n}i(i - 1) = \frac{1}{n^2}\sum_{i = 1}^{n}i^2 - i = \frac{1}{n^2} \left( \frac{n(n + 1)(2n + 1)}{6} - \frac{n(n + 1)}{2} \right) = \frac{(n + 1)}{2n} \left( \frac{2n + 1}{3} - 1 \right) = \frac{(n - 1)(n + 1)}{3n}$