Problem
Job candidates $C_1, C_2, …$ are interviewed one by one, and the interviewer
compares them and keeps an updated list of rankings (if $n$ candidates have
been interviewed so far, this is a list of the $n$ candidates, from best to worst).Assume that there is no limit on the number of candidates available, that for
any $n$ the candidates $C_1, C_2, …,C_n$ are equally likely to arrive in any order, and that there are no ties in the rankings given by the interview.Let $X$ be the index of the first candidate to come along who ranks as better
than the very first candidate $C_1$ (so $C_X$ is better than $C_1$, but the candidates after $1$ but prior to $X$ (if any) are worse than $C_1$. For example, if $C_2$ and $C_3$
are worse than $C_1$ but $C_4$ is better than $C_1$, then $X = 4$. All $4!$ orderings of the first $4$ candidates are equally likely, so it could have happened that the first candidate was the best out of the first $4$ candidates, in which case $X >4$.What is $E(X)$ (which is a measure of how long, on average, the interviewer
needs to wait to find someone better than the very first candidate)?
My question 1
Let's say there are only $2$ job candidates in the entire world.
Then is the pmf of $X$ (which is the index of the first candidate better than the first), something like $X=2$ with probability $1/2$ and $X=$ 'wait forever' with probability $1/2$? So $X$ is Bernoulli? Is that correct?
My quesiton 2
I understand the book solution but what is wrong with my alternative approach of finding the pmf and doing the typical expected value formula?
Let $X = $ the index of the first person better than the very first
Then $P(X=n) = \frac{(n-2)!}{n!} = \frac{1}{n(n-1)}$ where the reasoning is the last person has to be the best and the first person has to be the second best.
Therefore
$$E[X] = \sum_{n=2}^{\infty} \frac{n}{n(n-1)} = 1 + 1/2 + 1/3 +…$$
but this does not equal the book solution of $1+1 + 1/2 + 1/3 +…$
I'm thinking my pmf is wrong or perhaps this has something to do with St Petersburg Paradox? Thank you for your help and patience.
Book solution
Best Answer
Both approaches give the same answer, though this is obscured by the fact this answer is $+\infty$ and so it seems that the book has an extra term
Let's illustrate this by limiting the game to end at a maximum of $6$. So you have a random variable which takes the value $2$ with probability $\frac12$, the value $3$ with probability $\frac16$, the value $4$ with probability $\frac1{12}$, the value $5$ with probability $\frac1{20}$ and the value $6$ with the remaining probability $\frac15$
Then you would say that the expected value was $2 \times \frac12+3 \times \frac16 + 4 \times \frac1{12}+ 5 \times \frac1{20} + 6 \times \frac1{5}= 1 +\frac12+\frac13+\frac14+\frac65$
while the book would say the expectation was $1+1+\frac12+\frac13+\frac14+\frac15$
These are clearly the same total even if the sums are slightly different at the beginning and end. They each add up to $\frac{197}{60} \approx 3.2833$