Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

First, the background: Feynman's restaurant problem asks how we can maximise the total rating of the meals we eat at a restaurant with $N$ items on the menu, given that we know up-front that we are going to eat $M$ meals there.

I have transcribed the problem and answer:

Assume that a restaurant has $N$ dishes on its menu that are rated from worst to best, $1$ to $N$ (according to your personal preferences). You, however, don't know the ratings of the dishes, and when you try a new dish, all you learn is whether it is the best (highest rated) dish you have tried so far, or not. Each time you eat a meal at the restaurant you either order a new dish or you order the best dish you have tried so far. Your goal is to maximize the average total ratings of the dishes you eat in $M$ meals (where $M \leq N$).

The average total ratings in a sequence of meals that includes $n$ "new" dishes and $b$ "best so far" dishes can be no higher than the average total ratings in the sequence having all $n$ "new" dishes followed by all $b$ "best so far" dishes. Thus a successful strategy requires you to order some number of new dishes and thereafter only order the best dish so far. The problem then reduces to the following:

Given $N$ (dishes on the menu) and $M\leq N$ (meals to be eaten at the restaurant), how many new dishes $D$ should you try before switching to ordering the best of them for all the remaining $(M–D)$ meals, in order to maximize the average total ratings of the dishes consumed?

Answer : $D = \sqrt{2(M+1)} - 1$

So if we are visiting a restaurant with $20$ dishes $7$ times, we should pick different dishes for the first $3$ trips, then have the best of those the next $4$ times.

However, as far as practical application goes, this answer is the answer to a question that doesn't match reality - rarely do we know exactly how many times we're going to eat at a restaurant!

Suppose instead of having $M$ equal some fixed value, we instead have $M$ distributed according to some probability distribution $P$. For example, suppose we know we are going to visit a restaurant with $20$ dishes on some number of occasions uniformly distributed over $5..10$. What now should be our value for $D$? What about if $P$ is a less simple distribution?

* edit to add *

Is it as simple as $\sum_m{P(m) D(m)}$ (which is I think $E(D)$?) where $D(m) = \sqrt{2(m+1)} - 1$ as above? Assuming that $P$ can't change over the course of the exercise, which as mjqxxxx points out would be quite possible in reality...

share|cite|improve this question
Sounds like figuring out the ideal will be much more work than the expected increase in happiness the optimal choice will lead you to. Just decide to order the chocolate ice cream each time and spend your mental effort on something more productive instead. – Henning Makholm Feb 6 '13 at 15:06
I imagine the probability distribution $f$ would depend strongly on the quality of the dishes tried so far... – mjqxxxx Feb 6 '13 at 15:31
@HenningMakholm "More productive"...typical corporative mentality. We mathematicians usually increase our "stock" of happiness thinking about such "non-productive" matters, and from time to time someone discovers that these "useless" digressions can be quite useful. – Matemáticos Chibchas Feb 6 '13 at 17:08

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.