Secretaresseprobleem

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken
Deutsche Fotothek, 1951

Het Secretaresseprobleem is een praktisch vraagstuk uit de kansrekening, de statistiek en de beslissingstheorie. Het komt hierop neer:

1. Als we iets of iemand moeten kiezen uit een ongesorteerde reeks en niet mogen terugkomen op een eerdere afwijzing, wanneer kunnen we dan het beste stoppen en beslissen?
2. Hoe groot is de kans dat we zo de beste kandidaat kiezen?

Martin Gardner besprak het secretaresseprobleem in februari 1960 in zijn rubriek Mathematical Recreations in het tijdschrift Scientific American.[1] Het probleem staat ook bekend als het Huwelijksprobleem[2], de Bruidsschat van de sultan en de Grootste taart[3][4] en is verwant aan het Probleem van Cayley (1875) en Googols spel (Game of Googol voor twee spelers).

Formulering[bewerken]

  1. Er is een vacature voor een secretaresse.
  2. Het aantal sollicitanten n is bekend.
  3. De sollicitanten krijgen in een willekeurige volgorde een sollicitatiegesprek, met van tevoren gelijke kans van slagen.
  4. 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.
  5. Een afgewezen sollicitant kan niet opnieuw worden opgeroepen.
  6. Er wordt naar het beste resultaat (de optimale strategie) gestreefd.

De normale sollicitatieprocedure in Nederland bestaat uit een selectie van brieven of CV's gevolgd door sollicitatiegesprekken met vooralsnog uitverkorenen. Doorgaans wordt pas na het laatste sollicitatiegesprek de knoop doorgehakt. De formulering van het secretaresseprobleem wijkt daarvan af (zie punt 3, 4, 5). Uiteraard maakt het voor de wiskunde niet uit of het hier om secretaresses gaat of iets anders, als de abstracte regels maar gelijk zijn. (Denk bijvoorbeeld aan schoenen winkelen en niet terug gaan naar een eerder bezochte winkel.)

Oplossing[bewerken]

De beste aanpak lijkt om een aantal k sollicitanten te spreken en af te wijzen - een soort marktverkenning - en dan de eerstvolgende sollicitant te nemen die beter is dan alle voorgaande. Als geen betere langskomt, nemen we maar de laatste. Wat is de gunstigste waarde van k? En hoe groot is de kans op een optimaal resultaat? Berekening leert ons het volgende.

  1. Voor grote aantallen sollicitanten n geldt k = n / e = 0,368 \cdot n, met e het grondtal van de natuurlijke logaritme (e = 2,71828..).
  2. De kans dat we zo de beste kandidaat vinden nadert voor grote aantallen eveneens tot 1/e = 0,368.

Men spreekt daarom van de 1/e-regel, die geldt voor een algemene klasse van dergelijke problemen (Bruss, 1984).

Voorbeeld[bewerken]

Dus als we in het secretaresseprobleem 100 sollicitanten hebben, kunnen we het best de eerste 100 / e = 100 / 2,72 = 36,8 dus 37 na het gesprek afwijzen, en de eerstvolgende sollicitant die beter is aannemen. De kans dat we zo de beste secretaresse krijgen is optimaal maar slechts ongeveer 0,37 (op een schaal van 0 tot 1). Door de regels van het probleem is het niet anders.

Bewijs[bewerken]

Bovenstaande aanpak mislukt, als

  1. de beste kandidaat bij de eerste k zat
  2. de beste kandidaat niet bij de eerste k zat, maar volgt op een betere kandidaat dan de eerste k (want we moesten de eerste betere kiezen). Een extreem geval hiervan doet zich voor, als de reeks wel gesorteerd is van slechtste tot beste kandidaat: dit is bijzonder onwaarschijnlijk.

Kansen berekenen[bewerken]

We berekenen nu[3] voor het algemene geval de kansen p dat de beste kandidaat nummer k+1 of k+2 of ... of n is en gekozen wordt. De kans dat een willekeurige kandidaat de beste is, is 1/(het totaal aantal kandidaten) = 1/n. We verwerpen de eerste k kandidaten en gaan op zoek naar de eerstvolgende betere. De kans p(k+1) dat de kandidaat k+1 de beste is en dan gekozen wordt is

p(k+1) = \frac{1}{n}

Kandidaat k+2 is beter dan de eerste k kandidaten, maar kandidaat k+1 niet, anders was die gekozen! Dat wil zeggen dat de beste kandidaat van de eerste k+1 kandidaten in de groep van de eerste k kandidaten zit. De kans daarop is \frac{k}{k+1}, dus de totale kans p(k+2) dat kandidaat k+2 gekozen wordt krijgen we door vermenigvuldiging

p(k+2) = \frac{1}{n} \times \frac{k}{k+1}

Kandidaat k+3 is beter dan de eerste k kandidaten, maar kandidaten k+1 en k+2 moeten minder goed zijn dan de eerste k kandidaten, anders was kandidaat k+1 of k+2 gekozen! Dus de beste kandidaat van de eerste k+2 kandidaten zit in de groep van de eerste k kandidaten. De kans daarop is \frac{k}{k+2}, dus door vermenigvuldiging:

