Secretary problem
Encyclopedia
The secretary problem is one of many names for a famous problem of the
optimal stopping
theory.
The problem has been studied extensively in the fields of
applied probability
, statistics
, and decision theory
. It is also known as the marriage problem, the sultan's dowry problem, the fussy suitor problem, the googol game, and the best choice problem.
The basic form of the problem is the following.
Imagine an administrator willing to hire the best secretary out of
rankable applicants for a position. The applicants are interviewed one-by-one
in random order. A decision about each particular applicant is to be taken immediately after the interview. Once rejected, an applicant cannot be recalled.
During the interview, the administrator can rank the applicant among all applicants interviewed so far, but is unaware of the quality of yet unseen applicants. The question is about the optimal strategy (stopping rule
) to maximize the probability of selecting the best applicant.
The problem has a strikingly elegant solution. The optimal stopping rule prescribes to reject about
applicants after the interview (where e is the base of the natural logarithm
) without choice then stop at the first applicant who is better than every applicant interviewed so far (or proceed to the last applicant if this never occurs). Sometimes this strategy is called the
stopping rule, because the probability to stop at the best applicant with this strategy is about 
already for moderate values of
.
One reason why the secretary problem has received so much attention is that the optimal policy for the problem (the stopping rule) is simple, and selects the single best candidate about 37% of the time, no matter for searching through 100 or 100,000,000 applicants.
In fact, for every
the probability of best choice with the optimal policy
is at least
.
Because there are so many variations of the problem, the formulation will be re-stated once more:
This is the same as maximizing the expected payoff, with payoff defined to be one for the best applicant and zero otherwise.
Terminology: A candidate is an applicant who, when interviewed, is better than all the applicants interviewed previously. Skip is used to mean "reject immediately after the interview".
Clearly, since the objective in the problem is to select the single best applicant, only candidates will be considered for acceptance. The "candidate" in this context corresponds to the concept of record in permutation.
.
Under it, the interviewer rejects the first r − 1 applicants
(let applicant M be the best applicant among these r − 1 applicants), and then selects the first subsequent applicant that is better than applicant M.
It can be shown that the optimal strategy lies in this class of strategies.
For an arbitrary cutoff r, the probability that the best applicant is selected is
This sum is obtained by noting that if applicant i is the best applicant, then it is selected if and only if the best applicant among the first i − 1 applicants is among the first r − 1 applicants that were rejected.
Letting n tend to infinity, writing
as the limit of r/n, using t for i/n and dt for 1/n, the sum can be approximated by the integral
Taking the derivative of P(x) with respect to
, setting it to 0, and solving for x, we find that the optimal x is equal to 1/e. Thus, the optimal cutoff tends to n/e as n increases, and the best applicant is selected with probability 1/e.
For small values of n, the optimal r can also be obtained by standard dynamic programming
methods. The optimal thresholds r and probability of selecting the best alternative P for several values of n are shown in the following table.
Note that the probability of selecting the best alternative in the classical secretary problem converges toward
.
in a straightforward manner by the Odds algorithm
(2000) which also allows
for other applications. Modifications for the secretary problem which can be solved by this algorithm include random availabilities of applicants, more general hypotheses for applicants to be of interest to the decision maker, group interviews for applicants, as well as certain models for a random number of applicants. None of these modifications are treated in this article.
is that the number of applicants
must be known in advance. One way to overcome this problem is to suppose that the number of applicants is a random variable 
with a known distribution of 
(Presman and Sonin, 1972). For this model, the optimal solution is in general much harder, however. Moreover, the optimal success probability is now no longer around 1/e. Indeed, it is intuitive that there should be a price to
pay for not knowing the number of applicants. However, in this model the price is high. Depending on the choice of the distribution of
the optimal win probability is typically much lower than 1/e, and may even approach zero. This reduces the interest of this model for applications. Looking for ways
to cope with this new problem led to the following approach and result:
Unified approach(1984):
The model: An applicant must be selected
on some time interval
from an unknown number 
of rankable applicants.
The goal is to maximize the probability of selecting online the best under the hypothesis that all arrival orders of different ranks are equally likely. Suppose that all applicants have independently of each other the same arrival time density
on
and let 
denote the corresponding arrival time distribution function, that is
1/e-law: Let
be such that 
Consider the strategy to wait and observe all applicants up to time 
and then to select, if possible, the first candidate after time 
which is better than all preceding ones. Then this strategy, called 1/e-strategy, has the following properties:
The 1/e-strategy
yields for all
a success probability of at least 1/e,
is the unique strategy guaranteeing this lower success probability bound 1/e, and the bound is optimal,
selects, if there is at least one applicant, none at all with probability exactly 1/e.
When the 1/e-law was discovered in 1984 it came as a surprise.
The reason was that a value of about 1/e had been considered
before as being out of reach in a model for unknown
, whereas now this value was achieved as a lower bound, and this in a model with arguably weaker hypotheses (see e.g. Math. Reviews 85:m).
This law is sometimes confused with the solution for the secretary problem because of the similar role of the number 1/e. Note however, that in the 1/e-law, this role is stronger and more general. The result is also stronger, since it holds for an unknown number of applicants and since the model is more tractable for applications.
the Secretary Problem appeared for the first time in print in Martin Gardner
's column of Scientific American in 1960. Here is how Martin Gardner formulated the problem:
"Ask someone to take as many slips of paper as he pleases,
and on each slip write a different positive number. The numbers may range from small fractions of
1 to a number the size of a googol
(1 followed by a hundred 0's) or even larger. These slips are turned face down and shuffled
over the top of a table. One at a time you turn the slips face up.
The aim is to stop turning when you come to the number that; you
guess to be the largest of the series. You cannot go back and pick
a previously turned slip. If you turn over all the slips, then of
course you must pick the last one turned."
In the paper "Who solved the Secretary problem?"
pointed out that the Secretary Problem remained unsolved as it was stated by M. Gardner,
that is as a two-person zero-sum game with two antagonistic players.
In this game Alice, the informed player,
writes secretly distinct numbers on
cards.
Bob, the stopping player, observes the actual values and can stop turning cards
whenever he wants, winning if the last card turned has the overall maximum number.
The difference with the basic Secretary Problem is that Bob observes the actual values written on
the cards which he can use in his decision procedures. The numbers on cards are analogous
to the numerical qualities of applicants in some versions of the Secretary Problem.
The joint probability distribution of the numbers
is under the control of Alice.
Bob wants to guess the maximum number
with highest possible probability, while Alice' goal it to keep this probability as low as possible.
It is not optimal for Alice to sample the numbers independently from some fixed distribution,
and she can play better by choosing random numbers in some dependent way.
For
Alice has no minimax strategy,
which is closely related to a paradox of T. Cover.
But for
the game has a solution:
Alice can choose random numbers (which are dependent random variables)
in such a way that Bob cannot play better than using the classical stopping strategy based on the relative ranks
.
derived the expected success probabilities for several psychologically plausible heuristics that might be employed in the secretary problem. The heuristics they examined were:
Note that each heuristic has a single parameter y. The figure (shown on right) displays the expected success probabilities for each heuristic as a function of y for problems with n = 80.
To model this problem, suppose that the
applicants have "true" values that are random variable
s X drawn i.i.d. from a uniform distribution
on [0, 1]. Similar to the classical problem described above, the interviewer only observes whether each applicant is the best so far (a candidate), must accept or reject each on the spot, and must accept the last one if he is reached. (To be clear, the interviewer does not learn the actual relative rank of each applicant. He learns only whether the applicant has relative rank 1.) However, in this version his payoff is given by the true value of the selected applicant. For example, if he selects an applicant whose true value is 0.8, then he will earn 0.8. The interviewer's objective is to maximize the expected value of the selected applicant.
Since the applicant's values are i.i.d. draws from a uniform distribution on [0, 1], the expected value
of the tth applicant given that
is
given by
As in the classical problem, the optimal policy is given by a threshold, which for this problem we will denote by
, at which the interviewer should begin accepting candidates. showed that c is either 
or 
. (In fact, whichever is closest to 
.) This follows from the fact that given a problem with 
applicants, the expected payoff for some arbitrary threshold 1 = c = n is
Differentiating
with respect to c, one gets
Since
for all permissible
values of
, we find that 
is maximized at 
. Since V is convex in 
, the optimal integer-valued threshold must be either 
or 
. Thus, for most values of 
the interviewer will begin accepting applicants sooner in the cardinal payoff version than in the classical version where the objective is to select the single best applicant. Note that this is not an asymptotic result: It holds for all 
.
and experimental economists
have studied the decision behavior of actual people in secretary problems. In large part, this work has shown that people tend to stop searching too soon. This may be explained, at least in part, by the cost of evaluating candidates. Extrapolating to real world settings, this might suggest that people do not search enough whenever they are faced with problems where the decision alternatives are encountered sequentially. For example, when trying to decide at which gas station to stop for gas, people might not search enough before stopping. If true, then they would tend to pay more for gas than they might had they searched longer. The same may be true when people search online for airline tickets, say. Experimental research on problems such as the secretary problem is sometimes referred to as behavioral operations research
.
in a lecture he gave that year. He referred to it several times during the 1950s, for example in a conference talk
at Purdue on 9 May 1958, and it eventually became widely known in the folklore although nothing was
published at the time. In 1958 he sent a letter to Leonard Gilman, with copies to a dozen friends including S. Karlin
and J. Robbins, outlining a proof of the optimum strategy,
with an appendix by R. Palermo who proved that all strategies are dominated by a strategy of the
form "reject the first p unconditionally, then accept the next candidate". (See Flood (1958).)
The first publication was apparently by Martin Gardner
in Scientific American, February 1960. He had heard
about it from John H. Fox, Jr., and L. Gerald Marnie, who had independently come up with an equivalent
problem in 1958; they called it the "game of Googol". Fox and Marnie did not know the optimum solution;
Gardner asked for advice from Leo Moser
, who (together with J. R. Pounder) provided a correct analysis for publication in the magazine. Soon afterwards, several mathematicians wrote to Gardner to tell him about the equivalent problem they had heard via the grapevine, all of which can most likely be traced to Flood's original work.
The 1/e-law is due to F. Thomas Bruss (1984)
A 1989 paper by T. S. Ferguson has an extensive bibliography, and points out that a similar (but
different) problem had been considered by Arthur Cayley
in 1875 and even by Johannes Kepler
long before that.
optimal stopping
Optimal stopping
In mathematics, the theory of optimal stopping is concerned with the problem of choosing a time to take a particular action, in order to maximise an expected reward or minimise an expected cost. Optimal stopping problems can be found in areas of statistics, economics, and mathematical finance...
theory.
The problem has been studied extensively in the fields of
applied probability
Applied probability
Much research involving probability is done under the auspices of applied probability, the application of probability theory to other scientific and engineering domains...
, statistics
Statistics
Statistics is the study of the collection, organization, analysis, and interpretation of data. It deals with all aspects of this, including the planning of data collection in terms of the design of surveys and experiments....
, and decision theory
Decision theory
Decision theory in economics, psychology, philosophy, mathematics, and statistics is concerned with identifying the values, uncertainties and other issues relevant in a given decision, its rationality, and the resulting optimal decision...
. It is also known as the marriage problem, the sultan's dowry problem, the fussy suitor problem, the googol game, and the best choice problem.
The basic form of the problem is the following.
Imagine an administrator willing to hire the best secretary out of
rankable applicants for a position. The applicants are interviewed one-by-onein random order. A decision about each particular applicant is to be taken immediately after the interview. Once rejected, an applicant cannot be recalled.
During the interview, the administrator can rank the applicant among all applicants interviewed so far, but is unaware of the quality of yet unseen applicants. The question is about the optimal strategy (stopping rule
Stopping rule
In probability theory, in particular in the study of stochastic processes, a stopping time is a specific type of “random time”....
) to maximize the probability of selecting the best applicant.
The problem has a strikingly elegant solution. The optimal stopping rule prescribes to reject about
applicants after the interview (where e is the base of the natural logarithmE (mathematical constant)
The mathematical constant ' is the unique real number such that the value of the derivative of the function at the point is equal to 1. The function so defined is called the exponential function, and its inverse is the natural logarithm, or logarithm to base...
) without choice then stop at the first applicant who is better than every applicant interviewed so far (or proceed to the last applicant if this never occurs). Sometimes this strategy is called the
stopping rule, because the probability to stop at the best applicant with this strategy is about already for moderate values of
.One reason why the secretary problem has received so much attention is that the optimal policy for the problem (the stopping rule) is simple, and selects the single best candidate about 37% of the time, no matter for searching through 100 or 100,000,000 applicants.
In fact, for every
the probability of best choice with the optimal policyis at least
.Because there are so many variations of the problem, the formulation will be re-stated once more:
- There is a single secretarial position to fill.
- There are n applicants for the position, and the value of n is known.
- The applicants, if seen altogether, can be ranked from best to worst unambiguously.
- The applicants are interviewed sequentially in random order, with each order being equally likely.
- Immediately after an interview, the interviewed applicant is either accepted or rejected, and the decision is irrevocable.
- The decision to accept or reject an applicant can be based only on the relative ranks of the applicants interviewed so far.
- The objective is to select the best applicant with the highest possible probability.
This is the same as maximizing the expected payoff, with payoff defined to be one for the best applicant and zero otherwise.
Terminology: A candidate is an applicant who, when interviewed, is better than all the applicants interviewed previously. Skip is used to mean "reject immediately after the interview".
Clearly, since the objective in the problem is to select the single best applicant, only candidates will be considered for acceptance. The "candidate" in this context corresponds to the concept of record in permutation.
Deriving the optimal policy
The optimal policy for the problem is a stopping ruleStopping rule
In probability theory, in particular in the study of stochastic processes, a stopping time is a specific type of “random time”....
.
Under it, the interviewer rejects the first r − 1 applicants
(let applicant M be the best applicant among these r − 1 applicants), and then selects the first subsequent applicant that is better than applicant M.
It can be shown that the optimal strategy lies in this class of strategies.
For an arbitrary cutoff r, the probability that the best applicant is selected is
This sum is obtained by noting that if applicant i is the best applicant, then it is selected if and only if the best applicant among the first i − 1 applicants is among the first r − 1 applicants that were rejected.
Letting n tend to infinity, writing
as the limit of r/n, using t for i/n and dt for 1/n, the sum can be approximated by the integralTaking the derivative of P(x) with respect to
, setting it to 0, and solving for x, we find that the optimal x is equal to 1/e. Thus, the optimal cutoff tends to n/e as n increases, and the best applicant is selected with probability 1/e.For small values of n, the optimal r can also be obtained by standard dynamic programming
Dynamic programming
In mathematics and computer science, dynamic programming is a method for solving complex problems by breaking them down into simpler subproblems. It is applicable to problems exhibiting the properties of overlapping subproblems which are only slightly smaller and optimal substructure...
methods. The optimal thresholds r and probability of selecting the best alternative P for several values of n are shown in the following table.
 |
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
 |
1 | 1 | 2 | 2 | 3 | 3 | 3 | 4 | 4 |
 |
1.000 | 0.500 | 0.500 | 0.458 | 0.433 | 0.428 | 0.414 | 0.410 | 0.406 |
Note that the probability of selecting the best alternative in the classical secretary problem converges toward
.Alternative solution
This problem and several modifications can be solved (including the proof of optimality)in a straightforward manner by the Odds algorithm
Odds algorithm
The odds-algorithm is a mathematical method for computing optimalstrategies for a class of problems that belong to the domain of optimal stopping problems. Their solution follows from the odds-strategy, and the importance of the...
(2000) which also allows
for other applications. Modifications for the secretary problem which can be solved by this algorithm include random availabilities of applicants, more general hypotheses for applicants to be of interest to the decision maker, group interviews for applicants, as well as certain models for a random number of applicants. None of these modifications are treated in this article.
Unknown number of applicants
A major drawback for applications of the solution of the classical secretary problemis that the number of applicants
must be known in advance. One way to overcome this problem is to suppose that the number of applicants is a random variable with a known distribution of (Presman and Sonin, 1972). For this model, the optimal solution is in general much harder, however. Moreover, the optimal success probability is now no longer around 1/e. Indeed, it is intuitive that there should be a price topay for not knowing the number of applicants. However, in this model the price is high. Depending on the choice of the distribution of
the optimal win probability is typically much lower than 1/e, and may even approach zero. This reduces the interest of this model for applications. Looking for waysto cope with this new problem led to the following approach and result:
1/e-law of best choice
The essence of the model is based on the idea that real-world problems pose themselves in real time and that it is easier to estimate times in which specific events (arrivals of applicants) should occur more likely (if they do) than to estimate the distribution of the number of specific events which will occur. This idea lead to the following approach, the so-calledUnified approach(1984):
The model: An applicant must be selected
on some time interval
from an unknown number of rankable applicants.The goal is to maximize the probability of selecting online the best under the hypothesis that all arrival orders of different ranks are equally likely. Suppose that all applicants have independently of each other the same arrival time density
on and let denote the corresponding arrival time distribution function, that is-
, 
.
1/e-law: Let
be such that Consider the strategy to wait and observe all applicants up to time and then to select, if possible, the first candidate after time which is better than all preceding ones. Then this strategy, called 1/e-strategy, has the following properties:The 1/e-strategy
yields for all
a success probability of at least 1/e,is the unique strategy guaranteeing this lower success probability bound 1/e, and the bound is optimal,
selects, if there is at least one applicant, none at all with probability exactly 1/e.
When the 1/e-law was discovered in 1984 it came as a surprise.
The reason was that a value of about 1/e had been considered
before as being out of reach in a model for unknown
, whereas now this value was achieved as a lower bound, and this in a model with arguably weaker hypotheses (see e.g. Math. Reviews 85:m).This law is sometimes confused with the solution for the secretary problem because of the similar role of the number 1/e. Note however, that in the 1/e-law, this role is stronger and more general. The result is also stronger, since it holds for an unknown number of applicants and since the model is more tractable for applications.
The Game of Googol
According tothe Secretary Problem appeared for the first time in print in Martin Gardner
Martin Gardner
Martin Gardner was an American mathematics and science writer specializing in recreational mathematics, but with interests encompassing micromagic, stage magic, literature , philosophy, scientific skepticism, and religion...
's column of Scientific American in 1960. Here is how Martin Gardner formulated the problem:
"Ask someone to take as many slips of paper as he pleases,
and on each slip write a different positive number. The numbers may range from small fractions of
1 to a number the size of a googol
(1 followed by a hundred 0's) or even larger. These slips are turned face down and shuffled
over the top of a table. One at a time you turn the slips face up.
The aim is to stop turning when you come to the number that; you
guess to be the largest of the series. You cannot go back and pick
a previously turned slip. If you turn over all the slips, then of
course you must pick the last one turned."
In the paper "Who solved the Secretary problem?"
pointed out that the Secretary Problem remained unsolved as it was stated by M. Gardner,
that is as a two-person zero-sum game with two antagonistic players.
In this game Alice, the informed player,
writes secretly distinct numbers on
cards.Bob, the stopping player, observes the actual values and can stop turning cards
whenever he wants, winning if the last card turned has the overall maximum number.
The difference with the basic Secretary Problem is that Bob observes the actual values written on
the cards which he can use in his decision procedures. The numbers on cards are analogous
to the numerical qualities of applicants in some versions of the Secretary Problem.
The joint probability distribution of the numbers
is under the control of Alice.
Bob wants to guess the maximum number
with highest possible probability, while Alice' goal it to keep this probability as low as possible.
It is not optimal for Alice to sample the numbers independently from some fixed distribution,
and she can play better by choosing random numbers in some dependent way.
For
Alice has no minimax strategy,which is closely related to a paradox of T. Cover.
But for
the game has a solution:Alice can choose random numbers (which are dependent random variables)
in such a way that Bob cannot play better than using the classical stopping strategy based on the relative ranks
.
Heuristic performance
The remainder of the article deals again with the secretary problem for a known number of applicants.- The cutoff rule (CR): Do not accept any of the first y applicants; thereafter, select the first encountered candidate (i.e., an applicant with relative rank 1). This rule has as a special case the optimal policy for the CSP for which y = r.
- Candidate count rule (CCR): Select the y encountered candidate. Note, that this rule does not necessarily skip any applicants; it only considers how many candidates have been observed, not how deep the decision maker is in the applicant sequence.
- Successive non-candidate rule (SNCR): Select the first encountered candidate after observing y non-candidates (i.e., applicants with relative rank > 1).
Note that each heuristic has a single parameter y. The figure (shown on right) displays the expected success probabilities for each heuristic as a function of y for problems with n = 80.
Cardinal payoff variant
Finding the single best applicant might seem like a rather strict objective. One can imagine that the interviewer would rather hire a higher-valued applicant than a lower-valued one, and not only be concerned with getting the best. That is, he will derive some value from selecting an applicant that is not necessarily the best, and the value he derives is increasing in the value of the one he selects.To model this problem, suppose that the
applicants have "true" values that are random variableRandom variable
In probability and statistics, a random variable or stochastic variable is, roughly speaking, a variable whose value results from a measurement on some type of random process. Formally, it is a function from a probability space, typically to the real numbers, which is measurable functionmeasurable...
s X drawn i.i.d. from a uniform distribution
Uniform distribution (continuous)
In probability theory and statistics, the continuous uniform distribution or rectangular distribution is a family of probability distributions such that for each member of the family, all intervals of the same length on the distribution's support are equally probable. The support is defined by...
on [0, 1]. Similar to the classical problem described above, the interviewer only observes whether each applicant is the best so far (a candidate), must accept or reject each on the spot, and must accept the last one if he is reached. (To be clear, the interviewer does not learn the actual relative rank of each applicant. He learns only whether the applicant has relative rank 1.) However, in this version his payoff is given by the true value of the selected applicant. For example, if he selects an applicant whose true value is 0.8, then he will earn 0.8. The interviewer's objective is to maximize the expected value of the selected applicant.
Since the applicant's values are i.i.d. draws from a uniform distribution on [0, 1], the expected value
Expected value
In probability theory, the expected value of a random variable is the weighted average of all possible values that this random variable can take on...
of the tth applicant given that
isgiven by
As in the classical problem, the optimal policy is given by a threshold, which for this problem we will denote by
, at which the interviewer should begin accepting candidates. showed that c is either or . (In fact, whichever is closest to .) This follows from the fact that given a problem with applicants, the expected payoff for some arbitrary threshold 1 = c = n isDifferentiating
with respect to c, one gets
Since
for all permissiblevalues of
, we find that is maximized at . Since V is convex in , the optimal integer-valued threshold must be either or . Thus, for most values of the interviewer will begin accepting applicants sooner in the cardinal payoff version than in the classical version where the objective is to select the single best applicant. Note that this is not an asymptotic result: It holds for all .Experimental studies
PsychologistsDecision making
Decision making can be regarded as the mental processes resulting in the selection of a course of action among several alternative scenarios. Every decision making process produces a final choice. The output can be an action or an opinion of choice.- Overview :Human performance in decision terms...
and experimental economists
Experimental economics
Experimental economics is the application of experimental methods to study economic questions. Data collected in experiments are used to estimate effect size, test the validity of economic theories, and illuminate market mechanisms. Economic experiments usually use cash to motivate subjects, in...
have studied the decision behavior of actual people in secretary problems. In large part, this work has shown that people tend to stop searching too soon. This may be explained, at least in part, by the cost of evaluating candidates. Extrapolating to real world settings, this might suggest that people do not search enough whenever they are faced with problems where the decision alternatives are encountered sequentially. For example, when trying to decide at which gas station to stop for gas, people might not search enough before stopping. If true, then they would tend to pay more for gas than they might had they searched longer. The same may be true when people search online for airline tickets, say. Experimental research on problems such as the secretary problem is sometimes referred to as behavioral operations research
Behavioral Operations Research
Behavioral operations research examines the behavior of actual human agents in complex decision problems. BOR is the operations management analog of experimental economics and behavioral finance, and is part of the field known as management science....
.
Origin of the problem
The secretary problem was apparently introduced in 1949 by Merrill M. Flood, who called it the fiancée problemin a lecture he gave that year. He referred to it several times during the 1950s, for example in a conference talk
at Purdue on 9 May 1958, and it eventually became widely known in the folklore although nothing was
published at the time. In 1958 he sent a letter to Leonard Gilman, with copies to a dozen friends including S. Karlin
and J. Robbins, outlining a proof of the optimum strategy,
with an appendix by R. Palermo who proved that all strategies are dominated by a strategy of the
form "reject the first p unconditionally, then accept the next candidate". (See Flood (1958).)
The first publication was apparently by Martin Gardner
Martin Gardner
Martin Gardner was an American mathematics and science writer specializing in recreational mathematics, but with interests encompassing micromagic, stage magic, literature , philosophy, scientific skepticism, and religion...
in Scientific American, February 1960. He had heard
about it from John H. Fox, Jr., and L. Gerald Marnie, who had independently come up with an equivalent
problem in 1958; they called it the "game of Googol". Fox and Marnie did not know the optimum solution;
Gardner asked for advice from Leo Moser
Leo Moser
Leo Moser was an Austrian-Canadian mathematician, best known for his polygon notation....
, who (together with J. R. Pounder) provided a correct analysis for publication in the magazine. Soon afterwards, several mathematicians wrote to Gardner to tell him about the equivalent problem they had heard via the grapevine, all of which can most likely be traced to Flood's original work.
The 1/e-law is due to F. Thomas Bruss (1984)
A 1989 paper by T. S. Ferguson has an extensive bibliography, and points out that a similar (but
different) problem had been considered by Arthur Cayley
Arthur Cayley
Arthur Cayley F.R.S. was a British mathematician. He helped found the modern British school of pure mathematics....
in 1875 and even by Johannes Kepler
Johannes Kepler
Johannes Kepler was a German mathematician, astronomer and astrologer. A key figure in the 17th century scientific revolution, he is best known for his eponymous laws of planetary motion, codified by later astronomers, based on his works Astronomia nova, Harmonices Mundi, and Epitome of Copernican...
long before that.
See also
- Optimal stoppingOptimal stoppingIn mathematics, the theory of optimal stopping is concerned with the problem of choosing a time to take a particular action, in order to maximise an expected reward or minimise an expected cost. Optimal stopping problems can be found in areas of statistics, economics, and mathematical finance...
- Odds algorithmOdds algorithmThe odds-algorithm is a mathematical method for computing optimalstrategies for a class of problems that belong to the domain of optimal stopping problems. Their solution follows from the odds-strategy, and the importance of the...
- Search theorySearch theoryIn microeconomics, search theory studies buyers or sellers who cannot instantly find a trading partner, and must therefore search for a partner prior to transacting....
- Stable marriage problemStable marriage problemIn mathematics and computer science, the stable marriage problem is the problem of finding a stable matching between two sets of elements given a set of preferences for each element. A matching is a mapping from the elements of one set to the elements of the other set...