How to find the best when you can’t go back

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

  1. I’m headed someplace
  2. I’m hungry and need to stop somewhere to eat
  3. I don’t know what restaurants there are between myself and my destination
  4. Once I pass a restaurant, I don’t want to turn around and return to to it
  5. 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 problem1 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).

prob_best
Figure 1: The probability of selecting the best restaurant for various numbers of possible restaurants and initial sample sizes. The decision rule is to choose the first restaurant encountered that is better than the initial sample. Black dots indicate maximal probability for a given number of possible restaurants.

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.

 

mean_rank
Figure 2: The mean ranking of the chosen restaurant (relative to the maximum possible ranking) for various numbers of possible restaurants and initial sample sizes. The decision rule is to choose the first restaurant encountered that is better than the initial sample. Black dots indicate maximal mean ranking for a given number of possible 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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s