# How to prove independence of applicants' relative ranks in secretary problem?

After familiarizing myself with the theory of optimal stopping concerning finite horizon case, I decided to analyze a solution of the secretary problem presented by Y.S. Chow et al. in "Great Expectations". I believe I am quite comfortable with Snell envelope and method of backward induction, however I cannot puzzle out the independence of relative ranks of applicants.
Let me describe the problem precisely:

Let $A_1,A_2,\ldots,A_N$ denote a permutation of the integers $1,2,\ldots,N$, all permutations being equally likely. The integer $1$ corresponds to the best girl, $\ldots,$ $N$ to the worst. For any $n=1,\ldots,N$ let $Y_N=$ number of terms $A_1,\ldots, A_N$ which are $\le A_n$ ($Y_n=$ relative rank of the $n$th girl to appear) (...)
(?) It is easy to see that $Y_1,\ldots,Y_N$ are independent (?) and that $$\mathbb{P}(Y_n=j)=\frac{1}{n}, \quad j=1,2\ldots, n.$$

Could you please show me how to prove the claim I embraced with question marks? My combinatorial skills are poor, I would appreciate any hints!

Edit: (based on joriki's answer) Let $1\le i_1<i_2<\ldots<i_k\le N$ be $k$ fixed integers. We have to show that $$\mathbb{P}(Y_{i_1}=j_1,Y_{i_2}=j_2,\ldots,Y_{i_k}=j_k)=\mathbb{P}(Y_{i_1}=j_1)\mathbb{P}(Y_{i_2}=j_2)\ldots\mathbb{P}(Y_{i_k}=j_k)$$ for arbitrary $j_1\in\{1,2,\ldots,i_1\},\, j_2\in\{1,2\dots,i_2\},\ldots,\,j_k\in\{1,2,\ldots,i_k\}$.
Since each permutation of first $n$ candidates is equally likely, independent of who the $m$th candidate with $m>n$ is, \begin{aligned} \text{LHS} &= \mathbb{P}(Y_{i_1}=j_1\mid Y_{i_2}=j_2,\ldots,Y_{i_k}=j_k)\mathbb{P}(Y_{i_2}=j_2,\ldots,Y_{i_k}=j_k) \\ &= \mathbb{P}(Y_{i_1}=j_1)\mathbb{P}(Y_{i_2}=j_2,\ldots,Y_{i_k}=j_k) \\ &= \mathbb{P}(Y_{i_1}=j_1)\mathbb{P}(Y_{i_2}=j_2\mid Y_{i_3}=j_3\ldots,Y_{i_k}=j_k)\mathbb{P}(Y_{i_3}=j_3\ldots,Y_{i_k}=j_k)\\ &= \ldots \\ &= \mathbb{P}(Y_{i_1}=j_1)\mathbb{P}(Y_{i_2}=j_2)\ldots\mathbb{P}(Y_{i_k}=j_k)=\text{RHS}. \end{aligned}

• There are enough letters in the Latin alphabet to avoid confusing yourself with lowercase and uppercase versions of the same letter :-) I believe where it says $Y_N$ you mean $Y_n$, and the $A_N$ after that should be $A_n$? – joriki Mar 15 '13 at 23:17
• Yes, you're obviously right. I've got rid of all $n$'s. :) Thank you! – Kuba Helsztyński Mar 15 '13 at 23:27

This follows from the fact that all $n!$ permutations of the first $n$ candidates are equally likely, independent of who the $k$-th candidate with $k\gt n$ is, and $Y_n$ takes the values $1$ through $n$ with equal probabilities for these $n!$ permutations.