Average Distance Between Random Points on a Line

Suppose I have a line of length L. I now select two points at random along the line. What is the expectation value of the distance between the two points, and why?

-
$L/3$, by symmetry. –  Byron Schmuland Sep 13 '12 at 15:18
Care to elaborate, @Byron? –  David Sep 13 '12 at 16:13
@David I've added more explanation in my answer below. –  Byron Schmuland Sep 13 '12 at 18:21

Let $X$ be a random variable uniformly distributed over $[0,L]$, i.e., the probability density function of $X$ is the following

$$f_X (x) = \displaystyle\left\{\begin{array}{rl} \frac{1}{L} & \textrm{if} \quad{} x \in [0,L]\\ 0 & \textrm{otherwise}\end{array}\right.$$

Let us randomly pick two points in $[0,L]$ independently. Let us denote those by $X_1$ and $X_2$, which are random variables distributed according to $f_X$. The distance between the two points is a new random variable

$$Y = |X_1 - X_2|$$

Hence, we would like to find the expected value $\mathbb{E}(Y) = \mathbb{E}( |X_1 - X_2| )$. Let us introduce function $g$

$$g (x_1,x_2) = |x_1 - x_2| = \displaystyle\left\{\begin{array}{rl} x_1 - x_2 & \textrm{if} \quad{} x_1 \geq x_2\\ x_2 - x_1 & \textrm{if} \quad{} x_2 \geq x_1\end{array}\right.$$

Since the two points are picked independently, the joint probability density function is the product of the pdf's of $X_1$ and $X_2$, i.e., $f_{X_1 X_2} (x_1, x_2) = f_{X_1} (x_1) f_{X_2} (x_2) = 1 / L^2$ in $[0,L] \times [0,L]$. Therefore, the expected value $\mathbb{E}(Y) = \mathbb{E}(g(X_1,X_2))$ is given by

$$\begin{array}{rl} \mathbb{E}(Y) &= \displaystyle\int_{0}^L\int_{0}^L g(x_1,x_2) \, f_{X_1 X_2} (x_1, x_2) \,d x_1 \, d x_2\\ &= \frac{1}{L^2}\displaystyle\int_{0}^L\int_{0}^L |x_1 - x_2| \,d x_1 \, d x_2\\ &= \frac{1}{L^2}\displaystyle\int_{0}^L\int_{0}^{x_1} (x_1 - x_2) \,d x_2 \, d x_1 + \frac{1}{L^2}\displaystyle\int_{0}^L\int_{x_1}^{L} (x_2 - x_1) \,d x_2 \, d x_1\\ &= \frac{L^3}{6 L^2} + \frac{L^3}{6 L^2} = \frac{L}{3}\end{array}$$

-
On the third line of the $\mathbb{E}(Y)$ derivation, shouldn't $d x_1$ and $d x_2$ be swapped? (Or the limits of the integrals.) Pedantic, I know. –  David Sep 13 '12 at 16:17
@David: You're totally right. Thanks for pointing that out. I fixed those typos. –  Rod Carvalho Sep 13 '12 at 16:22

Sorry. I posted a cryptic comment just before running off to class. What I meant was that if $X,Y$ are independent uniform $(0,1)$ random variables, then the triple $$(A,B,C):=(\min(X,Y),\ \max(X,Y)-\min(X,Y),\ 1-\max(X,Y))$$ is an exchangeable sequence. In particular, $\mathbb{E}(A)=\mathbb{E}(B)=\mathbb{E}(C),$ and since $A+B+C=1$ identically we must have $\mathbb{E}(B)=\mathbb{E}(\mbox{distance})={1\over 3}.$

Intuitively, the "average" configuration of two random points on a interval looks like this:

-
What I like the most about this answer is that it can be used to prove the case where we have $n$ points and not only two points $x$ and $y$. Or am I missing something ? –  AJed Sep 11 '13 at 3:40

Let $X_1$ and $X_2$ be independent identically distributed random variables, with $f_X(x) = [0<x<1]$. It is well known that $X \stackrel{d}{=} 1-X$.

For simplicity assume $L=1$.

Therefore $|X_1-X_2| \stackrel{d}{=} |X_1+X_2-1|$. Random variable $D = X_1+X_2-1$ follows symmetric triangular distribution on $(-1,1)$, being a special case of Irwin-Hall distribution. We immediately have: $$f_{|D|}(\ell) = 2 (1-\ell)[0<\ell<1]$$ Immediately yielding the expectation: $$\mathbb{E}(|D|) = \int_0^1 2 \ell(1-\ell) \mathrm{d} \ell = \frac{1}{3}$$

-
What does $\buildrel d\over=$ mean? –  MJD Sep 13 '12 at 16:31
@MJD Symbol $\stackrel{d}{=}$ stands for "equality in distribution". –  Sasha Sep 13 '12 at 16:34

Let $X_1, X_2$ be independent uniformly distributed on $[0,1]$. Assume $X_1=x_1$. Then $P(X_2<x_1) = x_1$. Moreover $E(X_2|X_2<x_1)=\frac{x_1}2$ and $E(X_2|X_2>x-1) = x_1+\frac{1-x_1}2=\frac{1+x_1}2$, hence $E(|X_2-x_1|) = x_1\cdot\frac{x_1}2+(1-x_1)\cdot \frac{1-x_1}2=\frac12-x_1+x_1^2$. Finally $$E(|X_2-X_1|) = \int_0^1E(|X_2-x|)dx = \left[\frac12x-\frac12x^2+\frac13x^3\right]_0^1=\frac13.$$ Hence with an interval of length $L$ isntead of $1$, the answer is $\frac L 3$.

-
In the fourth sentence ("Moreover..") there are two places where on the RHS you wrote $x_2$ when you meant $x_1$, if I am not mistaken. –  David Sep 13 '12 at 15:59
Yes, I did. Thanks –  Hagen von Eitzen Sep 13 '12 at 16:42

I get a close but different result when I approach this with brute force and ignorance. Consider an example: if my random numbers are between 5 and 14 (L=10) and uniformly distributed, I can expect after sufficient iteration to have equally observed each number for both values. Thus I can simply consider a matrix of the differences between each value, and calculate the average of the sum of the values in the matrix.

(Please excuse my formatting. I'm new here.)

     5  6  7  8  9 10 11 12 13 14
-----------------------------
5 | 0  1  2  3  4  5  6  7  8  9
6 | 1  0  1  2  3  4  5  6  7  8
7 | 2  1  0  1  2  3  4  5  6  7
8 | 3  2  1  0  1  2  3  4  5  6
9 | 4  3  2  1  0  1  2  3  4  5
10 | 5  4  3  2  1  0  1  2  3  4
11 | 6  5  4  3  2  1  0  1  2  3
12 | 7  6  5  4  3  2  1  0  1  2
13 | 8  7  6  5  4  3  2  1  0  1
14 | 9  8  7  6  5  4  3  2  1  0


The sum of the differences in this matrix is 330, the count 100, giving an average of 3.3, not 10/3 as expected in other answers.

I don't see anything wrong with this except that i can't see anything wrong with the other answers. Can anyone explain the difference?

-
$10/3=3.333\ldots$ –  AJ Stas Aug 18 at 20:28
Which is not 3.3. Like I said, close but different. –  mlohbihler Aug 18 at 22:06
I think you're just seeing the difference between discrete and continuous. I suspect if you increased $L$ without bound, the average would indeed approach $L/3$. –  Brian Tung Aug 18 at 22:41