48
$\begingroup$

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?

$\endgroup$
  • 11
    $\begingroup$ $L/3$, by symmetry. $\endgroup$ – user940 Sep 13 '12 at 15:18
  • 2
    $\begingroup$ Care to elaborate, @Byron? $\endgroup$ – David Sep 13 '12 at 16:13
  • $\begingroup$ @David I've added more explanation in my answer below. $\endgroup$ – user940 Sep 13 '12 at 18:21
  • $\begingroup$ Can anyone explain how by symmetry we are getting the value as @user940 has stated? $\endgroup$ – tarit goswami Dec 4 '18 at 17:47
  • $\begingroup$ 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. $\endgroup$ – James Bender Aug 4 at 13:14

11 Answers 11

46
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ Was this problem ever studied with N randomly placed points? $\endgroup$ – YSN Apr 10 '17 at 15:54
  • $\begingroup$ @xyz Yes. It's $\frac{L}{N^2 - 1}$ Check out this answer mathoverflow.net/questions/1294/… $\endgroup$ – Alex Sk Jun 18 '18 at 9:12
  • $\begingroup$ @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. $\endgroup$ – Kran May 6 '19 at 19:14
  • $\begingroup$ 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. $\endgroup$ – Joe May 13 at 13:57
40
$\begingroup$

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: enter image description here

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ 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 ? $\endgroup$ – AJed Sep 11 '13 at 3:40
8
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
4
$\begingroup$

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)

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ What does $\buildrel d\over=$ mean? $\endgroup$ – MJD Sep 13 '12 at 16:31
  • 1
    $\begingroup$ @MJD Symbol $\stackrel{d}{=}$ stands for "equality in distribution". $\endgroup$ – Sasha Sep 13 '12 at 16:34
3
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – David Sep 13 '12 at 15:59
  • $\begingroup$ Yes, I did. Thanks $\endgroup$ – Hagen von Eitzen Sep 13 '12 at 16:42
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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?

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ $10/3=3.333\ldots$ $\endgroup$ – Rocket Man Aug 18 '15 at 20:28
  • $\begingroup$ Which is not 3.3. Like I said, close but different. $\endgroup$ – mlohbihler Aug 18 '15 at 22:06
  • 2
    $\begingroup$ 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$. $\endgroup$ – Brian Tung Aug 18 '15 at 22:41
  • 1
    $\begingroup$ 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. $\endgroup$ – lesnik Nov 21 '15 at 19:10
  • $\begingroup$ @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. $\endgroup$ – mlohbihler Nov 23 '15 at 16:23
1
$\begingroup$

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 $

| cite | improve this answer | |
$\endgroup$
-1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
-2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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