Average Distance Between Random Points on a Line Segment

Question

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

Answer 1

Byron has already answered your question, but I will attempt to provide a detailed solution...

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

Answer 2

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:

Answer 3

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.

Answer 4

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)

Answer 5

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

Answer 6

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

Answer 7

You can picture this problem from a discrete approach, then extend it to the real number line.

For the first L natural numbers, the difference between any two of them may range from 1 through L-1. Exactly N pairs of numbers from our set will be L-N units apart. Taking that into account we sum:

Sum of distances = sum (0 < x < L, x*(L-x))

Which turns out to be (L-1)(L)(L+1)/6

We then divide by combinations of L in 2 and get the average distance (L+1)/3, which becomes L/3 as we allow for infinitely many more numbers in the [0;L] interval.

Answer 8

It is possible to solve this using limits however the solution is somewhat inelegant.

Split the line L into $(k+1)$ equal segments by placing points $p_1$, $p_2$, ... $p_{k}$ on the line. The length of each segment is $\dfrac L{k+1}$. Let $S_i$ be the sum of distances from point $p_i$ to all other points.

$S_i$ = $ \dfrac L{k+1} \sum_{j=1}^{i-1} j + \dfrac L{k+1} \sum_{j=1}^{k-i} j $

$S_i$ = $\dfrac L{2(k+1)} ( (k-i) (k-i+1) + (i-1) (i) )$

$S_i$ = $\dfrac L{2(k+1)} ( 2i^2 - 2i(k+1) + k(k+1) )$

Now, the sum of all distances from every point to every other point is $\sum_{i=1}^{i=k} S_i$. Also, the number of pairs of points is $k^2$. Therefore the average $A_k$ is $\dfrac{\sum_{i=1}^{i=k} S_i}{k^2}$

$\sum_{i=1}^{i=k} S_i = \dfrac L{2(k+1)} \sum_{i=1}^{i=k} ( 2i^2 - 2i(k+1) + k(k+1) ) $

$A_k = \dfrac L{2(k+1)k^2} \sum_{i=1}^{i=k} ( 2i^2 - 2i(k+1) + k(k+1) ) $

$A_k = \dfrac {2L}{2(k+1)k^2} \dfrac{k(k+1)(2k+1)}6 - \dfrac {2L(k+1)}{2(k+1)k^2} \dfrac{k(k+1)}2 + \dfrac {L(k(k+1))}{2(k+1)k^2}k $

$A_k = \dfrac {L(2k+1)}{6k} - \dfrac {L(k+1)}{2k} + \dfrac {L}{2} $

$A_k = \dfrac {L}{6k} (2k+1 - 3k-3 + 3k) $

$A_k = \dfrac {L}{3k} (k-1) $

$A_k = \dfrac L3 - \dfrac L{3k} $

Now, we just need to make the line segments infinitely small, i.e infinitely large $k$ and we're done.

$\lim_{k \to +\infty} A_k$ = $ \dfrac L3 - \lim_{k \to +\infty} \dfrac {L}{3k} = \dfrac L3 \space\blacksquare $

Answer 9

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?

Answer 10

Differences represented by a line from 0-15

I took the brute force approach as noted above and thought about letting the size of the line (and hence the square with the differences) range from 0 to infinity. Taking the total absolute differences for squares ranging from 0 to n then the total number of integer points that can be chosen is n+1. The total count of the number of differences calculated is (n+1)^2. The total of all the differences calculated is twice the triangular numbers which is 2(n(n+1)(n+2))/6. Therefore the average distance between two points is 2(n(n+1)(n+2))/6 all divided by (n+1)^2. To normalise this to the equivalent of a unit line we divide again by (n+1).

For the 0-15 table as above n=15 and the average distance is 0.33203 for n=20 the average distance is 0.33258 and for n=25 the distance is 0.33284. Clearly getting closer to 1/3.

If we let n get larger towards infinity then what happens to 2(n(n+1)(n+2))/6(n+1)(n+1)^2?

This becomes 2/6 or 1/3.

Hopefully this makes sense and is another way to look at the problem.

R

Answer 11

The pdf of the distance is highest closer to zero. This means that distance is more likely to be close to zero than any other positive value. This seems to be puzzling. Put another way, let us divide the segment into equal sized bucket, say 100 buckets .01 length each and number 0 to 99 with bucket i from i*.01 to (i+1)*.01. If you do the experiment for a large number of pairs of points and divide them into buckets, then bucket 0 will contain the largest number of samples. This seems counter intuitive at first. But it makes sense, since after selecting a point closer to the edge makes it twice more likely to select a second point closer to the first point than one farther from it. The closer point can be on either side of the original point but the farther point can only be on one side.