Probability distribution for distances between randomly selected integers within an interval

Question

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.

Answer 1

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)$.

Answer 2

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)$.

Answer 3

For some reason, all existing answers to this question, including the accepted one, only discuss either the expected value of the nearest-neighbour distances or the distribution of the shortest nearest-neighbour distance, but not the distribution of the nearest-neighbour distances. This was also the subject of the later question Distribution probability of elements and pair-wise differences in a sorted list, which is very similar to this one, though neither is an exact duplicate of the other.

My answer to that question, adapted to the notation of the present question, gives the probability

$$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$.

Answer 4

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}$.

Answer 5

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$.