p(k+3) = \frac{1}{n} \times \frac{k}{k+2}

Zo gaan we door tot we bij de laatste kandidaat nummer n zijn aangekomen. Kandidaten k+1, k+2, ...., n-1 moeten minder goed zijn geweest dan de beste van de eerste k kandidaten, dus

p(n) = \frac{1}{n} \times \frac{k}{n-1}

Totale kans[bewerken]

Hoe groot is de totale kans dat de beste kandidaat in de groep met nummers k+1, k+2, ... n zit is en gekozen wordt? De som van de losse kansen die we net berekend hebben:

p_{totaal} = \frac{1}{n} + \frac{1}{n} \times \frac{k}{k+1} + \frac{1}{n} \times \frac{k}{k+2} + .... + \frac{1}{n} \times \frac{k}{n-1} = \frac{k}{n} (\frac{1}{k} + \frac{1}{k+1} + \frac{1}{k+2} + ... + \frac{1}{n-1})

Grote aantallen[bewerken]

Voor grote n en k - in de limiet voor n en k naar oneindig (∞), zie Constante van Euler-Mascheroni - kan dit benaderd worden door

p_{totaal} \approx \frac{k}{n} \times ln(\frac{n-1}{k-1}) \approx -\frac{k}{n} \times ln(\frac{k}{n}) .

Omdraaien van het argument van de natuurlijke logaritme ln geeft het minteken. Voor grote n benadert de kans een continue functie. Stel k/n = x, dan p_{totaal}(x) = - x . ln(x) .

Grootste kans?[bewerken]

Voor welke k/n = xmax hebben we de grootste kans (heeft deze functie een maximum)? We moeten eisen dat de eerste afgeleide van p_totaal voor die xmax gelijk moet zijn aan 0 en de tweede afgeleide kleiner dan 0:

- x_{max} . \frac{1}{x_{max}} - ln(x_{max}) = 0, dus ln(x_{max}) = -1 en x_{max} = (\frac{k}{n})_{max} = \frac{1}{e} \approx 0,368

De tweede afgeleide -\frac{1}{x} is voor deze waarde van x gelijk aan -\frac{1}{x_{max}} = -e dus kleiner dan 0. Hiermee is voor grote n en k het bewijs geleverd, dat de beste keuze wordt bereikt voor k = n / e. Hoe groot is dan de optimale kans dat we de beste kandidaat te pakken hebben? Invullen van x_max geeft

p_{totaal}(x_{max}) = - \frac{1}{e} \times ln( \frac{1}{e}) = \frac{1}{e} \approx 0,368

Dus dit getal vinden we tweemaal: als de relatieve grootte van de groep kandidaten die we meteen afwijzen én als de kans op een optimaal resultaat.

Voorbeelden voor kleine aantallen[bewerken]

Hoe pakt de berekening in de praktijk voor een beperkt aantal kandidaten uit (dus k en n niet heel groot)?

n = 2[bewerken]

Met maar twee kandidaten is het makkelijk. We kunnen één kandidaat bekijken en daarna de eerst volgende beste kiezen of de laatste: dat is hier de onvermijdelijke kandidaat nummer 2. De kans moet 1/2 zijn. Klopt dat? We noteren het totaal aantal als index van de p: p_{totaal} (voor k=1) = p_2(k=1) = \frac{1}{2}( \frac{1}{1}) = \frac{1}{2}.

n = 3 en 4[bewerken]

Met drie kandidaten krijgen we

p_{totaal}(voor k=1) = p_3(k=1) = \frac{1}{3}( \frac{1}{1} + \frac{1}{2}) = \frac{1}{2}
p_{totaal}(voor k = 2) = p_3(k=2) = \frac{2}{3}( \frac{1}{2}) = \frac{1}{3}

Dus de eerste kandidaat (k = 1, k/n = 0,333) afwijzen en dan de eerste betere nemen geeft de grootste kans (1/2) op een optimaal resultaat. Met vier kandidaten worden de kansen

p_4(k=1) = \frac{1}{4}( \frac{1}{1} + \frac{1}{2} + \frac{1}{3}) = 0,458
p_4(k=2) = \frac{2}{4}( \frac{1}{2} + \frac{1}{3}) = 0,417
p_4(k=3) = \frac{3}{4}( \frac{1}{3}) = 0,250

Weer geeft de eerste kandidaat (k = 1, k/n = 0,25) afwijzen en de eerste betere nemen de grootste kans (0,458) op het beste resultaat.

n = 10[bewerken]

We hebben nu tien kandidaten. De eerste (twee) kandidaten afwijzen en de eerste betere nemen levert de kansen:

p_{10}(k=1) = \frac{1}{10}( \frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \frac{1}{6} + \frac{1}{7} + \frac{1}{8} + \frac{1}{9}) = 0,283
p_{10}(k=2) = \frac{2}{10}( \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \frac{1}{6} + \frac{1}{7} + \frac{1}{8} + \frac{1}{9}) = 0,366 enzovoorts.

In tabelvorm:

