probability of certain order when sampling uniformly Suppose that we have a discrete uniform sample space $\{1,\dots,n\}$ and we independently take $k\le n$ samples $X_1,\dots,X_k$. What is the probability that $X_k>X_1,\dots,X_{k-1}$? 
I believe that it is $1/k$ and in particular it is independent of $n$. 
For example $n=3$ and $k=2$:
\begin{align}
P[ X_2>X_1 ] &= P[ (X_1 = 1 \land X_2=2) \lor (X_1 = 1 \land X_2=3) \lor (X_1 = 2 \land X_2 = 3)] \\ &= 3 * (1/9) = 1/3
\end{align}
Edit: The above computation is wrong, but I'm not sure why.
How can I show this for general $n$?
 A: Let $M_{k-1}=\max\{X_1,\ldots,X_{k-1}\}$, then, for every $1\leqslant i\leqslant n$, $[M_{k-1}\leqslant i]=\bigcap\limits_{\ell=1}^{k-1}[X_\ell\leqslant i]$ hence 
$$
\mathbb P(M_{k-1}\leqslant i)=\left(\frac{i}n\right)^{k-1}.
$$
Let $A_k=[\forall\ell\leqslant k-1,X_\ell\lt X_k]$, then $A_k=[X_k\gt M_{k-1}]$ hence
$$
\mathbb P(A_k\mid M_{k-1}=i)=\frac{n-i}n.
$$
This implies
$$
\mathbb P(A_k)=\sum_{i=1}^n\frac{n-i}n\mathbb P(M_{k-1}=i)=\sum_{i=1}^n\frac{n-i}n\left(\left(\frac{i}n\right)^{k-1}-\left(\frac{i-1}n\right)^{k-1}\right).
$$
Decomposing the sum on the RHS and using the change of variables $i\to i+1$ in some parts, one gets finally
$$
\mathbb P(A_k)=\frac1{n^k}\sum_{i=0}^{n-1}i^{k-1}=\frac1{n^k}\frac{B_k(n)-B_k(0)}k,
$$
where $B_k$ is the $k$th Bernoulli polynomial. Comparisons on sums with Riemann integrals yield
$$
\frac1k\left(1-\frac1{n^k}\right)\leqslant\mathbb P(A_k)\leqslant\frac1k.
$$
Sanity checks: 


*

*$\mathbb P(A_1)=1$ since $X_1$ is always the highest value so far, being the only one.

*$\mathbb P(A_2)=\frac12\frac{n-1}{n}$ since the probability of a tie is $\frac1n$ and if $X_1\ne X_2$, each has as much chance to be the highest value.

*When $n\to\infty$, $\mathbb P(A_k)\to\frac1k$ since the ties disappear.

