Suppose $3$ points are drawn uniformly at random from $[0,1]$. Call them $x_1,x_2,x_3$ with $x_1\leq x_2\leq x_3$. I am interested in the distances between them.

Fix $0<a<b<1$. I want to compute the probability $P$ that $$x_2-x_1 < a, \ \ \ \ x_3 -x_2 < a,\ \ \ \ x_3-x_1 > b$$ In other words, the two pairs of adjacent points are $a$-close to each other, but the two outside points are $b$-far apart. Clearly this can't happen unless $b<2a$.

Since we have a uniform distribution, we can integrate the constant density $\equiv 1$ over the appropriate region in $[0,1]^3$. Now, $x_2$ must be within $a$ of $x_1$, and $x_3$ has to be at least $b$ greater than $x_1$ but not more than $a$ above $x_2$. This gives the following:

$$P = \int_0^{1-2a}\int_{x_1}^{x_1+a}\int_{x_1+b}^{x_2+a}\ dx_3\ dx_2\ dx_1$$

The problem: $x_{1}$ doesn't have to be less than $1-2a$; it should be able to be as large as $1-b$ (well technically, arbitrarily close to it but still less than). For instance, if $a=.2, b=.3$ then an acceptable set of points would be $.69,.85,1$. Clearly there are $2$ cases to consider, but I'm having a hard time explicitly differentiating the cases in order to write down two integrals. It seems the second case should look like

$$\int_{1-2a}^{1-b}\int_{x_1}^{x_1+a}\int_{x_1+b}^1\ dx_3\ dx_2\ dx_1$$

However I don't feel that this is correct. Specifically, it doesn't look like the above guarantees that $x_3-x_2<a$. Are these the only two cases to consider? What are the appropriate bounds in the second integral? Is there a better way to approach this problem?


How about this order? (Using physics notation, where we place the differential form next to the integral sign)

$$\int_0^{1-b} dx_1 \int_{x_1+b}^{\min(1,x_1+2a)} dx_3 \int_{x_3-a}^{x_1+a} dx_2$$

That seems reasonable to simplify. To get the desired probability, don't forget to normalize by the volume of the simplex $x_1<x_2<x_3$, which is $\frac{1}{3!}$.

  • $\begingroup$ Thank you, this ordering is much more clear and the bounds look correct. I ran some simulations in Matlab and they agree with your solution. And yes, I knew to multiply by $3!$ but forgot to include that in the question - thanks for pointing that out! $\endgroup$ – pwerth Aug 9 '17 at 19:39

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.