4
$\begingroup$

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

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
3
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\begingroup$ Can someone help me hyperlink to the MSE question? I couldn't make it work. $\endgroup$
    – user6096
    Commented 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
    Commented 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$
    – Brendan McKay
    Commented Sep 25, 2011 at 22:55
1
$\begingroup$

See

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

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

Improve this answer
$\endgroup$
3
  • 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$
    – Douglas Zare
    Commented 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
    Commented 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$
    – Douglas Zare
    Commented Sep 26, 2011 at 16:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .