Uncertainty and Probability Optimal Stopping

Two classics

The Parking Problem

You drive along a road towards a theatre

You want to park as close as possible to the theatre

Parking spaces are free iid with probabilityp> 0

When is the right time to stop? take the first free after 68%1/p

distance

Secretary Problem = When to Marry?

You see sequentiallyNapplicants

maximize the probability to get the best one

rejected applicants do not come back

applicants come in random (uniform) order

optimal rule: take the first candidate (better than all previous) after

seeing 1/eof all applicants

probability of getting the best one approx. 1/e