Secretary Problem 2

Calculus Level 5

Imagine an administrator who wants to hire the best secretary out of n n to-be-ranked applicants for the position. The applicants are interviewed one by one in random order. A decision about each particular applicant is to be made immediately after the interview. Once rejected, an applicant cannot be recalled. During the interview, the administrator can rank the applicant among all applicants interviewed up to that time, but is unaware of the quality of yet unseen applicants. The question is about the optimal strategy (stopping rule) to maximize the probability of selecting the best applicant.

If you think carefully, it might seem obvious that one cannot select the first candidate because the first candidate has no one to compare with. A better strategy is always rejecting the first few applicants interviewed as samples to compare against and then stopping at the first applicant who is better than every applicant interviewed till then (or continuing to the last applicant if this never occurs).

If r ( n ) r(n) is the optimal sample size, find lim ⁡ n → ∞ n r ( n ) . \displaystyle\lim_{n\to\infty}\frac n{r(n)}.

Try this problem first.


The answer is 2.71828.

Brian Lie by Brian Lie , 26, China

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Brian Lie
Oct 21, 2018

When sample size is r r , the probability of selecting the best applicant is

p r , n = ∑ j = r + 1 n P ( j th applicant is best and the administrator selects it ) = ∑ j = r + 1 n P ( j th applicant is best ) P ( the administrator selects j th applicant ∣ j th applicant is best ) = ∑ j = r + 1 n P ( j th applicant is best ) P ( the best of the first j − 1 applicants is in the first r applicants ) = ∑ j = r + 1 n ( 1 n ) ( r j − 1 ) = ( r n ) ∑ j = r + 1 n 1 j − 1 \begin{aligned} p_{r,n}&=\sum_{j=r+1}^nP(j^\text{th}\text{ applicant is best and the administrator selects it}) \\&=\sum_{j=r+1}^nP(j^\text{th}\text{ applicant is best})\,P(\text{the administrator selects }j^\text{th }\text{applicant}\,|\,j^\text{th}\text{ applicant is best}) \\&=\sum_{j=r+1}^nP(j^\text{th}\text{ applicant is best})\,P(\text{the best of the first }j-1\text{ applicants is in the first }r\text{ applicants}) \\&=\sum_{j=r+1}^n\left(\frac 1n\right)\left(\frac r{j-1}\right) \\&=\left(\frac rn\right)\sum_{j=r+1}^n\frac 1{j-1} \end{aligned}

Let r n = x \frac rn=x , we get

p ( x ) = lim ⁡ n → ∞ p r , n = lim ⁡ n → ∞ ( r n ) ∑ j = r + 1 n ( 1 j − 1 n ) ( 1 n ) = x ∫ x 1 ( 1 t ) d t = − x ln ⁡ x p ′ ( x ) = − ( 1 + ln ⁡ x ) \begin{aligned} p(x)&=\lim_{n\to\infty}p_{r,n} \\&=\lim_{n\to\infty}\left(\frac rn\right)\sum_{j=r+1}^n\left(\frac 1{\frac {j-1}n}\right)\left(\frac 1n\right) \\&=x\int_x^1\left(\frac 1t\right)dt \\&=-x\ln x \\p'(x)&=-(1+\ln x) \end{aligned}

Therefore, p ( x ) p(x) has a maximum value when p ′ ( x ) = 0 p'(x)=0 , that is x = 1 e x=\frac 1e making the answer lim ⁡ n → ∞ n r ( n ) = e . \lim_{n\to\infty}\frac n{r(n)}=\boxed e.

3 Helpful 0 Interesting 0 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...