Uncertainty and Probability Secretary Problem

Classic Secretary Problem

only interested in the best applicant

introduceYn= 1 if applicantnbeats all previous applicants, else 0

by uniform probability, the (Yn) are independent and

P[Yn= 1] = 1/n.

show that optimal rules must be simple, i.e. of the form

τr= inf{k≥r:Yk= 1}

success of ruleτris

r− 1

N

∑N

n=r

1

n− 1

≈r−^1

N

log N

r− 1

optimum inNe+ 1