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