Secretaresseprobleem
Het secretaresseprobleem is een beroemd vraagstuk uit de theorie van optimaal stoppen. Het is uitvoerig geanalyseerd in de kansrekening, de statistiek en de beslissingstheorie.

Het secretaresseprobleem is hoe te beslissen als sollicitanten voor de vacature van secretaresse worden opgeroepen voor een gesprek. Na elk sollicitatiegesprek wordt direct beslist of de sollicitant voor de vacature zal worden aangenomen, waarna de resterende sollicitanten niet meer in aanmerking worden genomen.

Het secretaresseprobleem is van toepassing op situaties waarin een keuze gemaakt moet worden uit een ongesorteerde reeks en men niet mag terugkomen op een eerdere afwijzing. De vraag is dan wanneer men het beste kan stoppen en hoe groot de kans is dat men zo de beste kandidaat kiest.

Het secretaresseprobleem staat ook bekend als het huwelijksprobleem, de bruidsschat van de sultan, en de grootste taart. Het is verwant aan het probleem van Cayley (1875) en Googols spel (Game of Googol voor twee spelers).

Martin Gardner besprak het secretaresseprobleem in februari 1960 in zijn rubriek Mathematical Recreations in het tijdschrift Scientific American.

Formulering 
De formulering van het secretaresseprobleem luidt
 Er is een vacature voor een secretaresse.
 Het aantal sollicitanten  is bekend.
 De sollicitanten krijgen in een willekeurige volgorde een sollicitatiegesprek.
 De beoordeling van de sollicitanten is ondubbelzinnig (geen gelijke beoordelingen). Afwijzing of aanvaarding van een sollicitant berust uitsluitend op de beoordelingen tot dusver. Na een gesprek moet de sollicitant meteen afgewezen of aangenomen worden.
 Een afgewezen sollicitant kan niet opnieuw worden opgeroepen.
 Er wordt naar het beste resultaat (de optimale strategie) gestreefd.

Oplossing 
De beste aanpak blijkt om een aantal van  sollicitanten te spreken en af te wijzen - een soort marktverkenning - en dan de eerstvolgende sollicitant te nemen die beter is dan alle voorgaande. Als er geen betere langskomt, wordt de laatste gekozen. Wat is de gunstigste waarde van ? En hoe groot is de kans de beste kandidaat te vinden? Berekening leert:
 Voor grote aantallen sollicitanten  geldt , met e het grondtal van de natuurlijke logaritme.
 De kans dat zo de beste kandidaat gevonden wordt, nadert voor grote aantallen tot .
Men spreekt daarom van de 1/e-regel, die geldt voor een algemene klasse van dergelijke problemen (Bruss, 1984).

Bewijs
Het kan bewezen worden dat de optimale strategie een stopregel is van de bovengenoemde vorm. D.w.z. de eerste k kandidaten worden afgewezen en de eerstvolgende die beter is dan alle voorgaande wordt gekozen; als die er niet is wordt de laatste gekozen.

Wat is de kans  dat de beste kandidaat nummer  is en gekozen wordt? De kans dat een willekeurige kandidaat de beste is, is . Als kandidaat  de beste is en ook gekozen wordt, houdt dat in dat de kandidaten  niet gekozen zijn, dus de eerste  kandidaten waren beter dan deze . Dus:

en

De kans  dat met deze strategie de beste kandidaat gekozen wordt is dus:

Grote aantallen
Voor grote  kan de partiële som van de harmonische reeks benaderd worden door (zie Constante van Euler-Mascheroni):

Dus is voor grote  en , met :

Optimum
Het maximum van  wordt bereikt voor  waarvoor:

Dus:

en de maximale kans op de beste kandidaat is bij deze strategie:

De tweede afgeleide  is voor  gelijk aan , dus kleiner dan 0, zodat in het stationaire punt inderdaad een maximum wordt bereikt.

Voorbeeld voor grote aantallen
Als er in het secretaresseprobleem 100 sollicitanten zijn, kunnen we het best de eerste 100 / e = 100 / 2,72 = 36,8 dus 37 na het gesprek afwijzen, en de eerstvolgende sollicitant aannemen die beter is dan elk van de voorgaande. De kans dat we zo de beste secretaresse krijgen is niet groter dan ongeveer 37%.

