#!/usr/local/bin/perl -w

$ROUNDS = $ARGV[0] || 10000;

@rank = 1..100;


for $k (3..60){
    $statscore=0;
    for $i (1..$ROUNDS){
	@rank = fisher_yates_shuffle(\@rank);
	$count=0;
	$max=0;
	for $n (@rank){
	    $count++;
	    if ($count <= $k){
		if ($n > $max){ $max=$n; }
	    }else{
		if ($n > $max){
		    $score = $n;
		    $statscore += $n;
		    last;
		}elsif ($count==100){
		    $score = $n;
		    $statscore += $n;
		}
	    }
	}
    }
    print "Rejecting $k: mean rank ", $statscore/$ROUNDS, "\n";
}


sub fisher_yates_shuffle {
    my $deck = shift;  # $deck is a reference to an array
    my $i = @$deck;
    while ($i--) {
        my $j = int rand ($i+1);
        @$deck[$i,$j] = @$deck[$j,$i];
    }
    return @$deck;
}


__END__
From sjherschko@netscape.net Fri Jun 24 09:23:25 2005
Date: Fri, 24 Jun 2005 03:23:25 -0400
From: Stephen J. Herschkorn <sjherschko@netscape.net>
Newsgroups: sci.math, sci.op-research
Subject: Re: A variation on the Secretary Problem

In sci.math, Robert Israel wrote:

>In article <1119587547.844510.192540@g43g2000cwa.googlegroups.com>,
>[in sci.math] Zass <jbeasley@gmail.com> wrote:
>
>
>  
>
>>I have a variation on the secretary problem I'd like to discuss. I've
>>been toying with it, and I'd love to hear people's ideas.
>>
>>The problem is such: A sultan prince is ready to marry a wife. One
>>hundred of the most beautiful women have been gathered from across the
>>kingdoms to present themselves to him. The sultan sees the women one at
>>a time, and upon seeing each one he either chooses her or rejects her.
>>He cannot go back on his decision. The question is, how can he maximize
>>the expected beauty of his wife.
>>    
>>
>
>The problem is not fully specified unless you tell us how "beauty"
>is distributed.
>
>  
>
>>In the normal problem, the question is to find the best strategy to get
>>the best wife. This is different -- what's the strategy to get the
>>highest expected beauty?
>>
>>At first, I tried it this way:
>>Assume the women are ranked 1-100. Pick k women and reject them, then
>>take the next woman that beats those k. I found that the best strategy
>>was k=9 (I think, this was years ago), and you get an expected beauty
>>of about 91.
>>    
>>

Question to Zass:  What happens if none of the remaning candidates are 
better than the best among the first  k?  Do you end up choosing the 
last candidate?

>
>Ah, so is it the expected _rank_ that you want to maximize?
>If so, you should say so at the start.
>
>I assume you know nothing about the actual distribution of beauty
>on any absolute scale, and you just want to maximize the rank of
>the woman you choose.  So let A(n) be your expected value (under the
>best possible strategy) after rejecting the first n women.  Thus, 
>as you say, A(99) = 50.5.  Now after rejecting the first n women
>suppose you see candidate n+1, whose rank among the women seen so 
>far is k.  You have two possible moves: accept her, and get an 
>expected score of 101 k/(n+2), [...]
>

I don't see where you get this expectation.  If you have seen  n+1 
candidates, and  k-1 of these are of lower rank than the current 
candidate,  that means you have seen n + 1 - k candidates better than 
the current one.  Therefore, the current candidate is equally likely to 
have absolute rank of any of  k, k+1,..., 99-n+k,  so the expected 
absolute rank of the current candidate is  (99-n)/2 + k.

More generally, suppose there are  n  candidates total  (n=100  in this 
example).  Let  V_m(k)  be the optimal expected absolute rank of the 
chosen candidate given you have inspected  m  candidates and k of these 
are worse than the current candidate  (0 <= k < m).  The maximal 
expected rank is  V_1(0).  V_n(k) = k+1,  and, for  m < n,

V_m(k)  =  maj((n-m)/2 + k + 1,  sum(i=0..m, V_(m+1) (i)) / (m+1))

I have the suspicion that the best one can do from any policy is end up 
with an expected rank is  (n+1)/2,  but I would have to think about how 
to show that.  It's been a while since I have worked on such problems.

-- 
Stephen J. Herschkorn                        sjherschko@netscape.net
Math Tutor in Central New Jersey and Manhattan

From jbeasley@gmail.com Fri Jun 24 06:32:27 2005
Date: 23 Jun 2005 21:32:27 -0700
From: Zass <jbeasley@gmail.com>
Newsgroups: sci.math
Subject: A variation on the Secretary Problem

Hey everyone,

I have a variation on the secretary problem I'd like to discuss. I've
been toying with it, and I'd love to hear people's ideas.

The problem is such: A sultan prince is ready to marry a wife. One
hundred of the most beautiful women have been gathered from across the
kingdoms to present themselves to him. The sultan sees the women one at
a time, and upon seeing each one he either chooses her or rejects her.
He cannot go back on his decision. The question is, how can he maximize
the expected beauty of his wife.

In the normal problem, the question is to find the best strategy to get
the best wife. This is different -- what's the strategy to get the
highest expected beauty?

At first, I tried it this way:
Assume the women are ranked 1-100. Pick k women and reject them, then
take the next woman that beats those k. I found that the best strategy
was k=9 (I think, this was years ago), and you get an expected beauty
of about 91.

But, thinking about it some more, I felt there was a flaw in this
reasoning. How could I prove it was the best strategy. I think I've
found a better strategy.

A. Assume we've seen 99 women. We must pick the last one. What is her
expected beauty? 50.5.

B. So now assume we've seen 98 women. Using A, If the woman looks
better than a 50.5 given the previous 98, pick her. Otherwise, reject
her. What is her expected beauty?

This one must be either more beautiful than average (48/99 of the
time), less beautiful (48/99 of the time), or in the middle (1/99) of
the time.
If she is more beautiful, her expected beauty is 75.5 If she is less
beautiful, her expected beauty is 50.5. If she is less beautiful, her
expected beauty is 25.5

So then 49/99 of the time, we get 75.5, 1/99 of the time, we get 50.5,
and 49/99 of the time, we reject her and go on to the last one, giving
us a value of 50.5

So    49/99 * 75.5 + 50/99 * 50.5
    = (3699.5 + 2525) / 99
    = 62.87

So if we reject the first 98 women, we have an expected beauty of
62.87.

C. So now assume we've seen 97 women. Using B, if the woman looks
better than a 62.87 given the previous 97, pick her. Otherwise reject
her...

etc, etc..

Using this strategy recursively, we should be able to find the ideal
stopping point.

Any thoughts? This seems to me like it must be the ideal strategy,
since at any point we can calculate exactly what the expected beauty B
of the next woman would be .. so for any candidate, we accept her if
she is (probably) better than B or reject if she's worse than B.

I'd love to hear any thoughts or comments! I've been thinking about
this for a long time so I'd love to hear if my ideas are way off base
or if I'm onto something :)

Julien