# Sort algorithm input probabilities

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?

• What do you think? What have you tried? Where did you get stuck? – 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.
• 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? – wh1t3cat1k Sep 7 '13 at 20:41
• 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$. – Yuval Filmus Sep 7 '13 at 21:04