Confusion about the Hiring Problem

Question

I'm confused about where the probability from the hiring problem comes from.

For background:

We interview one person everyday who has a quality characteristic, x, from 0 to 1(distributed uniformly). We interview for n days. If on the $i^{th}$ day, person i is more qualified then all the previous candidates, then we hire that person. Find the expected number of people we hire.

We can proceed to solve the problem using linearity of expectation and the method of indicator random variables.

Let X be the number of people we hire. $$X = X_1 + X_2 + X_3 + ... + X_n$$ where $X_i = 1$ if we hire the with person and $X_i = 0$ if we don't. According to online resources, the probability that we hire the with person is $\frac{1}{i}$ since each person is equally likely to be the highest so far.

However, this doesn't make sense to me. Why doesn't the probability that we hire the $i^{th}$ person depend on the quality characteristic we've seen so far?

Take, for example, the second person: Shouldn't the $(2^{nd} \text{person hired}) =1 - n_1$ where n_1 is the quality characteristic of the first person?

If we use what online resources say then $P (2^{nd} \text{person hired}) = \frac{1}{2}$. But what if person one had a quality characteristic of .9, then $P(2^{nd} \text{ person hired}) = .1$ and not half.

Can someone tell me where my logic is wrong?

Answer 1

Let us denote by $x_1,\ldots,x_n$ the qualities of the $n$ persons; so the $x_i$ are iid random variables distributed uniformly over $[0,1]$.

If you know $x_1,\ldots,x_i$, then $X_i$ becomes deterministic. For example, if $x_1 = 0.3$ and $x_2 = 0.5$ then $X_2 = 1$, whereas if $x_1 = x_2 = 0.4$ and $x_3 = 0.1$ then $X_3 = 0$. If you know only some of $x_1,\ldots,x_i$, then you can calculate the distribution of $X_i$, as your example demonstrates.

None of this is needed to calculate $\mathbb{E}[X]$, however. Using linearity of expectation, we know that $$ \mathbb{E}[X] = \sum_{i=1}^n \mathbb{E}[X_i] = \sum_{i=1}^n \Pr[X_i = 1]. $$ In other words, in order to calculate the expected number of people hired, all we need to do is to calculate the probability that $X_i = 1$. This probability is $1/i$. You're right that the probability changes if we know more about the $x_j$, but so what? We are not interested in calculating $\mathbb{E}[X]$ given partial knowledge of the $x_j$. Instead, we want to calculate the expected value of $X$ when $x_1,\ldots,x_n$ are chosen uniformly at random from $[0,1]$, independently. This is the relevant distribution for calculating $\Pr[X_i = 1]$.

What might be throwing you off is the trick of using linearity of expectation. It allows us to treat the random variables $X_i$ completely independently, although the variables themselves are certainly dependent.