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

Answer 2

For each $k$ let $[n]_k$ be the family of all subsets of the set $\{1,\dots,n\}$ of size $k$. Then

$$p_{k,n}=P(A_k)=\sum_{S\in [n]_k} P(A_k|\{a_1,\dots,a_k\}=S) P(\{a_1,\dots,a_k\}=S)=$$ $$\sum_{S\in [n]_k} \frac 1kP(\{a_1,\dots,a_k\}=S)=\frac 1k\sum_{S\in [n]_k} P(\{a_1,\dots,a_k\}=S)=\frac 1k.$$

$$P(A_k\cap A_l)=\sum_{S\in [n]_l} P(A_k\cap A_l|\{a_1,\dots,a_l\}=S) P(\{a_1,\dots,a_l\}=S)=$$ $$\sum_{S\in [n]_l} \frac 1l P(A_k|\{a_1,\dots,a_{l-1}\}=S\setminus\max S) P(\{a_1,\dots,a_l\}=S)=$$ $$\sum_{S\in [n]_l} \frac 1l p_{k,l-1}P(\{a_1,\dots,a_l\}=S)=\sum_{S\in [n]_l} \frac 1l\frac 1{k} P(\{a_1,\dots,a_l\}=S)=$$ $$ \frac 1l\frac 1{k}\sum_{S\in [n]_l} P(\{a_1,\dots,a_l\}=S)= \frac 1l\frac 1{k}=P(A_l)P(A_k).$$