0
$\begingroup$

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 ?

  • 0
    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$.2012-11-29
  • 0
    The elements are also unique in the other question; that's what "without replacement" means.2012-11-30

1 Answers 1