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



What's the probability of differences among n independent uniform distribution variables?
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.](http://math.stackexchange.com/questions/198192)


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


