computing $P\left(\max(U_{(1)}, U_{(2)}-U_{(1)}, \cdots,U_{(n)}-U_{(n-1)} )

Question

Let $U_{1}, \, ... \, ,U_{n}$ be a random sample of uniform random variables $U_i \sim \mathrm{Uniform}(0,1)$. Let $U_{(1)}, \, ... \, , U_{(n)}$ be the order statistics of the sample. My problem is to find $$ P\left(\max(U_{(1)}, U_{(2)}-U_{(1)}, \cdots,U_{(n)}-U_{(n-1)} ) <a\right). $$ where $a$ is a positive fixed value. My guess is that I can use the following relationship $$ U_{(s)}-U_{(r)} \sim \textrm{Beta}(s-r, \, n - s + r +1) \qquad 1 \leq r < s \leq n. $$ Therefore \begin{eqnarray} P\left(\max(U_{(1)}, U_{(2)}-U_{(1)}, \cdots,U_{(n)}-U_{(n-1)} ) <a\right)&=&P\left(\max(U_{(1)}, U_{(1)}, \cdots,U_{(1)} ) <a\right)\\ &=&P\left(U_{(1)} <a\right)\\ &=&\int_0^a n(1-x)^{n-1} dx\\ &=& 1-(1-a)^n \end{eqnarray} I doubt it to be correct! Please help me.

Answer 1

Partial answer for small $a$

For small $a$, specifically $a<\frac{1}{n}$, you can use the fact that the joint distribution of the order statistics is uniform with density $n!$ (see this page). The probability can then be calculated by direct integration to obtain $n!\, a^n$.

In detail, $P\left(\max(U_{(1)}, U_{(2)}-U_{(1)}, \cdots,U_{(n)}-U_{(n-1)} ) <a\right)$ can be written as $P\left(U_{(1)}<a, U_{(2)}<U_{(1)}+a, \cdots,U_{(n)}<U_{(n-1)}+a \right)$, so can be evaluated as $$\int_{x_1=0}^a \int_{x_2=x_1}^{x_1+a}\cdots \int_{x_n=x_{n-1}}^{x_{n-1}+a} f(x_1,x_2,\cdots ,x_n)\,dx_n\, dx_{n-1}\cdots dx_1$$ The density $f(x_1,x_2,\cdots ,x_n)=n!$, as already referenced, so the integral evaluates to $n!\, a^n$.

If $a>\frac{1}{n}$ then the integral above, with $f(x_1,x_2,\cdots ,x_n)=n!$, is an overestimate because $f$ is actually $n!\,I(x_n\leq 1)$ and will become zero at vectors $(x_1,x_2,\cdots ,x_n)$ with $x_n>1$. If $a<\frac{1}{n}$ then $x_n$ is always $\leq 1$ in the above integration.

For general $a$, evaluating the above integral with $f=n!\,I(x_n\leq 1)$ is possible but looks messy. For example, for $n=2$, I obtained $2a^2$ for $a\leq \frac{1}{2}$ and $4a-2a^2-1$ for $a>\frac{1}{2}$.

You can easily check this by simulation in R...

   f<-function(x) # integral for n=2
{
  if(x<=0.5) return(2*x*x)
  if(x>0.5) return(4*x-2*x*x-1)
}

n=2
nsamples=100000
samples=array(0,dim=c(nsamples,n)) # sample[i,] is to be the i'th sample of n uniforms
samplemax=rep(0,nsamples) # samplemax[i] is the maximum of interest, computed for the i'th sample

for(i in 1:nsamples) samples[i,]<-sort(runif(n)) # samples[i,j] is now the j'th order statistic of sample i
for(i in 1:nsamples)
{
  shift=tail(samples[i,],-1)
  samplemax[i]=max(c(samples[i,1],shift-samples[i,1:(n-1)]))
}

a=(0:1000)/1000
cdf=rep(0,1001)
fa=rep(0,1001)
for(i in 1:1001) cdf[i]=length(samplemax[samplemax<=a[i]])/length(samplemax)
plot(a,cdf,type="l")

# Check for n=2
for(i in 1:1001) fa[i]=f(a[i])
points(a,fa,type="l",col="red")