Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
add comment

2 Answers

up vote 3 down vote accepted

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

share|improve this answer
    
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
2  
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
add comment

See

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

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

share|improve this answer
1  
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
add comment

Your Answer

 
discard

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.