note: edited to clarify boundary issue

Suppose $x_i$, $i=1\dots n$, are randomly drawn from a uniform circular distribution between 0 and 1 (using periodic boundaries). Let $d_i$ be the distance between $x_i$ and its nearest neighbour to the right (allowing to wrap at the boundary). Now, the mean for $d_i$ is simply $1/n$. But what is the expectation value for $d_{\min}=\min_i\{d_i\}$? (I reckon it must scale as $E\{d_{\min}\}\propto n^{-2}$ -- correct?)

update The distances between uniformly distributed variables are exponentially distributed with rate $n$, i.e. mean $1/n$. Moreover, the minimum of $k$ independent exponential variables of rate $\lambda_i$ is also exponentially distributed (see Wikipedia, for example) with rate $\lambda_1+\dots+\lambda_k$. So, if the distances were independent, the answer is $E\{d_{\min}\}=1/n^2$. But they aren't independent.

  • 1
    $\begingroup$ Walter wrote: "the mean for $d_i$ is simply $1/n$" ........ ---> I think that should be $\frac{1}{1+n}$ $\endgroup$
    – wolfies
    Dec 18 '13 at 18:25
  • $\begingroup$ @wolfies No, because I have $n$ distances (allowing periodic boundaries) which together give 1. $\endgroup$
    – Walter
    Dec 19 '13 at 17:34
  • 1
    $\begingroup$ You specify $n$ points on a standard Uniform distribution, which in turn defines $n+1$ distances. Why would you then 'assume' periodic boundaries???? If you want periodic boundaries, it might be more appropriate if you adopted a circular distribution. $\endgroup$
    – wolfies
    Dec 19 '13 at 17:52
  • 2
    $\begingroup$ Yes, it's expected to scale as $n^{-2}$; in fact, it seems that it actually is equal to $n^{-2}$. Intuitively, this should be related to definite integral of $(1-nx)^{n-1}$ from $0$ to $1/n$ which considers the set $\{(x_1,x_2,\ldots,x_n)\ |\ \sum x_i=1 \}$ (corresponding to the space of possible distances) as compared to its subset in which we additionally require $(\forall i) x_i\geq x$ (configurations where minimal distance is at least $x$). Of course, intuition might be wrong and needs more rigour -- e.g. are the distances really distributed uniformly (as assumed by the reasoning above)? $\endgroup$ Dec 20 '13 at 3:59
  • 1
    $\begingroup$ Why would you think that the "distances between uniformly distributed variables are exponentially distributed"? The difference between two uniformly distributions random variables follows a triangle distribution. What is true, however, is that the distribution of a distance, when rescaled by $n$, and the distribution of the minimal distance, rescaled by $n^2$, both converge to an exponential distribution with parameter 1. $\endgroup$
    – Eckhard
    Dec 25 '13 at 19:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.