n = 10
k 1 2 3 4 5 6 7 8 9
k/n 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9
Kans 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[bewerken]

De volgende tabel toont de gevallen met betrekkelijk weinig kandidaten.

n 2 3 4 5 6 7 8 9 10 .. 25 limiet n→∞
k_max 1 1 1 2 2 2 3 3 3 .. 9 n/e
k_max/n 0,500 0,333 0,250 0,400 0,333 0,286 0,375 0,333 0,300 .. 0,360 1/e ~ 0,368
Beste kans 0,500 0,500 0,458 0,433 0,428 0,414 0,410 0,406 0,399 .. 0,381 1/e ~ 0,368

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

Geschiedenis[bewerken]

Flood en Gardner[bewerken]

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[bewerken]

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 n>2 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[bewerken]

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[bewerken]

Psychologen en experimentele economen hebben het gedrag onderzocht van proefpersonen die het secretaresseprobleem in de praktijk moesten oplossen.[5] 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[bewerken]

  • Bearden, J.N. (2006). A new secretary problem with rank-based selection and cardinal payoffs. Journal of Mathematical Psychology 50: 58–9 . DOI:10.1016/j.jmp.2005.11.003.
  • Bearden, J.N., Murphy, R.O. Rapoport, A. (2005). A multi-attribute extension of the secretary problem: Theory and experiments. Journal of Mathematical Psychology 49 (5): 410–425 . DOI:10.1016/j.jmp.2005.08.002.
  • Bearden, J.N., Rapoport, A., Murphy R.O. (2006). Sequential observation and selection with rank-dependent payoffs: An experimental test. Management Science 52 (9): 1437–49 . DOI:10.1287/mnsc.1060.0535.
  • Bruss, F. Thomas (1984). A unified Approach to a Class of Best Choice problems with an Unknown Number of Options. Annals of Probability 12 (3): 882–891 . DOI:10.1214/aop/1176993237.
  • Bruss, F. Thomas (2000). Sum the odds to one and stop. Annals of Probability 28 (3): 1384–91 . DOI:10.1214/aop/1019160340.
  • Chow, Y.S., Moriguti, S., Robbins, H., & Samuels, S.M.: Optimal selection based on relative rank (the "secretary problem"). Chow et al.: optimal selection based on relative rank
  • Ferguson, T.S. (1989). Who solved the secretary problem?. Statistical science 4 (3): 282–296 . DOI:10.1214/ss/1177012493. Ferguson: Who solved the secretary problem?
  • Flood, Merrill R., Brief uit 1958 (kopie in de Martin Gardner papers aan de Stanford University Archives, series 1, box 5, folder 19.
  • Freeman, P.R. (1983). The secretary problem and its extensions: A review. International Statistical Review / Revue Internationale de Statistique 51 (2): 189–206 . DOI:10.2307/1402748. Freeman: The secretary problem and its extensions: A review
  • Gardner, Martin, New Mathematical Diversions from Scientific American, Simon and Schuster, 1966, Chapter 3, Problem 3 [herdruk van oorspronkelijke column van februari 1960 met commentaar].
  • Gnedin, A. (1994). A solution to the game of Googol. Annals of Probability 22 (3): 1588–1595 . DOI:10.1214/aop/1176988613.
  • Hill, T.P., "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)
  • Ketelaar, Timothy en Todd, Peter M., 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
  • Miller, Geoffrey F., The mating mind: how sexual choice shaped the evolution of human nature, Anchor Books, 2001 ISBN 0-385-49517-X.
  • Sardelis, D., Valahas, T. (March 1992). Decision Making: A Golden Rule. American Mathematical Monthly 99 (3): 935–942 .
  • Seale, D.A., Rapoport, A. (1997). Sequential decision making with relative ranks: An experimental investigation of the 'secretary problem'. Organizational Behavior and Human Decision Processes 69 (3): 221–236 . DOI:10.1006/obhd.1997.2683.
  • Soto, José: Secretary problems, October 21 2010, SPAMS Secretary problems . Presentatie, bespreekt varianten.
  • Stein, W.E., Seale, D.A. en Rapoport, A. (2003). Analysis of heuristic solutions to the best choice problem. European Journal of Operational Research 151: 140–152 . DOI:10.1016/S0377-2217(02)00601-X.

Externe links[bewerken]

Nederlandstalig[bewerken]

Engelstalig[bewerken]

Wetenschappelijke artikelen en boek[bewerken]

Lesmateriaal en overig[bewerken]

Franstalig[bewerken]

Bronnen, noten en/of referenties
  1. Gardner, Martin, New Mathematical Diversions from Scientific American, Simon and Schuster, 1966, Chapter 3, Problem 3 [herdruk van oorspronkelijke column van februari 1960 met commentaar]
  2. Wiskundemeisjes.nl Ionica Smeets: Echte liefde (toepassing op partnerkeuze)
  3. a b Kennislink.nl Alex van den Brandhof: De grootste taart
  4. Nwo.nl Nationale Wetenschapsquiz 2006 vraag 16
  5. Bearden, Murphy, and Rapoport, 2006; Bearden, Rapoport, and Murphy, 2006; Seale and Rapoport, 1997