4
$\begingroup$

Inspired by this recent question, what is the expected value of the minimum of the pairwise distances between $N$ uniform and independent RVs (uniform in $[0,1]$)? i.e. Let $X_1,...,X_N$ these RVs, the question is to find $E[\min_{i\neq j}|X_i-X_j|], \ \ \ 1\leq i,j\leq N$. I'm numerically convinced that the answer is $\frac{1}{N^2-1}$.

$\endgroup$
  • 2
    $\begingroup$ There is a proof provided here math.stackexchange.com/a/2001026/653851 $\endgroup$ – winperikle Jul 25 at 14:14
  • $\begingroup$ @Win Thank you for finding that: although that answer does not explicitly bring it out, it derives the entire distribution, not just the expectation. And although it does so by integration, it uses several steps along the way that provide insight into the problem and therefore are worth studying. $\endgroup$ – whuber Jul 26 at 12:25
3
$\begingroup$

You are correct.

One route to the solution, using only well-known relationships among these variables, is the following:

  1. Generate iid Gamma$(1)$ variates $V_i,$ $i=0,1,2,\ldots, N.$ (These are exponentially distributed variables.)

  2. Set $Y_1=V_0$ and $Y_i=Y_{i-1}+V_{i-1}$ for $i=1,\ldots, N+1.$ These are the partial cumulative sums of the $V_i.$

  3. The order statistics of the $X_i,$ written $0 \le X_{(1)} \le X_{(2)}\le \cdots \le X_{(N)},$ have the same distribution as the $Y_i/Y_{N+1}$ for $i$ between $1$ and $N.$

  4. The minimum of the $|X_i-X_j|, i\ne j,$ must be the minimum of the difference of two consecutive order statistics $X_{(k+1)}-X_{(k)} = V_{k^*}/Y_{N+1}$ for $k^*$ between $1$ and $N-1.$

  5. $V_{k^*}$ is the minimum of the $N-1$ iid exponential variables $V_1,V_2,\ldots,V_{N-1}.$ Thus, when multiplied by $N-1,$ it has a Gamma$(1)$ distribution.

  6. Conditional on the minimum, the remaining $N-2$ Gamma variates in $(5)$ are each distributed as $V_{k^*}$ plus iid Gamma$(1)$ variates. Letting the sum of the latter be $W,$ of which there are $N-2$ terms, that sum can be expressed as $V_{k^*}$ itself plus $(N-2)V_{k^*}$ plus an independent Gamma$(N-2)$ variable $W.$

  7. The denominator in $(3),$ $Y_{N+1}$ itself, is obtained by adding the independent Gamma$(1)$ variables $V_0$ and $V_N$ to that. Their sum with $W$ creates a Gamma$(N-2+1+1)$ = Gamma$(N)$ variable $Z.$

  8. Consequently the minimum distance among the $X_i$ has the distribution of $V_{k^*}/((N-1)V_{k^*}+Z)$ where $(N-1)\,V_{k^*}\sim\Gamma(1)$ and independently $Z\sim \Gamma(N).$

  9. Any ratio of $U$ to $U+Z,$ where independently $U$ has a Gamma$(a)$ distribution and $Z$ has a Gamma$(b)$ distribution, has a Beta$(a,b)$ distribution.

Thus, with $a=1$ and $b=N$ and accounting for the scale factor of $N-1$ in $(8),$

$N-1$ times the minimum distance among the $X_i$ has a Beta$(1,N)$ distribution. Because the expectation of that Beta distribution is $1/(N+1),$ the expectation of the minimum distance is $1/(N-1)\times 1/(N+1) = 1/(N^2-1),$ as claimed.

Deviations from this formula will be clearest for small $N,$ so here is a histogram of a sample of size 100,000 from the minimum $X$ distance for $N=3$ with a graph of the (scaled) Beta density superimposed. The agreement is excellent.

enter image description here

N <- 3
n <- 1e5
set.seed(17)
u <- matrix(runif(N*n), nrow=N)          # IID uniform variates, in `n` columns
u <- apply(u, 2, sort)                   # Their order statistics
u <- apply(u, 2, diff)                   # The gaps between them
x <- apply(matrix(u, nrow=N-1), 2, min)  # The smallest gap
hist(x, breaks=50, freq=FALSE)
curve(dbeta(x*(N-1), 1, N)*(N-1), add=TRUE, col="Red", lwd=2, n=1001)
$\endgroup$
  • $\begingroup$ I can't help thinking there's a simpler derivation that doesn't take this roundabout trip through uniform, exponential, and gamma variables while relying on facts about order statistics, distributions of minima, and conditional distributions of iid exponential variables -- but perhaps there is something instructive about the relationships exhibited here. $\endgroup$ – whuber Jul 25 at 12:29
  • $\begingroup$ I wonder how you came up with this method :) $\endgroup$ – gunes Jul 25 at 19:18
  • $\begingroup$ I'm afraid my account describes pretty closely the sequence of steps I took. The first four are a familiar way to understand gaps among uniform order statistics and the rest consists of attempts to understand $(4)$ without actually integrating. $\endgroup$ – whuber Jul 25 at 19: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.