|
4
|
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)$? |
||
|
|
|
3
|
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}}.$$ |
|||||||||||
|
|
1
|
See http://arxiv.org/pdf/cond-mat/0406116v2 for a more general version of the question (the 1-dim case is considered at length). |
|||||||||||
|
