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
|