# Average Distance Between Random Points on a Line Segment

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?

• $L/3$, by symmetry.
– user940
Sep 13, 2012 at 15:18
• Care to elaborate, @Byron? Sep 13, 2012 at 16:13
– user940
Sep 13, 2012 at 18:21
• Can anyone explain how by symmetry we are getting the value as @user940 has stated? Dec 4, 2018 at 17:47
• Here's the symmetry argument, roughly. If you were to randomly break a line into 3 pieces, assuming you don't have any information about how the line breaks, the average length of each piece will be L/3. That feels pretty intuitive. Now imagine you keep the pieces lined up: How many break points are there? Two! These two break points are equivalent to the two random points in OP's question. So if by symmetry the average length of the pieces is L/3, and this is equivalent to the average breakpoints being at L/3 and 2L/3 respectively, their average distance is L/3. Aug 4, 2020 at 13:14

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}

– YSN
Apr 10, 2017 at 15:54
• @xyz Yes. It's $\frac{L}{N^2 - 1}$ Check out this answer mathoverflow.net/questions/1294/… Jun 18, 2018 at 9:12
• @RodCarvalho I am solving similar problem but I am asked to find pdf function of a distance between two uniformly distributed random variables on $[0,2]$ so generalizing it to $[0,L]$ we have situation like above. So my question is if I have convolution when looking for pdf called here $g(x_1,x_2)$ how should I put limits on the inegrals to take both situations $x_1 \leq x_2$ and $x_2<x_1$ into consideration. It is tricky because if pdfs are dependent on $X_1(t)$ and $X_2(t)$ then the integral is dependent only on t.
– Kran
May 6, 2019 at 19:14
• After going to the link in the comment by @AlexSk, I see that $\dfrac{L}{N^2-1}$ is the expected value of the $\textbf{minimum}$ distance between any two points, for $N$ randomly placed points on the line, not the average distance between $N$ randomly placed points on the line.
– Joe
May 13, 2020 at 13:57

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, 2013 at 3:40
• @AJed You are not missing anything. Add an $n+1$th point. Place the $n+1$ points at random on a circle of circumference $L$: clearly each of the $n+1$ gaps is identically distributed (though not independent) and has expectation $\frac{L}{n+1}$. Now split the circle at the point you added, and you have this case for $n$ points. Nov 18, 2020 at 9:49

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.

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)

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. Sep 13, 2012 at 15:59
• Yes, I did. Thanks Sep 13, 2012 at 16:42

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, 2012 at 16:31
• @MJD Symbol $\stackrel{d}{=}$ stands for "equality in distribution". Sep 13, 2012 at 16:34

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.

I have another proof based on limits.

Split the line L into $$k$$ equal segments by placing points $$p_0$$, $$p_2$$, ... $$p_k$$ on the line. The length of each segment is $$\dfrac Lk$$. Let $$S_i$$ be the sum of distances from point $$p_i$$ to all other points.

$$S_i$$ = $$\dfrac Lk \sum_{n=0}^{k-i} n + \dfrac Lk \sum_{n=0}^{i} n$$

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

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

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

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

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

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

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

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

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

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

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}{3(k+1)} = \dfrac L3 \space\blacksquare$$

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$ Aug 18, 2015 at 20:28
• Which is not 3.3. Like I said, close but different. Aug 18, 2015 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$. Aug 18, 2015 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. Nov 21, 2015 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. Nov 23, 2015 at 16:23

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

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.