Solution: 2022 Winter Final - 15

Author: Michiel Smid

Question

Let $\pi_1,\ldots,\pi_{20}$ be a random permutation of $\{1,\ldots,20\}$. Define the events: $ A = \pi_{10}>\pi_{11} $ and $ B = \pi_{11} \gt \pi_{12} $ Which of the following is true?

(a)

$\Pr(A\mid B)$ is undefined

(b)

$\Pr(A\cap B) < \Pr(A)\cdot\Pr(B)$

(c)

None of the above

(d)

$\Pr(A\cap B) = \Pr(A)\cdot\Pr(B)$

(e)

$\Pr(A\cap B) > \Pr(A)\cdot\Pr(B)$

Solution

Mathematical Proof for $P(A \cap B) < P(A) \cdot P(B)$

Here is the mathematical explanation for why: $P(A \cap B) < P(A) P(B)$, where

$A: \pi_{10} > \pi_{11}$
$B: \pi_{11} > \pi_{12}$

This setup involves a random permutation of a sequence of 20 distinct numbers.

1. Understanding the Probabilities of the Events

Probability of Event A and Event B

Event $A$ asks whether the value at position 10 is greater than the value at position 11 in a random permutation. In a random permutation, every ordering of the numbers is equally likely. Between two random positions (like 10 and 11), there’s a 50% chance one is greater than the other.

Thus, $P(A) = \frac{1}{2}$

Similarly, the probability that the value at position 11 is greater than the value at position 12 is also: $P(B) = \frac{1}{2}$

2. Joint Probability of P intersect B

The event $A \cap B$ means: $\pi*{10} > \pi*{11}$ and $\pi*{11} > \pi*{12}$. This means that the sequence at positions 10, 11, and 12 is strictly decreasing.

In a random permutation of 20 elements, there are: $\binom{20}{3} \cdot 3!$ ways to select 3 positions (e.g., 10, 11, 12) and arrange them in any order. There are exactly 1 arrangement (out of $3! = 6$) where the sequence is strictly decreasing.

Thus, the probability is: $P(A \cap B) = \frac{1}{6}$

3. Compare P intersect B with P(A)P(B)

Using the values: $P(A)P(B) = \frac{1}{2} \cdot \frac{1}{2} = \frac{1}{4}$

And we found: $P(A \cap B) = \frac{1}{6}$

Comparing the two: $\frac{1}{6} < \frac{1}{4}$, which means we can conclude that $P(A \cap B) < P(A) P(B)$.