Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $X_1, \ldots,X_k$ represent k integers between $1$ and $n$ drawn randomly and without replacement (i.e., there are never repeated numbers). What is the PMF of $Y$, the random variable representing the nearest neighbor distance between draws?

This kind of problem falls into the general setting of computing distances between random variables. Is there any general formalism to work with? I have no idea how to start.

Thanks in advance.

share|cite|improve this question
Presumably by "drawn randomly" you mean "drawn randomly with uniform distribution"? – joriki Jul 25 '12 at 11:35
Yes. Uniformou, Butantã without juxtaposition or the results (not sure what the name for this is) – Gabriel Landi Jul 25 '12 at 12:51
up vote 1 down vote accepted

Update: I have modified the answer using a more sensible definition of $Y$. In terms of the gaps, we only care that $g_j\geq r$ for $2\leq j\leq k$ and we don't care about the size of $g_1$ or $g_{k+1}$. In this case, the number of suitable compositions is $n-(r-1)(k-1)\choose k$, and $$\mathbb{P}(Y\geq r)={{n-(r-1)(k-1)\choose k}\over {n\choose k}}.$$

I have interpreted the problem as follows: you are interested in $Y$, the smallest gap between the sampled values $X_1,\dots,X_k$. If this isn't what you want, you may want to clarify the question.

Let's look more closely at the gaps between the $X$'s. In addition to the gaps $G_1=X_{(1)}$ and $G_j=X_{(j)}−X_{(j−1)}$ for $2≤j≤k$, it is convenient to introduce the final gap $G_{k+1}=(n+1)−X_{(k)}$. Here the bracket notation refers to order statistics.

The random vector $(G_1,G_2,\dots,G_{k+1})$ is a random composition of the number $n+1$. That is, all outcomes $(g_1,g_2,\dots,g_{k+1})$ with $g_1+g_2+\cdots+g_{k+1}=n+1$, $g_j≥1$ are equally likely. There are $n\choose k$ such compositions, as found using stars and bars.

Similarly, the number of compositions with all the $g_j\geq r$ is $n-(r-1)(k+1)\choose k$. Therefore, $$\mathbb{P}(Y\geq r)={{n-(r-1)(k+1)\choose k}\over {n\choose k}}.$$ From this you can work out any property of the random variable $Y$.

See this question as well: What is the distribution of gaps?

share|cite|improve this answer
Mr. Schmuland, thank you for your answer Indeed, I was interpreting $Y$ as signifying the G's in your answer, thinking they could all be treated as a single variable. Is that impossible? This confuses me: suppose I take the limit of both $n$ and $k$ going to $\infty$, but such that k/n remains fixed. Then $Y$ represents E(G's)? Thank you again for your time. – Gabriel Landi Jul 25 '12 at 13:17
I am defining $Y$ to be the smallest of all the $G$'s. I'm not quite sure if that is what you wanted. – Byron Schmuland Jul 25 '12 at 16:13

The removal of numbers with uniform distribution leaves the marginal distribution for the remaining draws uniform, so all the nearest-neighbour distances have the same distribution as the first one, which is just


for $d=0\ldots n-1$.

share|cite|improve this answer
Hi @joriki. I really appreciate the answer, but not only did I not understand your argument, but computer simulations I have performed also show a clearly non-linear PMF. Also, in your explanation, where does the fact that there has been k draws enter? This is clearly relevant (taking, for instance, the extreme cases $k=1$ and $k=n$). Thanks again for the attention. – Gabriel Landi Jul 25 '12 at 12:58

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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