3
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ For reference: Pyke (1965) on page 398 confirms that the expected value is $(n+1)^{-1}$. $\endgroup$ – COOLSerdash Jul 25 '19 at 9:28

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.