# Probability distribution for distances between randomly selected integers within an interval

Suppose I pick 'N' integers over an interval [A, B] without replacement. As a function of 'N' and the interval length, what distribution / average values should I expect for the distances between nearest-neighbors in a sorted array of the selected integers?

Edit: I apologize, an important note is that the distances between the endpoints and the nearest integers to the endpoints should also be included. This is a bit like dividing a piece of rope into (B - A + 1) segments, cutting at the locations representing the 'N' selected integers, and looking at the distribution of cut rope lengths.

Edit 2: Apparently this question is in desperate need of clarification. Extending the rope example I provided, here's exactly what I'm looking for:

Upon cutting the rope into 'N' pieces, and placing these pieces in a bag, I would very much like the probability, P(k), of randomly selecting a fragment of rope of length 'k' from this bag. Here, the probability of selecting a particular fragment of the rope is independent of its length. The function for P(k) provides what I'd like to know about the distribution of rope lengths after 'N' cuts.

-
Can you pick the same point twice? –  Henry Apr 3 '11 at 22:24
@Henry: That happens w.p. $0$ unless $A = B$. –  Yuval Filmus Apr 3 '11 at 22:35
@Yuval Filmus: "Integers" - so with/without replacement matters –  Henry Apr 3 '11 at 22:39
–  joriki Apr 4 '11 at 6:52
@user8861: I think you should clarify your question, and state exactly which parameter you are interested in: minimum distance between two points?, average distance over the whole rope?, average distance over your selected points? none of the above? –  phimuemue Apr 4 '11 at 8:08

Let $X_{(1)}, \ldots, X_{(N)}$ be the chosen integers in increasing order (the order statistics). For simplicity I'll suppose $A = 1$. Of course we must have $B \ge N$. Then I claim that all the "gaps" $X_{(j+1)} - X_{(j)}$ as well as $B+1 - X_{(N)}$ and $X_{(1)} - 0$ have expected value $(B+1)/(N+1)$.

Note that $E[X_{(1)} | X_{(2)}] = X_{(2)}/2$, because given $X_{(2)} = x$, $X_{(1)}$ is equally likely to be any of the integers 1 to $x-1$. Thus $E[X_{(1)}] = E[X_{(2)} - X_{(1)}]$. Similarly, given $X_{(j)} = x$ and $X_{(j+2)} = y$, $X_{(j+1)}$ is equally likely to be any of the integers $x+1$ to $y-1$, so $E[X_{(j+2)} - X_{(j+1)}] = E[X_{(j+1)} - X_{(j)}]$. Similarly, $E[B+1-X_{(N)}] = E[X_{(N)} - X_{(N-1)}]$. Thus all $N+1$ gaps have the same expected value, and since they add up to $B+1$ that expected value is $(B+1)/(N+1)$.

-

Edit The answer below addresses a different question than the original one. That was a mistake of mine, properly signaled by Matthew in a comment, so I deleted my answer. Later on, the OP added some so-called precisions to the question, which in fact change it completely. As a consequence of this modification of the question, my answer becomes relevant, miraculously (modulo the endpoints thing). Call this a manifestation of prescience if you want, anyway I repost my answer, and this is the end of my interventions on this page.

There are $N-1$ distances between nearest-neighbors amongst $N$ points so the mean distance (averaged over a given sample) is the span of the sample divided by $N-1$. The span is the maximum $M$ of the sample minus the minimum $m$ of the sample. By symmetry, $m$ is distributed like $B+A-M$ hence the mean distance (averaged over the samples) is $$E(S)=\frac1{N-1}E(M-m)=\frac1{N-1}(2E(M)-(A+B)).$$ For each $n$ such that $N\le n\le B-A$, there are $n!/(n-N)!$ samples such that $M\le A+n$, hence $$B+1-E(M)=\sum_{n=N}^{B-A}P(M\le A+n)=\frac{(B-A-N)!}{(B-A)!}\sum_{n=N}^{B-A}\frac{n!}{(n-N)!}.$$ Putting all this together should yield $E(S)$.

