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?

  • $\begingroup$ It is correct that "if person one had a quality characteristic of .9, then $P(2^{nd} \text{ person hired}) = .1"$. However, what if person one had a quality characteristic of .1 or .2 or .8 or else? What we are interested is the "average" probability of the second person get hired. (We call that "average" probability the expectation of that probability.) $\endgroup$ – John L. Jun 24 '20 at 16:48

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.

  • 1
    $\begingroup$ Hmmm. Interesting, why can we treat random variables independently when we use linearity of expectation. I've learned about it before, but the fact that we can treat them independently has never come up... $\endgroup$ – Matthew Engelstein Jun 22 '20 at 23:18
  • $\begingroup$ That’s the magic of linearity of expectation. Note that I use the word “independent” here in the non-technical sense. The variables are still independent, but you look at them one at a time, separately from all others. $\endgroup$ – Yuval Filmus Jun 23 '20 at 6:02

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.