# 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$?

-
Does ot work for, say, $n=3, k = 3$? – Dilip Sarwate Jan 10 '13 at 3:00
You seem to be assuming distinct samples (i.e. sampling without replacement). If so, the result follows by symmetry. It seems you want $=$ where you have $\le$ in the displayed equation, by the way. – joriki Jan 10 '13 at 3:00
@joriki But the question also says "... we independently take ..." which would seem to imply sampling with replacement. – Dilip Sarwate Jan 10 '13 at 3:05
@somebody: Then $1/k$ is clearly false, since each item has the same probability of being greater than all the others, so the total probability for one of them being greater than the others would be $k\cdot1/k=1$, which it isn't if there can be ties. Also, your own example is wrong in this case, since the probability $1/6$ is the one for sampling without replacement and should be $1/9$ with replacement. – joriki Jan 10 '13 at 3:07
@somebody: then the calculation is wrong. I'm doing this while walking. :) If you draw twice from a uniformly distributed RV.,.what is the probability of second larger than first? 1/2. I think somewhere along the way this got screwed up: in fact, I'm not sure it's true if you remove sampled elements. But for iid draws, it's 1/k. – gnometorule Jan 10 '13 at 3:29

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.