Suppose that you need to hire a new office assistant. Your previous attempts at hiring have been unsuccessful, and you decide to use an employment agency. The employment agency sends you one candidate each day. You interview that person and then decide either to hire that person or not. You must pay the employment agency a small fee to interview an applicant. To actually hire an applicant is more costly, however, since you must fire your current office assistant and pay a substan- tial hiring fee to the employment agency. You are committed to having, at all times, the best possible person for the job. Therefore, you decide that, after interviewing each applicant, if that applicant is better qualified than the current office assistant, you will fire the current office assistant and hire the new applicant. You are willing to pay the resulting price of this strategy, but you wish to estimate what that price will be.

HIRE-ASSISTANT(n)
1  best = 0    //candidate 0 is a least-qualified dummy candidate
2  for i = 0 to n
3    do interview candidate i
4       if candidate i is better than candidate best
5          then best = i
6               hire candidate i

For us hiring is much more costly than interview. So we interview everybody. Candidate i has probability of 1/i being the better than the previous 1..i-1 employees we have interviewed.

E[Xi] = 1/i