# For a random permutation, what is the probability the relative order of at least 3 elements are the same?

Say there are $$K > 3$$ distinct numbers $$a_1 < a_2 < \dots < a_{K-1}. Under a random permutation, what is the probability the relative order of at least 3 elements are the same? Say after the permutation, these elements are labeled as $$b_1, b_2, ..., b_K$$. The question is what is the probability there exists $$i < j < k$$ such that $$b_i < b_j < b_k$$?

PS: Actually, my goal is to prove this probability goes to 1 as K becomes large. I realized the original problem is challenging. If there is an intuitive way to give a lower bound for this probability, it would be great.

• @CalvinLin The question is not asking about three particular elements, but about the existence of three such elements. Commented Nov 12, 2021 at 1:33
• @angryavian Thanks for the clarification. Yes, the question is asking about the probability of the existence of such three elements. Commented Nov 12, 2021 at 1:58
• Searching this probability multiplied by $K!$ on the OEIS yields that the probability is $1-\frac{(2K)!}{(K!)^2(K+1)!}=1-\frac{\binom{2K}{K}}{(K+1)!}$. Commented Nov 12, 2021 at 2:01
• @VarunVejalla could you provide a link to the result? or could you let me know what keywords you are using for the searching? thanks. Commented Nov 12, 2021 at 2:06
• A056986 gives the total number of valid permutations; this divided by $K!$ would give the probability of getting a valid permutation. Commented Nov 12, 2021 at 2:12

Certainly the probability goes to $$1$$ as $$K\to\infty$$. Here is a way to see this:
Let's say the permutation is of $$1, 2, 3, ..., K$$. The probability that $$1, 2, 3$$ appear in order is $$\frac16$$; and therefore the probability that they don't occur in order is $$\frac56$$. The same for the elements $$4, 5, 6$$. So the probability that both $$1,2,3$$ and $$4, 5, 6$$ are out of order is $$\left(\frac56\right)^2$$. So the probability that either $$1,2,3$$ or $$4,5,6$$ is in order is $$1-\left(\frac56\right)^2$$. In general, the probability that at least one of $$1, 2, 3$$ or $$4, 5, 6$$ or ... or $$3t-2, 3t-1, 3t$$ is in order is $$1-\left(\frac56\right)^t$$, which goes to $$1$$ as $$t$$ gets large.
Of course there are many other ways you could get three elements in order, so this just gives a lower bound on the probability. But this lower bound goes to $$1$$, and so the probability you want also goes to $$1$$ (even faster).