# Knowing When to Stop  URL:: https://www.americanscientist.org/article/knowing-when-to-stop Author:: American Scientist ## AI-Generated Summary None ## Highlights > The history of optimal-stopping problems, a subfield of probability theory, also begins with gambling. One of the earliest discoveries is credited to the eminent English mathematician Arthur Cayley of the University of Cambridge. In 1875, he found an optimal stopping strategy for purchasing lottery tickets. ([View Highlight](https://read.readwise.io/read/01hnap4tcsj8tywkn108tvn0zy)) > Shortly after the war, Richard Bellman, an applied mathematician, invented dynamic programming to obtain optimal strategies for many other stopping problems. ([View Highlight](https://read.readwise.io/read/01hnap52a7dwkjmvt89zmdy2jp)) > Observe only 37 cards (or potential partners) without stopping and then stop with the next record. John Gilbert and Frederick Mosteller of Harvard University proved that this strategy is best and guarantees stopping with the best number about 37 percent of the time. ([View Highlight](https://read.readwise.io/read/01hnap8e5zr7bd647r11jkcdng)) > (Note that the “observe half the numbers” strategy clearly wins with probability at least ¼, also independent of the number of cards.) ([View Highlight](https://read.readwise.io/read/01hnap8m7ppvmybdhff6d3hqzw)) > The case of partial information is the most difficult. Usually one does not know how many applicants there will be for a job, nor the exact probabilities of future stock values. In these situations, one method of solution is to use tools from the theory of zero-sum, two-person games, where the stopping problem can be thought of as a decision maker playing against an opponent (often called Nature or God) who may assign the values and probabilities in any way she chooses. ([View Highlight](https://read.readwise.io/read/01hnapbz97gwentw3cqwc775hb)) > Ulrich Krengel of the University of Göttingen and I used this technique to discover the optimal strategy in the so-called marriage problem where only a bound on the number of applicants is known. As a concrete example, consider the problem where the objective is to select the highest number from a hat containing at least one, and at most five, numbered cards (if you do not stop and there are no cards left, you lose.) We proved that the optimal strategy in this case is to stop with the first card with probability 26/75 (which you may do using a random number generator or other method). If you do not stop with the first card, then you should continue to the second card, if there is one. If the second card’s number is higher than the first card’s number, stop with probability 26/49. Otherwise, continue, stopping with the first record thereafter (or when you run out of cards or are forced to choose the number on the fifth card). This guarantees a probability of 26/75 of stopping with the highest number, no matter how many cards Nature deposited in the hat. > There is no better strategy. We found the exact formulas and strategies for all possible bounds on the maximum number of cards and the winning probabilities are surprisingly high. For example, even if you only know that there are somewhere between 1 and 100 cards in the hat, it is still possible to win about 20 percent of the time. Exactly the same method can be employed to obtain optimal stopping rules in many real-life problems such as a situation where an employer wants to hire the very best salesperson available, and knows the maximum number of candidates available for the position, but does not know how many have already accepted other jobs. ([View Highlight](https://read.readwise.io/read/01hnapmwsvafdpz5ezkq5v60bm))