From: israel@math.ubc.ca (Robert Israel)
Newsgroups: sci.math
Subject: Re: Probability question
Date: 17 Feb 1998 22:33:32 GMT

In article <Pine.GSO.3.96.980216204825.605A-100000@saga8.Stanford.EDU>, Michael Chun-chieh Lee <mclee@leland.Stanford.EDU> writes:

|> There is a set of n ordered numbers that can take on any real values.  You
|> are then presented these numbers one at a time: your job is to select the
|> highest of the n numbers.  At any point you can say (a) That's it, that's
|> the highest number, at which point you win or lose or (b) No, give me the
|> next number.  You obviously, cannot go backwards.  

This old chestnut is called the "Secretary Problem" or the "Bachelor's
Problem".  

|> What I would like to see is:
 
|>  (a) an expression that describes your odds of winning for n numbers,
|> as a function of n and a, how long you wait before judging the current
|> number against the previous numbers

Let p(k) be the optimal probability of accepting the best candidate, given that 
candidates 1 .. k-1 have already been rejected.  
In particular, p(n) = 1/n (namely the probability that candidate #n is best). 
If you reject #k out-of-hand, p(k)=p(k+1).  On the other hand, if you
accept #k if it is the best so far, p(k) = 1/n + (1-1/k) p(k+1), 
where 1/n is the probability that #k is actually the best (if so, of course 
it is the best so far) and 1-1/k is the probability that you reject #k.  
Thus it is to your advantage to reject #k out-of-hand if 
p(k+1) > 1/n + (1-1/k) p(k+1), i.e. p(k+1) > k/n.  Moreover p(k) >= p(k+1).
Since p(k) is non-increasing while k/n is increasing, the best strategy
must be of the form: accept #k if k >= r and #k is the best so far.
By induction you can show that pi(k) = (k-1)/n (1/(k-1) + 1/k + ... + 1/(n-1))
= (Psi(n) - Psi(k-1))(k-1)/n for k >= r, with r the least integer such that 
Psi(n) - Psi(r) < 1.  For example, with n=20 we have 
Psi(20) - Psi(7) = 1/7 + ... + 1/19 = 1.098 while Psi(20) - Psi(8) = .955
approximately, so r = 8, and the probability of picking the best candidate
is p(8) = 7/20 (Psi(20)-Psi(7)) = .3842 approximately.

|>  (b) I was told that for n -> infinity, the odds go to 1/e.  Why?  I
|> assume this will come out of the expression

Psi(t) has the asymptotic expansion ln(t) - 1/(2 t) + ... as t -> infinity,
so Psi(n) - Psi(t) = 1 for t = n/e + (1-1/e)/2 + O(1/n).  With 
r = n/e + O(1), the probability of picking the best candidate
is pi(r) = 1/e + (1-1/e)/(2 n) + O(1/n^2).  Thus for n=20, pi(8) = .3842
while 1/e + (1-1/e)/40 = .3837 approximately.
 
|>  (c) Is there an analogous strategy if you don't know how large the set of
|> numbers is?

You would have no way of knowing when to stop rejecting candidates.  Of course
you could pick an r arbitrarily, but there would be no way to know which
one would be best.

Robert Israel                            israel@math.ubc.ca
Department of Mathematics             (604) 822-3629
University of British Columbia            fax 822-6074
Vancouver, BC, Canada V6T 1Z2