1
$\begingroup$

Say there are $K > 3$ distinct numbers $a_1 < a_2 < \dots < a_{K-1}<a_K$. 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.

$\endgroup$
12
  • 1
    $\begingroup$ @CalvinLin The question is not asking about three particular elements, but about the existence of three such elements. $\endgroup$
    – angryavian
    Commented Nov 12, 2021 at 1:33
  • $\begingroup$ @angryavian Thanks for the clarification. Yes, the question is asking about the probability of the existence of such three elements. $\endgroup$
    – W_Qiu
    Commented Nov 12, 2021 at 1:58
  • $\begingroup$ 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)!}$. $\endgroup$ Commented Nov 12, 2021 at 2:01
  • $\begingroup$ @VarunVejalla could you provide a link to the result? or could you let me know what keywords you are using for the searching? thanks. $\endgroup$
    – W_Qiu
    Commented Nov 12, 2021 at 2:06
  • $\begingroup$ A056986 gives the total number of valid permutations; this divided by $K!$ would give the probability of getting a valid permutation. $\endgroup$ Commented Nov 12, 2021 at 2:12

1 Answer 1

1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .