Problem Detail: Now I tried tackling this question from different perspectives (and already asked a couple of questions here and there), but perhaps only now can I formulate it well and ask you (since I have no good ideas). Let there be $k, n inmathbb{Z_+}$. These are fixed. Consider a set of $k$ integers $S={0, 1, 2, … k-1}$. We form a sequence $a_1, a_2, …, a_n$ by picking numbers from $S$ at random with equal probability $1/k$. The question is – what is the probability of that sequence to be sorted ascending, i.e. $a_1 leq a_2 leq … leq a_n$? Case $k to infty$: This allows us to assume (with probability tending to $1$) that all elements $a_1, …, a_n$ are different. It means that only one ordering out of $n!$ possible is sorted ascending. And since all orderings are equally likely (not sure why though), the probability of the sequence to be sorted is $$frac{1}{n!}.$$ Case k = 2: Now we have zeroes and ones which come to the resulting sequence with probability $0.5$ each. So the probability of any particular n-sequence is $frac{1}{2^n}$. Let us count the number of possible sorted sequences: $$0, 0, 0, ldots, 0, 0$$ $$0, 0, 0, ldots, 0, 1$$ $$0, 0, 0, ldots, 1, 1$$ $$ldots$$ $$0, 0, 1, ldots, 1, 1$$ $$0, 1, 1, ldots, 1, 1$$ $$1, 1, 1, ldots, 1, 1$$ These total to $(n+1)$ possible sequences. Now again, any sequence is equally likely, so the probability of the sequence to be sorted is $$ frac{n+1}{2^n}. $$ Question: I have no idea how to generalize it well for arbitrary $k, n$. Maybe we can tackle it together since my mathematical skills aren’t really that high.
Asked By : wh1t3cat1k
Answered By : Subhayan
You can have $k^n$ possibilities of generating a sequence. Now, there are only $^{n+k-1}C_{k-1}$ favorable outcomes . So, the probability that your sequence is already sorted is: $$ frac{^{n+k-1}C_{k-1}}{k^n}$$
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/14209