-
Should all of your A-B expressions be B-A? –  Matthew Conroy Apr 4 '11 at 6:16
@Matthew You are right. Corrected. Thanks. –  Did Apr 4 '11 at 6:19
@Didier Piau I don't follow your argument. The span divided by N-1 does not seem to give the mean nearest neighbor distance. For instance, if A=1, B=10, and N=4, the sample {1, 2, 9, 10} has mean nearest neighbor distance equal to 1 (since each element is exactly a distance 1 from its nearest neighbor), not 9/3, which is the average "gap". Can you clarify? Thanks. –  Matthew Conroy Apr 4 '11 at 6:48
@Matthew I see... If you don't mind, I will cancel this post. –  Did Apr 4 '11 at 6:54
@Didier Piau I don't mind at all. Cheers. –  Matthew Conroy Apr 4 '11 at 6:55
show 1 more comment

I'm not sure if I interpret your question correct, so I tell how I understood you.

You're picking $N$ integers ($X_1,\dots,X_N$) out of the intervall $[A, B]$. Then you obtain w.l.o.g. an ascending sequence of $X$s and are interested in the average distance between two consecutive points, i.e. you want to know

$$\frac{(X_1-A) + (X_2 - X_1) + (X_3 - X_2) + \dots + (X_n-X_{n-1}) + (B-X_n)}{n+1} = \frac{B-A}{n+1}.$$

The above simplification follows from the fact that you can evaluate the numerator is a telescope sum. The result isn't random at all, as you can see, i.e. the expected value of the average distance between neighbours is simply $\frac{B-A}{n+1}$.

-
You've considerably simplified the problem by including the endpoints of the interval :-) The question refers to the distances between nearest neighbours of the selected integers, so $X_1-A$ nd $B-X_n$ don't contribute to the sum. –  joriki Apr 4 '11 at 7:34
@joriki: I thought that was it that was added by the OP by his edit-paragraph. –  phimuemue Apr 4 '11 at 7:37
@joriki @phimuemue: I would take the OP to be asking for the length of the shortest piece of rope after the cuts. But I don't think the OP was asking average length per piece of $N+1$ pieces of rope adding up to $B-A$. –  Henry Apr 4 '11 at 7:47
Sorry, I hadn't noticed the edit. –  joriki Apr 4 '11 at 8:53

There are $N$ places out of $B - A - 1$ where cuts can be made so we must have $N+1 \ge B - A$ to be able to make any cuts. The shortest distance $s$ between neighbours (i.e. cuts and endpoints) must satisfy $s(N+1) \ge B-A$ so the widest possible shortest distance between neighbours is $\lfloor \frac{B-A}{N+1} \rfloor$.

There are $B-A-1 \choose N$ ways of making the $N$ cuts. If the shortest difference between neighbours is at least $s$, then there are $B-A-1 - (s-1)N \choose N$ ways of making the $N$ cuts. So the probability that the shortest distance between neighbours is exactly $s$ is $$Pr(S=s) = \frac{{B-A-1 - (s-1)N \choose N} - {B-A-1 - sN \choose N} }{B-A-1 \choose N}.$$

The expected shortest distance between neighbours is therefore $$E[S]=\sum_{s=1}^{\lfloor \frac{B-A}{N+1} \rfloor} \frac{{B-A-1 - (s-1)N \choose N} }{B-A-1 \choose N} .$$

As an illustration, if $A=10$, $B=20$ and $N=3$, then the widest possible shortest distance is $2$. There are 20 ways of the shortest distance being 2, and 64 ways of it being 1, out of a total of 84. The expected shortest distance is therefore $\frac{104}{84} \approx 1.238$.

-
$$P(d_i=d)=\frac{\binom{B-A+1-d}{N-1}}{\binom{B-A+1}N}$$
that the $i$-th nearest-neighbour distance $d_i$ is $d$, independent of $i$.