Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose a set of $m$ integers from $0$ to $n-1$. The integers are uniformly distributed and unique in the set ($n \gg m$). Then, put all the integers into a list an sort that list: $$x_0 < x_1 < \dots{} < x_{m-1}$$

What is the probability distribution of $x_i$, and of $d_i := x_{i+1} - x_i$ ?

I stumbled on a very similar question, but it only discusses the minimal and average value of $d_i$. It does however present an interesting way to think of it:

Give a rope of size $n$, I cut it on $m$ places chosen uniformly at random (such that, in my case, no two cuts are done at the same spot). What is the probability distribution of the position of the $i^{th}$ cut ? What is the probability distribution of the size of the rope bits ?

I ran some simulations, and $d_i$ seems to have an exponential, maybe Gamma distribution (which is intuitive), and $x_i$ is bell-shaped (probably hypergeometric, which again is rather intuitive) but I cannot figure it out on paper. Any thoughts ?

share|improve this question
    
It's a widespread misconception that whether a question is a duplicate depends on the answers to the question it duplicates. The answers to the question you linked to only discuss the minimal and average value of $d_i$, but the question is about the distribution. The reason your question is not a duplicate of that question is not that that question hasn't been fully answered, but that you also ask about the distribution of the $x_i$. –  joriki Nov 29 '12 at 17:29
    
The elements are also unique in the other question; that's what "without replacement" means. –  joriki Nov 30 '12 at 13:52
add comment

1 Answer

If $x_i=x$, then $x_0,\dotsc,x_{i-1}\in\{0,\dotsc,x-1\}$ and $x_{i+1},\dotsc,x_{m-1}\in\{x+1,\dotsc,n-1\}$. There are $\binom xi\binom{n-x-1}{m-i-1}$ different choices, so the probability is

$$ P(x_i=x)=\frac{\binom xi\binom{n-x-1}{m-i-1}}{\binom nm}\;. $$

For the distribution of $d_i$, add another option $n$ and another unique integer $x_m$, consider the options $0$ to $n$ arranged in a circle, cut the circle by removing $x_m$ and renumber the remaining options beginning with $0$ next to the cut and ending with $n-1$ on the other side of the cut.

What remains is a linear arrangement distributed exactly as in your scenario, but the symmetry we had before we broke it by removing $x_m$ allows us to conclude that all $m+1$ runs of unused options are on the same footing and thus have the same distribution.

But the distribution of the first run of unused options, the ones less than $x_0$, is easy to determine: The probability that $x_0=d-1$ and the remaining $m-1$ numbers are greater is

$$ P(d_i=d)=\frac{\binom{n-d}{m-1}}{\binom nm} $$

for $1\le d\le n-m+1$ and $0$ otherwise.

share|improve this answer
    
Thanks for the answer! I actually had that after I posted the question, but I was not able to check that $\sum_{i=0}^{N-1} \Pr(x_i = x) = 1$, and somehow started doubting on it. The way you put it makes sense though, and I did that sum numerically which seems to be right! A note on $d$: it seems that $\Pr(d_i = 0) = \frac m {N-m+1} > 0$ which makes no sense if elements are unique... Yet you did take that into account in the pdf of $x_i$. Any idea ? –  doc Nov 30 '12 at 13:19
    
@doc: I added the bounds for $d$. You can check (e.g. using Wolfram|Alpha) that the sum of $P(d_i=d)$ over those values of $d$ is $1$. –  joriki Nov 30 '12 at 13:57
    
Indeed, thanks for this great answer :-) –  doc Nov 30 '12 at 13:59
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.