Next We want to determine,for each k,the probability that we hire the best one. And then maximize this probability over all k. Suppose we hire candidate i. i>k in the strategy (since we choose to reject the first k candidates). S:event that we hire the best one. S;:event that we hire the best one,which is candidate i. "Pr[S]=∑=k+1Pr[S]. 11
Next ◼ We want to determine, for each 𝑘, the probability that we hire the best one. ◼ And then maximize this probability over all 𝑘. ◼ Suppose we hire candidate 𝑖. ❑ 𝑖 > 𝑘 in the strategy (since we choose to reject the first 𝑘 candidates). ◼ 𝑆: event that we hire the best one. ◼ 𝑆𝑖 : event that we hire the best one, which is candidate 𝑖. ◼ 𝐏𝐫 𝑆 = σ𝑖=𝑘+1 𝑛 𝐏𝐫 𝑆𝑖 . 11
Si:candidate i is the best among the n candidates,.. probability:1/n. and candidates k +1,...,i-1 are all worse than the best one among 1,...k. so that candidates k +1,...,i-1 are not hired. probability:k/(i-1).(The best one among the first i-1 appears in the firstk.) 12
◼ 𝑆𝑖 : candidate 𝑖 is the best among the 𝑛 candidates, … ❑ probability: 1/𝑛. ◼ and candidates 𝑘 + 1, …, 𝑖 − 1 are all worse than the best one among 1, … , 𝑘. ❑ so that candidates 𝑘 + 1,…,𝑖 − 1 are not hired. ❑ probability: 𝑘/(𝑖 − 1). (The best one among the first 𝑖 − 1 appears in the first 𝑘.) 12
Putting together k ·Pr[S]= 1 k 二 n i-1 n(i-1) So PrS]= 2=k+1Pr[S] k ∑=k+1ni-5 = (k/n)Σ(1/) (k/n)(In(n -1)-In(k)). Maximize this over all k e {1,...,n}we get k=n/e≈0.368.n take derivative with respect to k,and set it equal to 0. And the success probability is 1/e 0.368. 13
Putting together ◼ 𝐏𝐫 𝑆𝑖 = 1 𝑛 ⋅ 𝑘 𝑖−1 = 𝑘 𝑛(𝑖−1) . ◼ So 𝐏𝐫 𝑆 = σ𝑖=𝑘+1 𝑛 𝐏𝐫 𝑆𝑖 = σ𝑖=𝑘+1 𝑛 𝑘 𝑛(𝑖−1) = (𝑘/𝑛) σ𝑖=𝑘 𝑛−1 (1/𝑖) ≈ (𝑘/𝑛) ln 𝑛 − 1 − ln 𝑘 . ◼ Maximize this over all 𝑘 ∈ {1, … , 𝑛} we get 𝑘 = 𝑛/𝑒 ≈ 0.368 ⋅ 𝑛 ❑ take derivative with respect to 𝑘, and set it equal to 0. ◼ And the success probability is 1/𝑒 ≈ 0.368. 13
Summary for the Secretary problem In the first strategy (always hire a better one) we hire around In(n)times (in expectation) In the second strategy (hire only once)we hire the best with probability 0.368 Reject the first k =0.368.n candidates oAnd in the rest hire the first one who beats all the first k ones. 14
Summary for the Secretary problem ◼ In the first strategy (always hire a better one) we hire around ln(𝑛) times (in expectation). ◼ In the second strategy (hire only once) we hire the best with probability ≈ 0.368. ❑ Reject the first 𝑘 = 0.368 ⋅ 𝑛 candidates ❑ And in the rest hire the first one who beats all the first 𝑘 ones. 14