Indicator variables Now we see how to compute it easily,by introducing some new random variables. Define Xi 0 if candidate i has been hired otherwise "Then X=∑1Xi. Recall the linearity of expectation: E[∑1X]=∑1E[X] ·We thus have E[X]=∑1E[x]. 6
Indicator variables ◼ Now we see how to compute it easily, by introducing some new random variables. ◼ Define 𝑋𝑖 = ቊ 1 if candidate 𝑖 has been hired 0 otherwise . ◼ Then 𝑋 = σ𝑖=1 𝑛 𝑋𝑖 . ◼ Recall the linearity of expectation: 𝐄 σ𝑖=1 𝑛 𝑋𝑖 = σ𝑖=1 𝑛 𝐄 𝑋𝑖 ◼ We thus have 𝐄 𝑋 = σ𝑖=1 𝑛 𝐄 𝑋𝑖 . 6
Analysis continued What is EXi? Recall Xi=0 1 if candidate i has been hired otherwise Thus E[Xi]Pr[Xi=1]=1/i. 0( Candidate i was hired iff she is the best among the first i candidates. ■ So E[X]=1E[Xi]=11/i In(n). ■ The average cost is In(n).c
Analysis continued ◼ What is 𝐄 𝑋𝑖 ? ◼ Recall 𝑋𝑖 = ቊ 1 if candidate 𝑖 has been hired 0 otherwise . ◼ Thus 𝐄 𝑋𝑖 = 𝐏𝐫 𝑋𝑖 = 1 = 1/𝑖. ❑ Candidate 𝑖 was hired iff she is the best among the first 𝑖 candidates. ◼ So 𝐄 𝑋 = σ𝑖=1 𝑛 𝐄 𝑋𝑖 = σ𝑖=1 𝑛 1/𝑖 ≈ ln 𝑛 . ◼ The average cost is ln 𝑛 ⋅ 𝑐. 7
Another strategy A more natural scenario is that we only hire once. And of course,we hope to hire the best one. But the candidates on the market also get other offers.So we need to issue offer fast. Interview one candidate each day,and decide acceptance/rejection immediately. The candidates come in a random order. 8
Another strategy ◼ A more natural scenario is that we only hire once. ◼ And of course, we hope to hire the best one. ◼ But the candidates on the market also get other offers. So we need to issue offer fast. ◼ Interview one candidate each day, and decide acceptance/rejection immediately. ◼ The candidates come in a random order. 8
Strategy Reject the first k candidates no matter how good they are. Because there may be better ones later. After this,hire the first one who is better than all the first k candidates. If all the rest n-k are worse than the best one among the first k,then hire the last one
Strategy ◼ Reject the first 𝑘 candidates no matter how good they are. ❑ Because there may be better ones later. ◼ After this, hire the first one who is better than all the first 𝑘 candidates. ◼ If all the rest 𝑛 − 𝑘 are worse than the best one among the first 𝑘, then hire the last one. 9
Pseudo-code best score =0 ■fori=1tok if score(i)>best_score best_scorescore(i) for i=k+1 to n if score(i)best_score return(i) return n 10
Pseudo-code ◼ 𝑏𝑒𝑠𝑡_𝑠𝑐𝑜𝑟𝑒 = 0 ◼ for 𝑖 = 1 to 𝑘 if 𝑠𝑐𝑜𝑟𝑒(𝑖) > 𝑏𝑒𝑠𝑡_𝑠𝑐𝑜𝑟𝑒 𝑏𝑒𝑠𝑡_𝑠𝑐𝑜𝑟𝑒 = 𝑠𝑐𝑜𝑟𝑒(𝑖) for 𝑖 = 𝑘 + 1 to 𝑛 if 𝑠𝑐𝑜𝑟𝑒(𝑖) > 𝑏𝑒𝑠𝑡_𝑠𝑐𝑜𝑟𝑒 return(𝑖) return 𝑛 10