Googol, The Secretary Problem, Mark Leeds' problem.

[Arthur Nadas <nadas@env.med.nyu.edu>]

Dear S-Plusers,

Here is a comment on Mark Leeds' problem.  This problem
is very close to "the secretary problem" , also known as
"the marriage problem"  wherein independent candidates
appear sequentially and cannot be recalled if not accepted. In its
weakest form, only  the relative rank of the candidates is available
at each step.  A version of the problem, requiring the maximization
of the probability of choosing the best among the candidates, was solved
by Dynkin more than half a century ago.  The solution, which is
exact in the limit for increasing number of candidates, is to let the
first 1/e fraction go away and then choose the first candidate who is
superior to all those preceeding.  Sometime in the 1960s, Herb
Robbins solved the version which required that the expected rank of the
chosen candidate be maximized (instead of the probability of being the
best) by a dynamic programming approach.. Martin Gardner also popularized
a version of the problem in Scientific American, a version where the
actual scores are available, as in Mark Leeds' problem. There is now a
huge literature on variations of the problem, inclunding even thick
books!  For some later developments see

Silverman, R.S. and Nádas,
A.  On the game of Googol as ?THE? Secretary Problem. 
In:  Strategies for Sequential Search and Selection in Real
Time (F.T. Bruss, et al. eds, Amer. Math. Society, Providence, RI,
1990, pp. 77-83.

Arthur Nádas

******************************
Tony Plate wrote:

I believe that Mark Leeds' problem is different from the Sultan's
dowry problem (as described at
http://mathworld.wolfram.com/SultansDowryProblem.html)
because in the Sultan's dowry problem, the goal is to identify the
maximum dowry (the payoff is binary), whereas in the Mark Leeds' problem,
the goal is to maximize the expected payoff, where the actual realized
payoff is a number between 1 and 100.
These types of problems are known as "optimal stopping
problems." Mark Leeds' problem is a nice easy one to solve with
dynamic programming. Here's the framework of a solution written as a
recursive function. (I'm sure there's also a closed-form solution to this
version of the problem.)
> V <- function(k) { 
# V(k) is expected value achieved from k trials 
if (k<=0) { 
return(0) 
} else { 
# v1 is expected value achieved from k-1 trials 
v1 <- V(k-1) 
# actual code removed and replaced by explanation :-) 
# X is a random variable - an integer selected uniformly from 1:100 
# The best thing to do is to stop (and accept X) if X is greater than
# the value we expect if we continue, i.e., stop if X > v1. 
# So, our expected value if we stop is E(X | X > v1) (i.e., the mean
# of all values between ceiling(v1) and 100). 
# The expected value if we continue is v1. 
# To calculate the expected value of V(k), we multiply these values 
# by their respective probabilities and sum. 
# return Pr(X > v1) . E(X | X > v1) + Pr(X <= v1) . v1 
} 
} 
> V(0) 
[1] 0 
> V(1) 
[1] 50.5 
> V(2) 
[1] 63 
> V(3) 
[1] 70.03 
> V(4) 
[1] 74.671 
> V(20) 
[1] 92.48587 
>
-- Tony Plate
At Monday 04:02 PM 7/21/2003 -0700, Horace Tso wrote: 
Mark, that's also known as Sultan's Dowry Problem. You want to solve for
the smallest x such that
H(x) = H(n) - 1
where n is the number of turns, and H(n) is harmonic number.
Check out :
http://mathworld.wolfram.com/SultansDowryProblem.html
Cheers.
Horace Tso
>>> "Leeds, Mark" <mleeds@mlp.com> 07/21/03
03:46PM >>> 
i've seen the following question before but 
i don't remember how to do it so 
i was wondering if anyone knows 
where i can find the answer. i'm 
not asking anyone to do it because 
i know it's published somewhere.
you have a game : each turn, 
a random number is chosen 
between 1 and 100 ( assume uniform distribution ) 
and given to you. you can either
A) accept the number and stop the game 
and decide that the number you received is 
your number.
B) throw out that number ( but you 
can't claim it later ) and try for another number
you get say, 20 turns ( numbers 
are chosen with replacement ) and you 
want to maximize your value where 
your value is the number you receive when 
you choose to stop.
what is the algorithm for deciding when to stop ?
sorry to bother everyone.

mark

--------------------------------------------------------------------
This message was distributed by s-news@lists.biostat.wustl.edu. To 
unsubscribe send e-mail to s-news-request@lists.biostat.wustl.edu with
the BODY of the message: unsubscribe s-news
Tony Plate tplate@acm.org
--------------------------------------------------------------------
This message was distributed by s-news@lists.biostat.wustl.edu. To 
unsubscribe send e-mail to s-news-request@lists.biostat.wustl.edu with
the BODY of the message: unsubscribe s-news