Voorbeelden voor kleine aantallen
Hoe pakt de berekening in de praktijk voor een beperkt aantal van n kandidaten uit?

n = 2 
Met maar twee kandidaten is het gemakkelijk. De kans dat de beste kandidaat nummer 1 is, is gelijk aan de kans dat het nummer 2 is, namelijk 1/2. Dus of men neemt direct de eerste kandidaat, of men laat de eerste voorbijgaan en kiest dan (noodgedwongen) de tweede.

n = 3 
Bij drie kandidaten geldt:

Direct de eerste kandidaat kiezen:

De eerste kandidaat voorbij laten gaan: 

De eerste twee kandidaten voorbij laten gaan: 

Dus de eerste kandidaat afwijzen en dan de eerstvolgende betere nemen geeft de grootste kans (1/2) op de beste kandidaat.

n = 4
Met vier kandidaten worden de kansen:

Direct de eerste kandidaat kiezen

De eerste kandidaat voorbij laten gaan: 

De eerste twee kandidaten voorbij laten gaan: 

De eerste drie kandidaten voorbij laten gaan: 

Weer is de optimale strategie: de eerste kandidaat afwijzen en dan de eerstvolgende betere nemen.

n = 10
Bij tien kandidaten zijn de kansen:

 

 
 
enzovoort.

Tabel:

{| class="wikitable"
|k || 0 || 1 || 2|| 3|| 4|| 5|| 6|| 7|| 8|| 9
|-
|k/n || 0 || 0,1 || 0,2|| 0,3|| 0,4|| 0,5|| 0,6|| 0,7|| 0,8|| 0,9
|-
|pn(k)||0,1||0,283||0,366||0,399||0,398||0,373||0,327||0,265||0,189||0,100
|}
Voor k = 3 (k/n = 0,3) vinden we de grootste kans (0,399) dus
de eerste drie kandidaten afwijzen en de eerstvolgende betere nemen geeft het beste resultaat.

Overzicht
De volgende tabel toont de gevallen met betrekkelijk weinig kandidaten.

Volgens het bewijs wordt voor grote k en n zowel de verhouding kmax/n als de optimale kans benaderd door 1/e ~ 0,368.

Geschiedenis

Flood en Gardner
Voor zover bekend werd het secretaresseprobleem in 1949 voor het eerst gesteld door de Amerikaanse wiskundige Merrill M. Flood, bekend van het prisoner's dilemma: hij noemde het toen in een college het probleem van de verloofde (the fiancée problem). In de loop van de jaren 50 werd het een vermaard probleem in wiskundige kring. In 1958 stuurde Flood een brief aan vrienden rond met een voorlopig bewijs van de optimale strategie: "wijs de eerste p onvoorwaardelijk af, neem daarna de volgende kandidaat" (bedoeld is de volgende die beter is, Flood 1958).

De eerste publicatie schijnt van Martin Gardner te zijn in de Scientific American van februari 1960. Hij had van John H. Fox, Jr. en L. Gerald Marnie over het probleem gehoord. Zij hadden in 1958 een gelijkwaardig probleem bedacht, dat ze het Googolspel (game of Googol) noemden, maar kenden de optimale oplossing niet. Gardner vroeg om hulp en Leo Moser leverde met J. R. Pounder een juiste analyse voor Scientific American. De 1/e-regel of -wet is te danken aan F. Thomas Bruss (1984). Ferguson (1989) geeft een uitgebreide bibliografie en noemt soortgelijke problemen van Arthur Cayley (1875) en Johannes Kepler.

