Often when traveling or exploring a new city, I find myself with the following problem:

- I’m headed someplace
- I’m hungry and need to stop somewhere to eat
- I don’t know what restaurants there are between myself and my destination
- Once I pass a restaurant, I don’t want to turn around and return to to it
- I’d like to eat at one of the best restaurants available (where “best” is a function of both food quality and expense)

An obvious solution, of course, is to buy a smart phone and take the time to search online. An alternative, if you’re more in the mood for wandering on foot than online, is to inspect the first few restaurants you pass to get a sense of the quality of restaurants in that locale, and to then pick the next restaurant that exceeds the quality of the best of your sample (or until you run out of restaurants or time). The problem then becomes, “How many restaurants should I sample before I decide to choose the next best?”.

The last time this happened to me, I remembered that I had actually read the optimal solution to this problem^{1} in Henry Stark and John Wood’s textbook *Probability, Random Processes, and Estimation Theory for Engineers* (1994). Assuming that the order in which you encounter the restaurants is random, Stark and Wood are able to prove that in the limit of a large number of restaurants, the optimal initial sample size is *n*/*e* where *n* is the total number of restaurants you’re willing to consider and *e* is the natural number (approximately 2.718). Thus, if you’re willing to explore up to nine restaurants, to maximize your chances of selecting the best restaurant, you should examine the first three restaurants and then choose the next restaurant that’s better than the first three (or the ninth restaurant if you fail to come across a restaurant better than the first three).

Since Stark and Wood’s proof assumes a large number of restaurants and I probably don’t have the time or patience to explore more than 20, I ran some Monte Carlo simulations to see what the optimal sample size is for 20 or fewer restaurants. The results are shown in Figure 1 and closely agree with Stark & Wood’s approximately *n*/3 rule. If you fit a least-squares line to the optimal sample size as a function of the total number of restaurants, the slope is 0.37. Interestingly, if instead of trying to find the best restaurant, your goal is to maximize the mean ranking of the restaurant you choose, the number of restaurants you should sample is much less (Figure 2). The least squares line for this objective has a slope of 0.13. So one should only sample around 10% of the possible number of restaurants.

So there you have it, a solution to your restaurant wandering needs. In practice, I wonder how useful these rules of thumb are since, even when you’re a stranger, you surely can infer something about the distribution of restaurant quality in that area and recognize an exceptional restaurant even without having to take an initial sample. Also, the order in which you encounter restaurants is not random, since restaurants of similar caliber tend to group together. Anyone up for doing a randomized experiment to see how well this works?

REFERENCES:

Stark, H. & Wood, J.W. (1994) *Probability, Random Processes, and Estimation Theory for Engineers *(2nd ed.). Upper Saddle River, N.J.: Prentice-Hall.