Independence of probability of $a_k$ being the largest element among the first $k$ elements in the permutation

Question

The question is:

Let $n \ge 2$ be an integer and consider a uniformly random permutation
($a_1$, $a_2$, . . . , $a_n$) of the set (1, 2, . . . , n).

For each $k$ with $1 \le k \le n$, define the event

$A_k$ = "$a_k$ is the largest element among the first $k$ elements
in the permutation".

Let $k$ and $l$ be two integers with $1 \le k \lt l \le n$. Prove that the events $A_k$ and $A_l$ are independent.

I know that we should define Pr($A_k$), Pr($A_k$), Pr($A_k \cap A_l$) and than check relation between those but I keep getting into a dead end where those events are dependent.

Answer 1

To specify a permutation where $a_k$ is the largest among $\{a_1,\dots,a_k\}$, you choose which $k$ numbers form the set $\{a_1,\dots,a_k\}$ in $\binom{n}k$ ways, you place the largest at the $k^{th}$ spot in $1$ way, you order the other elements in $(k-1)!$ ways, then you order the other $n-k$ elements in $(n-k)!$ ways. Therefore, $$ P(A_k)=\frac{\text{# of valid permutations}}{\text{total number of permutations}}=\frac{\binom{n}k(k-1)!(n-k)!}{n!}=\frac1k $$ Similarly, letting $k<\ell$, in order to specify a permutation where $a_\ell$ is the largest among $a_1,\dots a_\ell$ and $a_k$ among $a_1,\dots,a_k$, you

• Choose the set $\{a_1,\dots,a_\ell\}$ in $\binom{n}\ell$ ways.
• Place the largest element in the $\ell^{th}$ spot.
• From the remaining $\ell-1$ numbers, choose $\{a_1,\dots,a_k\}$ in $\binom{\ell-1}k$ ways.
• Place the largest of those $k$ numbers in the $k^{th}$ spot.
• Choose an order for $a_{k+1},a_{k+2},\dots,a_{\ell-1}$ in $(\ell-1-k)!$ ways.
• Choose an order for $a_1,\dots,a_{k-1}$ in $(k-1)!$ ways.
• Choose an order for$a_{\ell+1},\dots,a_n$ in $(n-\ell)!$ ways.

If you multiply all hose numbers out and divide by $n!$, wou will get $\frac{1}{k\ell}$.