Sultan's Dowry with known distribution

Let there be n daughters, and x_k the dowry of daughter k.  The
condition to pick daughter k is given by

  Prob[x_k highest] >= Prob[x_j highest for some j _and_
                            optimal strategy will pick x_j]    (*)

Prob[x_k highest] is nondecreasing with increasing x as well as with
increasing k.  That is, if the optimal strategy tells us to pick the
k-th daughter with dowry x, we should pick the (k+...)-th daughter with
dowry (x+...), too.

Imagine that the optimal strategy tells us to pick the k-th daughter
with dowry x, but we restrict our choice to one of daughters > k.  Then
the above tells us that the optimal strategy for this subproblem is
simply to choose the next x_j > x_k.

If we consider only x_k larger than all x_i before, and let p = n - k be
the number of daughters left, then (*) is

  Prob[exactly 0 dowries higher than k-th in last p] >=
        Prob[exactly 1 dowry higher than k-th in last p] +
        Prob[exactly 2 dowries higher than k-th in last p]/2 +
        ...
        Prob[exactly p dowries higher than k-th in last p]/p.  (**)

[ By the way, this inequality is still correct for the original problem
  without distribution, and can be written

    k/n >= k/n * sum(1/m*choose(p,m)/choose(n-1,m), m=1..p),

  which is -- as expected -- independent of x_k. ]

If we are given a probability distribution in the form
Prob[x_k <= x] = F(x), then (**) simplifies to

  F(x_k)^p >= sum(1/m*choose(p,m)*F(x_k)^(p-m)*(1-F(x_k))^m, m=1..p).

Note that your decision only depends on the number of daughters left
and the given probability distribution.

For a specific example, let's take a uniform distribution on the
interval [0,1].  Then F(x) = x, and we obtain the following table

p =  0     .0000000000
p =  1     .5000000000
p =  2     .6898979486
p =  3     .7758450676
p =  4     .8245895830
p =  5     .8559492082
p =  6     .8778070171
p =  7     .8939100422
p =  8     .9062652924
p =  9     .9160441614
p = 10     .9239761266

which tells us, for example, that if p = 3 daughters are yet to see, we
should pick the current if

  (i)  the dowry is highest until now
  (ii) the dowry is >= .7758450676

-- Rolf Strebel <strebel@dioxide.inf.ethz.ch>  (August 1998)

strebel@dioxide.inf.ethz.ch (Rolf Strebel) wrote:
>Let there be n daughters, and x_k the dowry of daughter k.  The
>condition to pick daughter k is given by

with "condition", you mean, that the following inequality must be
valid for any optimal strategy?  And if we have a strategy, which makes
it an equality, then the strategy is optimal?

>  Prob[x_k highest] >= Prob[x_j highest for some j _and_
>                            optimal strategy will pick x_j]    (*)

with uniform [0,1] distribution this reads :
     1/n >= Prob to win the game using the optimal strategy

ah, stop; that can't be meant.  You mean : (?)
1.) there is an optimal strategy consisting of numbers o_1,...,o_n,
   such that daughter k is accepted iff her dowry if bigger than o_k
   and is also bigger than all preceeding dowrys.
2.)  Prob[x_k >= max{x_1,...,x_n}]
   >= Prob[ the max-dowry is bigger than the corresponding o_ value ]

>Prob[x_k highest] is nondecreasing with increasing x as well as with
>increasing k.

So Prob[x_k highest] is a function of x and k?  The only restriction
was, that the probability of two dowries being the same is zero.

>That is, if the optimal strategy tells us to pick the
>k-th daughter with dowry x, we should pick the (k+...)-th daughter
>with dowry (x+...), too.

you mean    x>o(k) implies x>o(l) for all l>k .

>Imagine that the optimal strategy tells us to pick the k-th daughter
>with dowry x, but we restrict our choice to one of daughters > k.

so this is a different new game, in which we are not allowed to pick
the *first* daughter with dowry x_k > o(k), where o(k) is the optimal
value from the original game.

>Then the above tells us that the optimal strategy for this subproblem
>is simply to choose the next x_j > x_k.
>
>If we consider only x_k larger than all x_i before, and let p = n - k
>be the number of daughters left, then (*) is
>
>  Prob[exactly 0 dowries higher than k-th in last p] >=
>        Prob[exactly 1 dowry higher than k-th in last p] +
>        Prob[exactly 2 dowries higher than k-th in last p]/2 +
>        ...
>        Prob[exactly p dowries higher than k-th in last p]/p.  (**)

I suppose, this is correct but unfortunately I can't see why.

>For a specific example, let's take a uniform distribution on the
>interval [0,1].  Then F(x) = x, and we obtain the following table

      n-k        o(k)
--------------------------
 >p =  0     .0000000000
 >p =  1     .5000000000
 >p =  2     .6898979486
 >p =  3     .7758450676
 >p =  4     .8245895830
 >p =  5     .8559492082
 >p =  6     .8778070171
 >p =  7     .8939100422
 >p =  8     .9062652924
 >p =  9     .9160441614
 >p = 10     .9239761266

o(n-p) seems to be roughly asymptotic to 1-1/p .

>which tells us, for example, that if p = 3 daughters are yet to see,
>we should pick the current if
>
>  (i)  the dowry is highest until now
>  (ii) the dowry is >= .7758450676

well done, all seems to be correct, I only wished I could follow your
first steps ...

This still leaves the question :
  what is the probability to win the game - using this optimal
  strategy - as a function of n ?

-- QSCGZ <qscgz@aol.com>  (August 1998)