# What's the distribution of the closest point from uniform samples?

Suppose you have $$N$$ values $$x_1, \ldots, x_N$$ that are uniformly sampled in $$[0; 1]$$. For a random $$x_k$$ amongst the $$(x_i)_i$$ (with equiprobability), what is the expected value of the distance between $$x_k$$ and the closest $$x_j\in (x_i)_i$$ (with obviously $$k\neq j$$) ?

For an analytic solution, you need to start by finding the distributions of differences between adjacent order statistics. Then you need to deal with two cases: (a) where $$X_j$$ is the max or min because those to order statistics have only one neighbor, and (b) where $$X_j$$ is somewhere in the middle.

Intuitively, if you have $$n$$ observations, the order statistics are on average spaced equally, so that the average distance between them is $$\frac{1}{n+1}.$$ That takes care of case (a). For case (b), the closest of two differences will be smaller.

By simulation, the average distance from the min $$X_{1:n}$$ to the next larger value $$X_{2:n}$$ does indeed seem to be $$\frac{1}{n+1}.$$ By symmetry, the average distance between $$X_{(n-1):n}$$ and $$X_{n:n}$$ is the same. Simulation if you happen to choose the smallest of $$n=5:$$

set.seed(725)  # for reproducibility
m = 10^6;  n = 5;  d = numeric(m)
for(i in 1:m) {
x = sort(runif(n))
d[i] = x[2] - x[1] }
mean(d)
[1] 0.1666103  # aprx 1/6


Simulation, if you happen to choose a value other than the max or min. This seems to be half as large as for the max or min.

set.seed(2019)
m = 10^5;  n = 5;  d = numeric(m)
for(i in 1:m) {
x = sort(runif(n))
d[i] =  min(diff(x[2:4])) }
mean(d)
[1] 0.08302884


So it seems the answer for a randomly chosen one of $$n = 5$$ is $$(2/5)(1/6) + (3/5)(1/12) = 7/60.$$

• For reference: Pyke (1965) on page 398 confirms that the expected value is $(n+1)^{-1}$. Jul 25, 2019 at 9:28