Problem with random permutation and conditional probability Let $\pi_1,...,\pi_n$ be a random permutation of numbers $1,...,n$. If you are told that $\pi_k > \pi_1,...,\pi_k > \pi_{k-1}$, what is the probability that $\pi_k = n$?
What I've tried:
Let $A_j$ be the event that $\pi_k = j$. Let $H$ = be event that $\pi_k > \pi_1,...,\pi_k > \pi_{k-1}$.
Then $P(A_n|H) = \frac{P(H|A_n)P(A_n)}{\sum_{j = 1}^n P(H|A_j)P(A_j)} = \frac{\frac{1}{n}}{\sum_{j=1}^n P(H|A_j)\frac{1}{n}} = \frac{1}{\sum_{j=1}^n P(H|A_j)} = \frac{1}{\sum_{j=1}^n P(j > \pi_1,...,j > \pi_{k-1})}$.
How to calculate that last sum?
 A: That's a great start. The last step isn't quite right, because the last expression no longer contains the information that $\pi_k=j$ (and hence $\pi_1,\ldots,\pi_{k-1}\ne j$). There are $\binom{n-1}{k-1}$ ways to choose $\pi_1,\ldots,\pi_{k-1}\ne j$, and $\binom{j-1}{k-1}$ of them have $\pi_1,\ldots,\pi_{k-1}\lt j$, so
$$
P(H\mid A_j)=
\frac{\binom{j-1}{k-1}}{\binom{n-1}{k-1}}\;,
$$
and
\begin{align}
\sum_{j=1}^nP(H\mid A_j)
&=
\sum_{j=1}^n\frac{\binom{j-1}{k-1}}{\binom{n-1}{k-1}}
\\
&=\frac{\binom nk}{\binom{n-1}{k-1}}\\
&=\frac nk\;.
\end{align}
Thus $P(A_n|H)=\frac kn$. The simple result suggests that it should be possible to obtain it more elegantly, and indeed it is: Uniformly randomly draw a permutation and swap $\pi_k$ with the greatest of $\pi_1,\ldots,\pi_k$ (leaving it unchanged if it's already the greatest). The resulting distribution is the same as the conditional distribution given $H$ (since we have no information other than $H$ about the result), and $\pi_k=n$ exactly if one of $\pi_1,\ldots,\pi_k$ was $n$, with probability $\frac kn$.