Googols spel
Martin Gardner goot het secretaresseprobleem in 1960 in de vorm van Googols spel voor twee spelers, dat als volgt verloopt:
Speler 1 mag zoveel (n) kaartjes gebruiken als gewenst, en moet op ieder kaartje een ander positief getal schrijven. De getallen mogen lopen van een kleine positieve breuk tot meer dan een googol (een 1 met honderd nullen). Speler 2 ziet niet welke getallen opgeschreven worden. De kaartjes worden geschud en met het getal naar beneden op tafel gelegd. Een voor een keert speler 2 de kaartjes om. De bedoeling is dat deze stopt als hij of zij denkt het grootste getal gevonden te hebben: is dit juist, dan heeft speler 2 gewonnen. Men mag niet terugkomen op een eerdere keuze. Als alle kaartjes worden omgedraaid, moet het laatste gekozen worden.

Voor  is er een oplossing (Gnedin 1994): speler 1 kan op zo'n manier willekeurige getallen (afhankelijke random variabelen) kiezen dat de beste stopstrategie van speler 2 de methode van de relatieve volgorde (relative ranks) niet kan overtreffen.

Varianten 
Verschillende varianten van het secretaresseprobleem zijn onderzocht, onder meer:
 Er mogen twee sollicitanten gekozen worden in plaats van één enkele.
 Het aantal sollicitanten is onbekend (Bruss 1984).
 Sollicitanten mogen een gelijke beoordeling krijgen.
 Afgewezen sollicitanten mogen worden teruggeroepen.
 De keuze mag ook op de een na beste sollicitant vallen.

Experimenteel onderzoek
Psychologen en experimentele economen hebben het gedrag onderzocht van proefpersonen die het secretaresseprobleem in de praktijk moesten oplossen. In het algemeen bleek dat men te snel stopte met zoeken, deels vanwege de moeite die de beoordeling van kandidaten kost. Toegepast op dagelijkse situaties wijst dit erop dat men te snel opgeeft als alternatieven zich na elkaar voordoen. Bijvoorbeeld als een automobilist moet tanken, wordt mogelijk een te duur benzinestation gekozen.

Literatuur
 
 
 
 
 
 : Optimal selection based on relative rank (the "secretary problem"). Chow et al.: optimal selection based on relative rank
  Ferguson: Who solved the secretary problem?
 , Brief uit 1958 (kopie in de Martin Gardner papers aan de Stanford University Archives, series 1, box 5, folder 19.
  Freeman: The secretary problem and its extensions: A review
 , New Mathematical Diversions from Scientific American, Simon and Schuster, 1966, Chapter 3, Problem 3 [herdruk van oorspronkelijke column van februari 1960 met commentaar].
 
 , "Knowing When to Stop". American Scientist, Vol. 97, 126-133 (2009). (Een Franse vertaling stond in Pour la Science (juli 2009) Savoir quand s' arrêter)
 , Framing Our Thoughts: Ecological Rationality as Evolutionary Psychology's Answer to the Frame Problem, , Hoofdstuk 5 in Conceptual Challenges in Evolutionary Psychology, p. 187., Harmon R. Holcomb III (Ed.), Kluwer Academic Publishers, Dordrecht, 2001, pdf
 
 
 
 : Secretary problems, October 21 2010, SPAMS Secretary problems . Presentatie, bespreekt varianten.

Externe links

Nederlandstalig
 Wiskundemeisjes.nl Ionica Smeets: Echte liefde
 Kennislink.nl Alex van den Brandhof: De grootste taart
 Weetlogs.scilogs.be Rudi Penne en Paul Levrie: Een wiskundige heeft de grootste kans op de beste koopjes

Engelstalig

Wetenschappelijke artikelen en boek
  Ferguson: Who solved the secretary problem?
 Thomas S. Ferguson: Optimal Stopping and Applications (book)
  Freeman: The secretary problem and its extensions: A review
  Chow et al.: Optimal selection based on relative rank

Lesmateriaal en overig
  University of Alabama at Huntsville, Virtual Laboratories in Probability and Statistics: Secretary problem
  Online Utility to Calculate Optimal r
  MathWorld.wolfram.com Weisstein, Eric W.: Sultan's Dowry Problem
 Neil Bearden's Optimal Search Page
 MathPages: Optimizing Your Wife
  A practical example of the theory of taking decisions and the theory of optimal stopping.

Franstalig
  Pourlascience.fr Savoir quand s 'arrêter

Kansrekening
Statistiek
Statistische paradox
Wiskundig vraagstuk