Feynman's Restaurant Problem Revealed
In 2002 Ralph Leighton and I had lunch at Indra, in Glendale,
California, a Thai restaurant where Ralph had often lunched with
Richard Feynman. Over a delicious curry Ralph told me that at one such
lunch in the 1970’s he and Feynman discussed the problem of how to
decide whether it is better to try a new restaurant for lunch or go
back to a known good one, a kind of 'stopping' problem. Unfortunately
Ralph did not recall many of the details, other than the general notion
that one tries to maximize a "score" assuming that the restaurants one
has tried can be ordered from worst to best.
In 2004-5 I analyzed variants of what I imagined this problem might
have been, and strategies for solving them, with the aim of trying to
reconstruct the original. Ralph provided some scans of Feynman's "back of the envelope" notes,
made while they were discussing the problem at lunch, from which I
failed to discern anything definite that accorded with Ralph’s
description of the problem, and after some time I dropped the whole
thing. However, the problem stayed in the back of my mind, and
three years later (2008) I wrote to Ralph:
I have been working on some problems in
probability theory lately (pretty interesting ones you might like) that
got me thinking about Feynman's restaurant problem again. I re-read our
correspondence on the subject, and looked at the scans of Feynman's
notes, and I am frustrated: If Feynman solved it, it must have been a
well-defined problem, but I can not tell from what you have said and
what he has written, precisely how it was defined... So I have no
problem to solve or too many. I can think of dozens of possible
variants of this problem, all with completely different solutions, so
it is not interesting to know "kind of" what the problem was - I really
want to know exactly what it was. Is there anyone you can think of that
might have discussed or corresponded with Feynman about the restaurant
problem?
... to which Ralph responded:
You're right that the key is in
defining the problem, and I can't remember how we decided to end up
defining it. And Feynman's notes to himself could well have been
according to another definition.
Subsequent email to Ralph indicates that I had formulated the problem and its solution as it currently appears on The Feynman Lectures Website
in November 2008, where the problem and its answer has been posted as
‘Feynman’s Restaurant Problem’ ever since. The full solution was
posted in September 2011.
In August, 2013 I was contacted about ‘Feynman’s Restaurant Problem’ by Tom Griffiths
(Director of the Computational Cognitive Science Lab and the Institute
of Cognitive and Brain Sciences at the University of California,
Berkeley) and Brian Christian (author of The Most Human Human, What Artificial Intelligence Teaches Us About Being Alive,
Anchor, 2012). Tom and Brian were working on a book about mathematical
approaches to solving everyday problems (such as where to eat for
lunch), and asked if they could include Feynman’s Restaurant Problem.
After disclosing the history of the problem (as given above) I offered
to show them the scans of Feynman’s notes. And that was very fortunate,
because Tom, who is familiar with stopping problems, recognized the
form of Feynman’s solution, and "peeled the scales from my eyes,”
allowing me for the first time to understand and analyze how Feynman
went about solving this problem. Tom wrote:
It’s pretty clear from the start of the
first one that the setup is each restaurant having a quality uniformly
distributed between 0 and 1, then having a threshold on quality such
that if the restaurant exceeds the threshold you stay, otherwise you
switch. The first part deals with the case where there are just two
nights of dining. The strategy is to choose X, then choose X again if X
is greater than the threshold S. The optimal threshold is solved for.
In this case it's clear that the threshold is 50%. After that, the
notes generalize this threshold for more remaining nights. Normally the
threshold would have to be defined by backwards induction…I think the
analysis is most similar to the "full information" secretary problem,
where the interviewer has access to the percentile ranks of applicants
(equivalently, has values drawn from a uniform distribution). In that
case the optimal strategy is a decreasing threshold too, committing to
the first applicant above the threshold when n are remaining.
Tom followed this email with neatly typeset notes giving his formal
mathematical interpretation of Feynman’s notes, in his own notation.
But soon we discovered a problem: one of Feynman’s calculations that
Tom interpreted as an approximation accurate only for small n, turned
out to be exact for all n! Tom quickly found an explanation within the
context of his interpretation, but it seemed unlikely to me that
Feynman would think in such formal mathematical terms, particularly on
a problem he solved hastily on a couple scraps of paper over lunch!
Furthermore, the explanation left other questions unanswered. Feeling
we were straying too far from Feynman’s original thoughts on the
problem, I turned once again to his notes, armed with what Tom, to whom
I am forever indebted, showed me. I scrutinized Feynman's notes as
carefully as I could in an attempt to trace Feynman's chain of thought
(walking humbly in the footsteps of a giant!)
Because the copies of Feynman’s notes are not very clear (and even if
they were, Feynman’s handwriting can be difficult to read), I began by
making a transcription of the first page of his notes (including all cross-outs, incomplete equations, etc), though not the second, which is written out more neatly.