Secretary Problem with rank based selection and cardinal payoff

Question

Background:
The cardinal payoff variant of the Secretary problem aims to maximize the expected value of the selected applicant, assuming values of applicants are random variables X drawn i.i.d. from a uniform distribution on [0, 1].

Refer the paper for details: New Secretary Problem

While determining the expected value/payoff of the selected applicant after applying some cutoff c, the expected value is expressed in the form of a recurrence (pg3 of the aforementioned paper) :

Question : In this recurrence formula, the first term denotes the case if (t)th applicant is the best so far and the second term
=(Probability that (t)th applicant is not the best so far)* V(t+1)
= (1/t) * V(t+1)
= (1/t)* {1/(t+1)}* E(t+1) + (1/t)* {1- 1/(t+1)}* V(t+2)
where the first term denotes the case of (t+1)th applicant being the best so far.

How would the probability of this ((t+1)th applicant being the best so far) be (1/t)* {1/(t+1)} ? Shouldn't it be
= (1/t)* (1/t)
= (Probability that (t)th applicant is not the best among the first t applicants)* (Probability that (t+1)th applicant is the best so far, given (t)th applicant was not the best among first t applicants) ?

Answer 1

First of all, your link is dead. However, that's not a problem, as far as answering the question goes.

We have \begin{align}V_n(t) &= \frac{1}{t}\mathbb{E}(X_t) + \frac{t-1}{t}V_n(t+1)\\ &= \frac{1}{t}\mathbb{E}(X_t) + \frac{t-1}{t}\bigg(\frac{1}{t+1}\mathbb{E}(X_{t+1}) + \frac{t}{t+1}V_n(t+2)\bigg). \end{align}

Now, the first term inside the bracket says exactly what you think it should say: \begin{align}&\big(\text{probability that $X_t$ isn't the maximum in $\{X_1,...,X_t\}$}\big)\\ \times &\big(\text{probaility that $X_{t+1}$ is the maximum in $\{X_1,...,X_{t+1}\}$}\big)\\ = &\frac{t-1}{t}\cdot \frac{1}{t+1}\mathbb{E}(X_{t+1}). \end{align}

Answer 2

From your last line, it seems that you thought that the probability that the $(t+1)$-th applicant is the best so far, given that the $t$-th applicant was not the best among the first $t$ applicants, should be $\frac1t$ and not $\frac1{t+1}$. I’m guessing that you arrived at this conclusion along these lines: If the $t$-th applicant wasn’t the best among the first $t$ applicants, she can’t be the best so far (that is, among the first $t+1$ applicants). That only leaves $t$ applicants, all of which are equally likely to be the best so far; so the probability that the $(t+1)$-th applicant (who is one of these $t$) is the best so far is $\frac1t$.

The flaw in this reasoning is that the probability $\frac1{t+1}$ for the $(t+1)$-th applicant to be the best so far doesn’t derive from equiprobability of the $t+1$ applicants being the best so far, but from equiprobability of the $t+1$ ranks that the $(t+1)$-th applicant could have among the first $t+1$ applicants. What we know about the relative order of the first $t$ applicants among themselves is entirely irrelevant. Even if we already knew, for some reason, that the first $t$ applicants appeared in order of increasing value, so that only the last of them could potentially be the best so far, the probability for the $(t+1)$-th applicant to be the best so far would still be $\frac1{t+1}$ because she would still have equal probability to have any of the $t+1$ ranks among the first $t+1$ applicants. It might strengthen your intuition about this to imagine first meeting the first $t$ applicants, then thinking about the probability of the next one being the best so far, then being told that the first $t$ appeared in order, and then thinking about the same probability again. It would be weird if that probability jumped from $\frac1{t+1}$ to $\frac12$ simply because someone told you the order in which the other applicants appeared.

(As an aside, if you'd been right that knowing that previous applicants weren’t the best up to that point increases the probability for the current applicant to be the best so far, things would be more complicated than you described, because in that case it would have been necessary to also take into account our knowledge about all earlier applicants, not just about the $t$-th applicant.)