What's the probability of differences among n independent uniform distribution variables?

Question

Given n independent random variables $x_1,x_2,...,x_n$, they have standard uniform distributions over [0,1]. Then what's the probability that there is at least one $|x_i-x_j| >= d$ for any different $i,j$ and $0<=d<=1$?

The discrete form of this problem is as follow:

Given n independent random variables $x_1,x_2,...,x_n$, they have discrete uniform distributions over {0,1,2,...m}. Then what's the probability that there is at least one $|x_i-x_j| >= d$ for any different $i,j$ and the integer d satisfying $0<=d<=m$?

Answer 1

Quite generally, if $P(x)$ is the probability density of $n$ independent random variables and $F(x)=\int_{-\infty}^{x}P(x')dx'$ is their cumulative distribution function, then the joint distribution of the smallest and largest variables $x_{\rm min}<x_{\rm max}$ is given by

$$P(x_{\rm min},x_{\rm max})=n(n-1)P(x_{\rm min})P(x_{\rm max})[F(x_{\rm max})-F(x_{\rm min})]^{n-2}.$$

Several ways to prove this result are given here.

You ask for the probability ${\cal P}(d)$ that the largest spacing exceeds $d$, which follows from

$${\cal P}(d)=\int_{-\infty}^{\infty}dx_{\rm min}\int_{x_{\rm min}+d}^{\infty}dx_{\rm max}\,P(x_{\rm min},x_{\rm max}).$$

For the uniform distribution $P(x)=1$ and $F(x)=x$ for $0<x<1$, so

$$P(x_{\rm min},x_{\rm max})=n(n-1)(x_{\rm max}-x_{\rm min})^{n-2},$$

for $0<x_{\rm min}<x_{\rm max}<1$, and

$${\cal P}(d)=\int_{0}^{1-d}dx_{\rm min}\int_{x_{\rm min}+d}^{1}dx_{\rm max}\,n(n-1)(x_{\rm max}-x_{\rm min})^{n-2}=1-n d^{n-1}+(n-1) d^{n}.$$

Two limits as a check: ${\cal P}(0)=1$, ${\cal P}(1)=0$ (assuming $n\geq 2$).

Answer 2

Let $X$ ~ Uniform(0,1) with pdf $f(x)$:

The joint pdf of the 1st and $n$th order statistics is, say, $g(x_\left(1\right), x_\left(n\right))$:

where I am using the OrderStat function from the mathStatica package for Mathematica to automate the nitty gritties for me (I am one of the authors of the former).

... and with domain of support:

We seek $P(X_\left(n\right)- X_\left(1\right) > d)$:

All done.