2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – joriki Mar 15 '13 at 23:17
  • 1
    $\begingroup$ Yes, you're obviously right. I've got rid of all $n$'s. :) Thank you! $\endgroup$ – Kuba Helsztyński Mar 15 '13 at 23:27
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Could you please check if I understand you correctly? Thanks in advance! $\endgroup$ – Kuba Helsztyński Mar 16 '13 at 0:05
  • 1
    $\begingroup$ @Kuba: I think you have. However, my advice (which is very subjective; I'm sure there are others on this site who would disagree) would be to take a less formal approach to these things. In my view, the sort of calculation that you wrote down is more likely to hide the essential insight behind a forest of formalities than to lead to greater clarity. The independence is quite an intuitive fact if you look at the problem in the right away, and at least for me that looking in the right way isn't assisted by such formalism. $\endgroup$ – joriki Mar 16 '13 at 0:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.