Imagine you’re hiring a new secretary. One hundred candidates will line up for interviews, arriving one by one in random order. After each interview, you must make a decision immediately: hire this candidate on the spot or reject them forever and move on. You cannot recall someone you rejected. The challenge? You want to maximize the probability of hiring the very best candidate.
This fascinating puzzle is known as the Secretary Problem, also called the Marriage Problem or the Sequential Hiring Decision Problem. It blends probability, decision theory, and even philosophy about decision-making in life.
(more…)