Probability that a uniformly random sequence is already sorted

Question

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 \in\mathbb{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.

Answer 1

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}$$

Answer 2

The key to this problem is to count the number of sequences $a_1,\dots,a_n$ of length $n$ that are in sorted order and where every element is from $S$.

Here's a key trick to do that. Given a sequence $a_1,\dots,a_n$, we can form a $k$-tuple $(c_0,\dots,c_{k-1})$ where $c_i$ denotes the number of times that $i$ appears in the sequence $a_1,\dots,a_n$. This $k$-tuple will always satisfy $c_0+\dots+c_{k-1} = n$. Now notice that the each sorted sequence $a_1,\dots,a_n$ corresponds to a unique $k$-tuple $(c_0,\dots,c_{k-1})$.

In other words, there is a bijective correspondence between the following two sets:

$$A = \{(a_1,\dots,a_n) : 0 \le a_1 \le \dots \le a_n < k\}$$ $$C = \{(c_0,\dots,c_{k-1}) : c_0 \ge 0, \dots, c_{k-1} \ge 0, c_0+\dots+c_{k-1} = n\}.$$

Do you see why this bijective correspondence exists? Given a sequence $a_1,\dots,a_n$, we can easily find the corresponding $k$-tuple $(c_0,\dots,c_{k-1})$. The reverse is also true: given a $k$-tuple $(c_0,\dots,c_{k-1})$, it is easy to recover the corresponding sequence $a_1,\dots,a_n$, and that sequence is unique (since the items have to appear in sorted order).

Since these two sets can be put into bijective correspondence, they have the same size: $|A|=|C|$. So, now all we need to do is count the number of such $k$-tuples, i.e., to compute $|C|$. And that's an easier task. It can be done using a standard "stars-and-bars" technique from combinatorics. (If you're not familiar with "stars-and-bars", look it up in a textbook, or ask a separate question about it.) Ultimately, we get the answer

$|A| = |C| = {n+k-1 \choose n}$.

The probability you want to compute is this number, divided by the number of sequences (i.e., divided by $n^k$). So the final answer is: the probability is

$${n+k-1 \choose n}/n^k.$$