2
$\begingroup$

We have $N$ points randomly and uniformly distributed on a ring of length 1. Let $d_i$ be the distance between point $i$ and its first neighbor. We want to know the expected value of the smallest $d_i$, $E([d_i]_{min})$, being specially interested in the case of a quite small value of $N$ ($N<10$).

From numerical simulation it looks like $E([d_i]_{min}^{(N)})=N^{-2}$.

I faced problems in getting rid of correlations. As a first step, I tried to consider neighbors on the right side only, looking for the minimum of $N$ quantities $d_i^{(R)}$ that I suppose to be uncorrelated, but this is not a good approximation for small $N$.

I would be grateful for any help. Thank you

Luce

$\endgroup$
1
  • $\begingroup$ How is the question related to algebraic geometry? $\endgroup$
    – Vanessa
    Dec 3, 2012 at 12:41

3 Answers 3

4
$\begingroup$

You can generate a point-set with the correct joint distribution of gap-sizes by running a rate 1 Poisson point process on the positive real numbers until you have $N$ events. Then wrap around to get a circle by identifying the time of the $N$th event with the origin.

By standard properties of the Poisson process, conditioning on the time of the $N$th point, the first $N-1$ points (forgetting the ordering) are distributed like $N-1$ independent uniform points in the interval from zero to the time of the $N$th point. Therefore, if we rescale the circle to perimeter 1, this is exactly what you want.

The smallest gap is the smallest of $N$ independent standard exponential variables, which has expectation $1/N$. And then there is a factor $1/N$ from the rescaling. So your guess from simulations is correct!

$\endgroup$
1
$\begingroup$

PYKE, R. (1965). Spacings. J. R. Stat. Soc. Ser. B Stat. Methodol. 27 395–449.

$\endgroup$
1
$\begingroup$

The problem is related to the following. Assume you have $K$ i.i.d. Uniform$[0,1]$ points put in the increasing order: $X_1,X_2,.., X_{K-1}$. Let $X_0=0$ and $X_K=1$. Define $D=D_K$ as the minimum distance amongst these $K+1$ points. What is the distribution of $D$?

To answer this, Let $0<Y_1<Y_2<...<Y_K$ be the increasing sequence of points of a Poisson process with rate 1. Let $W_1=Y_1, W_2=Y_2-Y_1, ..., W_K=Y_K-Y_{K-1}$ be the inter-arrival distances; hence they are i.i.d. $Exp(1)$ distributed.

Then $[0,Y_1/Y_{K+1},Y_2/Y_{K+1},...,Y_{K-1}/Y_K,1]$ has the same distribution as $[X_0,X_1,...,X_K]$. For any $a>0$, you can get that the joint probability ${\mathbb P}(\min_i W_i>a,W_1+...+W_K \in [L,L+\delta]) = \delta \frac{(L-Ka)^{K-1} e^{-L} }{(K-1)!}$ for infinitesimally small $\delta>0$.

This will imply that ${\mathbb P}(\min_i W_i/L >v, W_1+...+W_K \in [L,L+\delta]) = \delta \frac{L^{K-1}(1-Kv)^{K-1} e^{-L} }{(K-1)!} $. Since $W_1+...+W_K$ has a Gamma(K,1) distribution with density $\frac{L^{K-1} e^{-L} }{(K-1)!}$, we get that the conditional distribution

${\mathbb P}(\min_i W_i/L >v | W_1+...+W_K=L) = (1-Kv)^{K-1}$ and thus ${\mathbb P}(D<v)=1-(1-Kv)^{K-1}$ and ${\mathbb E}(D)=\int_0^{1/K} {\mathbb P}(D>v) dv=\frac{1}{K^2}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.