Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 1 down vote accepted

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}$.

share|cite|improve this answer
now it's like it should be – Johnny Nov 23 '12 at 0:01

$$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}$$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.