As I wrote earlier, I've recently been wanting to look into this Secretary Problem. I have finally managed to put aside a few days to think about it. I wrote a handout that is supposed to clarify the problem. The intention is for a simple, readable introduction for Alex, myself, and perhaps others. I'm not sure how clear/unclear it is, because I haven't shown it to anyone yet. It is temporarily hosted here:

http://patrick.toche.free.fr/teaching/DOCS/SecretaryProblem.pdf

If anyone has a look at it, please do let me know if there are errors, imprecisions, confusions --- any suggestions on how to improve the handout are welcome. It's ultimately intended for MBA students (lawyers, journalists, etc.).

There is nothing new whatsoever in my handout, it's all mostly lifted from the classic paper by Gilbert and Mosteller (written in 1966) and Robert's explanations in this thread.

As I write in the handout, the syntax of the code is not designed to be optimal for Maple, but rather to follow the logical steps of the problem. Hence I used a loop rather than seq. I did not find the need to optimize the code as it was running fast anyhow, but optimizing it is a project for future improvements.

I copy below some of the bits of code I used to produce the figures in the handout:

P := proc(s,n)

if s=1 then 1/n;

else (1/n)*sum((s-1)/(k-1),k=s..n);

fi;

end:

S := n -> [seq( [s, P(s,n)], s=1..n )]:

thePlot := plot(S(N),style=point,symbol=circle,color=red):

plots:-display(thePlot,labels=[s,p],view=[1..N,0..0.5]);

N := 10:

thePointPlot := seq( plot(S(n),style=point,symbol=solidcircle,symbolsize=14,color=(COLOR(HUE,n/N))),n=3..N):

theLinePlot := seq( plot(S(n),style=line,linestyle=dot,color=(COLOR(HUE,n/N))),n=3..N):

plots:-display({thePointPlot,theLinePlot},labels=[s,p],view=[1..N,0..0.5]);

N := 200:

theLinePlot := seq( plot(S(n),style=line,linestyle=dot,color=(COLOR(HUE,n/N))),n=3..N):

plots:-display(theLinePlot,labels=[s,p],view=[1..N,0..0.5]);

# Procedure to select a candidate based on skipping s-1 of n draws

Select := proc(s::nonnegint,n::nonnegint)

local L, M, m, r, c, k;

L := Statistics:-Shuffle([seq(i,i=1..n)]); # generate a random list

M := max(L[1..n]); # the maximum on 1..n

m := max(L[1..s-1]); # the maximum on 1..s-1

r := 0: # initialize the score

for k from s to n do # select a candidate

if L[k]>m then c:=L[k]; k:=n; fi;

end do;

if c=M then r:=1; fi; # update the final score

RETURN(r);

end proc:

T := 100:

Trials := [seq([t,evalf(add(i,i=[seq(Select(S,N),i=1..t)])/t)],t=1..T)]: # Frequency as the number of trials t rises from 1 to T

theTrialsPlot := plot(Trials,style=point,symbol=solidcircle,symbolsize=12,color=red):

plots:-display(theTrialsPlot,labels=[t,p],view=[1..T,0..1]);

T := 10000:

LargeTrials := [seq([t,evalf(add(i,i=[seq(Select(S,N),i=1..t)])/t)],t=1..T,T/20)]: # Frequency for t from 1 to T in steps of T/20

theTrialsPlot := plot(LargeTrials,style=point,symbol=solidcircle,symbolsize=12,color=red):

plots:-display(theTrialsPlot,labels=[t,p],tickmarks=[[1000,5000,10000],default],view=[2..T,0..1]);

Edit: changed the url and posted a slightly revised version