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) = \begin{cases} \frac{1}{L} & \textrm{if} \quad{} x \in [0,L]\\ 0 & \textrm{otherwise}\end{cases}$$

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| = \begin{cases} 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{cases}$$

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{align} \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\\[6pt] &= \frac{1}{L^2} \int_0^L\int_0^L |x_1 - x_2| \,d x_1 \, d x_2\\[6pt] &= \frac{1}{L^2} \int_0^L\int_0^{x_1} (x_1 - x_2) \,d x_2 \, d x_1 + \frac{1}{L^2} \int_0^L\int_{x_1}^L (x_2 - x_1) \,d x_2 \, d x_1\\[6pt] &= \frac{L^3}{6 L^2} + \frac{L^3}{6 L^2} = \frac{L}{3}\end{align}

-
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
@RodCarvalho : If you use "cases" and "align" in the standard way, instead of "array" as a substitute for those, then you don't have to keep repeating \displaystyle. I edited your answer accordingly. ${}\qquad{}$ – Michael Hardy Nov 21 '15 at 19:08

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

Without loss of generality, let the interval length be L and the sought average difference D.

The answer is seen to be D=L/3 by the following simple argument: Select 3 random values a,b,c on the interval of length L. The probability that c is between a and b equals 1/3 since the other equiprobable alternatives are that a or b are in the middle. Since the interval length is L, the probability must also be D/L, thus D=L/3.

-

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 '15 at 20:28
Which is not 3.3. Like I said, close but different. – mlohbihler Aug 18 '15 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 '15 at 22:41
Your approach is generally correct, but the result is not absolutely accurate. In your experiment you broke the line into 10 parts. What if it was only 2 parts? Or only 1 part? (with 1 part your answer will be 0 - very inaccurate). Breaking into two parts will give you 0.25. Breaking into 10 parts gives 0.33. Why do you think 0.33 is correct, why not 0.25? Of course, more parts you take, more accurate your answer will be. – lesnik Nov 21 '15 at 19:10
@lesnik, mcmeyer provided the answer below, referencing Byron's work. In discrete cases such as mine and your examples, the answer is what it is, and it is correct. With only one part (i.e. a point) the distance between points will always be zero, so the answer of 0 will in fact be quite accurate. However, as N approaches infinity, the average approaches N/3. – mlohbihler Nov 23 '15 at 16:23

Byron's answer is short and elegant. Here's a geometric/algebraic derivation: Let $X$ and $Y$ be two independent uniform variates in $[0,1]$. Then $$p\left(\{|X-Y|>s\}\right) = (1-s)^2$$ as can be seen by viewing $(X,Y)$ as a uniform variate in $[0,1]^2$, where the set $\{|X-Y|>s\}$ occupies the top left and bottom right triangles of the square box $[0,1]^2$. See figure (a). Now we have $p\left(\{|X-Y|<s\}\right) = 1-(1-s)^2$ and therefore $$p\left(\{|X-Y|=s\}\right) = {d\over ds}p\left(\{|X-Y|<s\}\right) = 2(1-s) .$$ The result follows immediately: $\mathbb{E}\,|X-Y| = \int_0^1 2s(1-s)\,ds = {1\over 3}.$

Sidenote: The discrete case is analogous. Let $(X,Y)$ be independent uniform variates in $\left\{1,2,\dots,N\right\}^2$. Then $$p\left(|X-Y|=s\right) = 2(N-s), \quad s>0$$ as can be seen from mlohbiehler's plot. (Note that the equation is not valid for $n=0$.) The expectation is $$\mathbb E |X-Y| = {1\over N^2}\sum_{s=1}^N s\,2\,(N-s) = \frac{N^2-1}{3 N} .$$ Asymptotically for $N\to\infty$ this is ${N\over3}$.

Figure (a) and (b)

-