Probability of a sorted sequence

Question

Now I tried tackling this question from different sizes and 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

The number of possible sequences is $k^n$. Then number of favourable outcomes, namely weakly increasing sequences, is $\binom{n+k-1}{k-1}=\binom{n+k-1}n$. The probability of finding the random sequence to be increasing is $$ \frac{\binom{n+k-1}{k-1}}{k^n} = \frac{\binom{n+k-1}n}{k^n} = \prod_{i=1}^n\frac{k+i-1}{ik}. $$ To see why the binomial coefficient gives the number of weakly increasing sequences, imagine drawing a bar chart for the function, and tracing a path from position $(0,1)$ (at height $1$ to the left of the first bar) to $(n,k)$ (at height $k$ to the right of the last bar) across the tops of the bars. The path has $n+k-1$ steps, of which $n$ are horizontal across the top of a bar, and $k-1$ are vertical to increase the height.

Answer 2

Each sorted string consists of $n_0$ copies of $0$, followed by $n_1$ copies of $1$, etc., ending with $n_{k-1}$ copies of $k-1$. The restriction on the $n_j$ are that they be nonnegative and sum to $n$. The number of solutions to that has a known expression via binomial coefficients, in this case it is $\binom{n+k-1}{k-1}.$ So if this is placed over the number $k^n$ of possible strings, that is the probability the string is nondecreasing.

Here's a reference for the binomial coefficient use above. The thing being counted is the number of "weak compositions" of $n$, in the terminology used at that site: http://en.wikipedia.org/wiki/Composition_(combinatorics)