# Distribution of the biggest gap

Randomly select $n$ numbers from the universe $\{1,2\dots,m\}$ without replacement, and sort the numbers in ascending order.

We can get a list of number $\{(a_1,a_2,\dots,a_n\)}$, and then we can get the difference between two consecutive numbers and get the gap list: $\{(a_1, a_2-a_1,\dots ,a_n-a_{n-1})\}$

Among these gaps, there must be a biggest one, say $a_{\max}$.

So what is the distribution of $Pr(a_{\max}=k)$?

-

This is the answer to a slightly modified version of the problem. I hope that it would also lead to a solution of the original version.

As I point out in my answer to Math StackExchange question 66430 ("What is the distribution of gaps?"), if, in addition to the gaps $G_1=a_1$and $G_j:=a_j-a_{j-1}$ for $2\leq j\leq n$, you introduce final gap $G_{n+1}=(m+1)-a_n$, the random vector $(G_1,G_2,\dots, G_{n+1})$ gives a random composition of the number $m+1$. That is, all outcomes $(g_1,g_2,\dots, g_{n+1})$ with $$g_1+g_2+\cdots+g_{n+1}=m+1,\quad g_j\geq 1$$ are equally likely. There are $m\choose n$ such compositions, as found using stars and bars.

Then $Pr(a_{\max}\leq k)$ (where my maximum includes the final gap) is just the proportion of compositions using numbers from $1$ to $k$. By inclusion-exclusion and stars and bars, this probability is $$Pr(a_{\max}\leq k)={\sum_{x} (-1)^x {m-xk\choose n}{n+1\choose x}\over{m\choose n}}.$$

-
Can someone help me hyperlink to the MSE question? I couldn't make it work. –  Byron Schmuland Sep 25 '11 at 20:08
One way to convert this to a solution to the whole problem is to use your answer with m-1 and a_n instead of m and n. Then you just need to find the distribution of a_n, which is not difficult. The downside to this is that it produces a double sum - perhaps it can be simplified? –  Will Sawin Sep 25 '11 at 22:34
The asymptotic distribution of the largest part (actually the $j$ largest parts) of a random composition is at arxiv.org/pdf/1005.1957 . –  Brendan McKay Sep 25 '11 at 22:55

See

http://arxiv.org/pdf/cond-mat/0406116v2

for a more general version of the question (the 1-dim case is considered at length).

-
That paper studies the distribution of the size of a Voronoi cell, the average of two adjacent intervals, but not the maximum size of either an interval or Voronoi cell. –  Douglas Zare Sep 25 '11 at 22:00
If you know the distribution, then you know what the probability that some cell is bigger than a furlong. N'est-ce pas? –  Igor Rivin Sep 26 '11 at 14:48
You would if the cell sizes were independent, but they are not. Perhaps the dependence is mild enough that pretending that the sizes are independent would not produce large errors. –  Douglas Zare Sep 26 '11 at 16:42