4
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
5
  • 1
    $\begingroup$ It seems you are finding the probability that $x_{max}-x_{min}\ge d$, which is not quite what the OP asked about. $\endgroup$ – R W Nov 23 '13 at 16:19
  • 2
    $\begingroup$ did I misread the question? --- the probability that there is at least one spacing greater than $d$, isn't that the same as the probability that the largest spacing is greater than $d$? $\endgroup$ – Carlo Beenakker Nov 23 '13 at 16:22
  • $\begingroup$ Oups - sorry - my bad - thought he was asking about spacings between consecutive numbers in the linear order. $\endgroup$ – R W Nov 23 '13 at 16:59
  • $\begingroup$ @Carlo I agree with your formulation that the probability sought is P(sample range > d). However, I get a different result. $\endgroup$ – wolfies Nov 23 '13 at 18:11
  • $\begingroup$ @wolfies, I've corrected the error in the final integral, thanks for spotting it. $\endgroup$ – Carlo Beenakker Nov 23 '13 at 20:27
4
$\begingroup$

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

enter image description here

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:

enter image description here

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

enter image description here

All done.

$\endgroup$
1
  • $\begingroup$ corrected, thanks for spotting my error. $\endgroup$ – Carlo Beenakker Nov 23 '13 at 20:27

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.