4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Hello, I know it is a stupid question but what you mean by the notation n+k-1 Ck-1? I'm used to see the exp on the right of the base... $\endgroup$ – Phate Jun 10 '18 at 8:55
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.