current community

your communities

more stack exchange communities

Stack Exchange Inbox Reputation and Badges
tour help
Sign up ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.
up vote 2 down vote favorite

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?

share|cite|improve this question
2  
What do you think? What have you tried? Where did you get stuck? –  Yuval Filmus Sep 7 '13 at 20:11

1 Answer 1

up vote 3 down vote accepted

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.

share|cite|improve this answer
    
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
    
Clear now. Thanks a lot! –  wh1t3cat1k Sep 8 '13 at 6:38

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.