Question

Please answer parts d e and f. The answers to the rest have been answered repeatedly here and no one completes the problem. Thank you.

To get information about the quality of the applicant pool, you pick a number 0 <r <n, and you callously) interview the first r candidates without intending to hire any of them. • Beginning with the next candidate (r +1), you continue interviewing until the current candi- date is the best you've seen so far, at which point you stop the interviewing process and hire that candidate. • If none of the candidates from (r + 1) to n is best, you just throw up your hands and hire candidate n. The goals in this problem are twofold: to compute the probability that you hire the best candidate with this strategy, and to chooser to maximize this probability. Let A = (you hire the best candidate) and B; = (the best candidate is person i in the interviewing sequence). (a) For any i>r, show that the probability that {the best candidate among the first i people interviewed is one of the first r people} is : (10 points) (b) Explain why P(AB) = () for i <r, and (hard) show that P(AB;) = " for i > r. (Hint: it helps to define the cvents C = (you keep intcrvicwing until you scc candidate i).) (15 points) (c) Having specificd a value of r before intcrvicwing begins, let pr = P(A) with the chosen r valuc, and show that (i) po = 1, and (ii) for 0 <r<n, Pr = n Lier+1 -1 LIN 1. (Hint: Use the results from part (b).) 172 (15 points) (d) On the way to finding the optimal value of r, define qr = (Pr - pr-1) for r = 1,..., (n - 1) and show that qr is a strictly decreasing function of r for r > 0. (15 points) (e) Use (d) to show that the value of r that maximizes p, is the largest r such that qr >0. (Hint: For r > 0, from the definition of qr, it helps to write pr = po + -1 9i.) (10 points] (f) Use (e) to find the best value of r when n = 10 and the resulting optimal value of pr. Does the adaptive hiring strategy examined in this problem look good to you? Explain briefly. (15 points) (Remarkable fact (not part of what you're asked to show in this problem), for those of you who like to think about math: it turns out, weirdly, that for 0 <r <n, hertu = v(n) - V(r), where V(x) 4. In T(x) is the digamma function.)

Answer 1

d) Observe that

(pr Pr-1) n 1 1 r - i 1 i- 1 i=r+1 n 1 1 + i 1 - 1 n i-r+1 n 1 X n r1 i 1

Therefore,

1 1 1 2 7 2=r-1 X 2 1 1] 2 1 1 1 < 0 n(r 1 1 7 X X X

Hence q_r is a strictly decreasing function of r for r > 0.

e) Observe that if p_r is maximized at r, then,

i>0 Vi < >Pi-1 Vi <r

Hence, the result follows.

f) The following table gives us the value of q_r at r:

r	q
2	0.0828968254
3	0.0328968254
4	-0.0004365079365
5	-0.02543650794
6	-0.04543650794
7	-0.0621031746
8	-0.07638888889
9	-0.08888888889
10	-0.1

Hence the maximum for p_r occurs at r = 3 and the value of the maximum is 0.398