Suppose that there is an algorithm which sorts a sequence of $n$ elements

$$a_1, a_2, ..., a_n$$

Each of the $a_i$ is chosen with probability $1/k$ from a set of $k$ distinct integer numbers.

Is it true, given that $k \to \infty$, that:

  1. The probability that any two of incoming sequence elements are equal, tends to $0$?
  2. The probability that the incoming sequence is already sorted, tends to $\frac{1}{n!}$?

Why / why not?

  • 2
    $\begingroup$ What do you think? What have you tried? Where did you get stuck? $\endgroup$ – Yuval Filmus Sep 7 '13 at 20:11

Here is why you would expect these properties to hold. Suppose that $a_1,\ldots,a_n$ are chosen independently from the uniform distribution on $[0,1]$. The event $a_i = a_j$ has probability zero, and so with probability $1$ all numbers are distinct. Moreover, given that, all sequence orderings are equally likely, and since there are $n!$ of them, the probability that the sequence is ordered is exactly $1/n!$.

To prove that these claims hold in the limit even when the $a_i$ are sampled from a finite set requires some calculation, which I leave to you.

| cite | improve this answer | |
  • $\begingroup$ Thanks! OK, the first one - got it! The second one still isn't that obvious to me. Because, see, with probability 1 all numbers in the n-tuple are distinct; and given that, only one ordering out of $n!$ is a sorted sequence. Then, we have $k \choose n$ ways to pick distinct numbers from the source set. Wouldn't the answer be somehow related to these values? $\endgroup$ – wh1t3cat1k Sep 7 '13 at 20:41
  • $\begingroup$ There is no $k$ in the infinite case. Even in the finite case, $n$ is fixed while $k\to\infty$. There is no connection to $\binom{k}{n}$, since conditioned on the fact that all numbers are distinct, all orders are equally likely. For example, if you randomly pick two distinct $a,b$ from any set of numbers, then half the time $a < b$ and half the time $a > b$. $\endgroup$ – Yuval Filmus Sep 7 '13 at 21:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.