Wiskunde Wanneer is het verstandig om te stoppen met zoeken naar iets beters? Natuurkundige Richard Feynman formuleerde voor die vraag ooit een exacte wiskundige oplossing, die nu opnieuw is ontdekt.
In de jaren zeventig zat natuurkundige en Nobelprijswinnaar Richard Feynman (Nobelprijs 1965) met een vriend in een Thais restaurant in Californië. Zijn vriend twijfelde. Zou hij opnieuw zijn favoriete gemberkip bestellen, of eens iets nieuws proberen? Feynman maakte van deze vraag een wiskundige puzzel. Hij vond ook een oplossing, maar zijn handgeschreven notities werden nergens gepubliceerd.
Mogelijk verklaart dat waarom zijn restaurantprobleem nooit dezelfde bekendheid kreeg als het verwante ‘secretaresseprobleem’, een klassieker uit de theorie van het optimaal stoppen. Bij zulke problemen gaat het erom te bepalen of de mogelijkheid die zich nu aandient goed genoeg is, of dat het de moeite loont om verder te zoeken. Dat speelt niet alleen in restaurants. Wie een huis zoekt, een parkeerplaats kiest of overweegt van baan te veranderen, staat voor hetzelfde dilemma.
Richard Feynman in 1986.
Feynmans aantekeningen waren moeilijk leesbaar en bleven decennialang grotendeels onontcijferd. Daar is nu verandering in gekomen. Brian Christian (University of Oxford), Evan Russek (City University of New York) en Thomas Griffiths (Princeton University) reconstrueerden het probleem, inclusief Feynmans oplossing. Hun studie verscheen deze maand in Proceedings of the National Academy of Sciences.
In het scenario van de drie wetenschappers bezoek je een stad voor een vast aantal dagen. Iedere avond eet je in een restaurant. Je hebt geen idee welk restaurant goed is – Google en Tripadvisor bestonden in Feynmans tijd nog niet. Elk restaurant heeft weliswaar een kwaliteitsscore, maar die is niet vooraf te raadplegen. Hoe hoger die score, hoe beter de zaak.
Om het probleem wiskundig hanteerbaar te maken, nam Feynman aan dat de kwaliteitsscore een getal tussen 0 en 1 is en dat alle waarden even waarschijnlijk zijn. Je krijgt de score van een restaurant pas te horen nadat je er hebt gegeten. Het doel is de totale kwaliteit van al je restaurantbezoeken samen (de som van alle scores) zo groot mogelijk te maken. Wat is dan beter: blijven zoeken naar die gastronomische parel, of opnieuw aanschuiven bij dat restaurant waar je eerder al een best goede ervaring had? Feynmans vraag is welke strategie het beste resultaat oplevert.
Hoeveel restaurants de stad precies telt, doet er niet toe, zolang dit aantal maar groter is dan het aantal dagen dat je er verblijft. Grof gezegd komt de oplossing hierop neer. De eerste avonden probeer je verschillende restaurants uit om een indruk te krijgen van het aanbod. Daarna stap je over op een favoriet.
Dat kantelmoment wordt bepaald door wat een dynamische drempelwaarde wordt genoemd. Zolang geen van de bezochte restaurants boven die drempel uitkomt, blijf je experimenteren. Zodra een restaurant de drempel wél overschrijdt, stop je met zoeken en keer je alle resterende avonden terug naar het beste restaurant dat je tot dan toe hebt gevonden. Praktische bezwaren – bijvoorbeeld dat het restaurant misschien niet elke dag open is of de verveling van herhaling – worden genegeerd.
De waarde van de drempel is niet constant. Aan het begin van de reis ligt hij hoog; naarmate er minder avonden overblijven, zakt hij geleidelijk. Met andere woorden: hoe meer dagen verstrijken, des te minder zin heeft het om op zoek te gaan naar een uitzonderlijk goed restaurant.
Feynman maakte dit wiskundig precies. Hij bewees dat de optimale drempel gelijk is aan de wortel van het aantal resterende restaurantbezoeken, gedeeld door één plus die wortel. Heb je nog zestien avonden te gaan, dan bedraagt de drempel dus √16 / (1 + √16) = 0,8. Ligt de score van alle restaurants die je tot dan toe hebt geprobeerd daaronder? Dan kies je de volgende avond opnieuw een onbekende zaak. Na dat volgende bezoek zakt de drempel naar, afgerond, 0,795 (vervang in de voorgaande formule het getal 16 door 15). Een restaurant kan eerst worden afgewezen en later alsnog goed genoeg blijken: een score van 0,798 is bij zestien resterende bezoeken net te laag, maar voldoet wel zodra er nog vijftien bezoeken over zijn.
In het model van Feynman hebben alle restaurants een score tussen 0 en 1, en al die scores zijn gelijkmatig verdeeld: de kansverdeling is ‘uniform’. Dat is niet bijzonder realistisch: het is goed denkbaar dat relatief veel restaurants ergens in de middenmoot zitten. Christian, Russek en Griffiths keken daarom ook verder. Ze onderzochten wat er gebeurt als de kwaliteit van restaurants anders verdeeld is, zoals via een exponentiële verdeling. Daarbij komen lage scores veel vaker voor dan hoge. De laagst mogelijke score is opnieuw 0, maar een harde bovengrens is er niet. De kans op een score hoger dan 5 is echter verwaarloosbaar: die ligt onder de 1 procent.
Het gemiddelde ligt precies bij 1. Iets minder dan twee derde van alle scores ligt daaronder en ruim een derde erboven (de exacte fractie is trouwens 1/e, met e het getal van Euler). Dat is een opvallend verschil met symmetrische verdelingen zoals de uniforme en de normale verdeling, waar precies de helft van alle scores onder het gemiddelde ligt. De exponentiële verdeling past goed bij een stad met veel matige eettentjes en maar een paar echte topzaken.
In dit geval verandert ook de optimale strategie. Als je de stad lang bezoekt, ligt de drempel aanvankelijk behoorlijk hoog. Het is dus de moeite waard om langer door te zoeken. De formule voor die drempel is niet eenvoudig. Waar je in het uniforme geval genoeg hebt aan een wortel, verschijnt nu de Lambert-W-functie, genoemd naar de achttiende-eeuwse wiskundige Johann Lambert. Voor wie het weten wil: de drempelwaarde bedraagt 1 + W((n–1)/e), met n het resterende aantal etentjes. Concreet: met nog twintig bezoeken te gaan, ligt de drempel rond 2,5; met nog vijf bezoeken 1,7.
Uiteindelijk dicteert de wiskunde wat ons gevoel al vermoedde: alles draait om de tijd die je nog rest. Wie nog een lange vakantie voor zich heeft, kan extra kieskeurig zijn. Wie bijna naar huis gaat, neemt genoegen met dat oké restaurant van een vorige keer.
Op de hoogte van kleine ontdekkingen, wilde theorieën, onverwachte inzichten en alles daar tussenin