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


2 Answers 2


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

  • $\begingroup$ Can someone help me hyperlink to the MSE question? I couldn't make it work. $\endgroup$
    – user6096
    Sep 25, 2011 at 20:08
  • $\begingroup$ 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? $\endgroup$
    – Will Sawin
    Sep 25, 2011 at 22:34
  • 2
    $\begingroup$ The asymptotic distribution of the largest part (actually the $j$ largest parts) of a random composition is at arxiv.org/pdf/1005.1957 . $\endgroup$ Sep 25, 2011 at 22:55



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

  • 1
    $\begingroup$ 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. $\endgroup$ Sep 25, 2011 at 22:00
  • $\begingroup$ If you know the distribution, then you know what the probability that some cell is bigger than a furlong. N'est-ce pas? $\endgroup$
    – Igor Rivin
    Sep 26, 2011 at 14:48
  • $\begingroup$ 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. $\endgroup$ Sep 26, 2011 at 16:42

Your Answer

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

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