Strategies in the secretary problem (Q1329670)

The article begins with an anecdotal, early history of one of the original, sequential, optimal stopping problems, known among other names, as the ``Secretary Problem''. A given number \(n\) of items each numbered with distinct integers (positive or negative) is drawn, sequentially, from a container. The object is to devise a ``strategy'' that provides the best chance of recognizing the largest integer as it is drawn from the container. The original proof is given that rejecting the first (approximately) \(n/e\) items and choosing the next larger one drawn (should there be one) yields a win ``\(1/e\)'' of the time. A discussion of the meaning of ``strategy'' follows, and careful proofs are given that the strategy just described is optimal in each of two classes of ``rational'' strategies, one restricted, the position strategies, and one very broad, the deterministic strategies.