The legendary Caltech physicist Richard Feynman and two editors of The Feynman Lectures

Chapter 4, Problem 83

(choose chapter or problem)

The legendary Caltech physicist Richard Feynman and two editors of The Feynman Lectures on Physics (Michael Gottlieb and Ralph Leighton) posed the following problem about how to decide what to order at a restaurant. You plan to eat m meals at a certain restaurant, where you have never eaten before. Each time, you will order one dish. The restaurant has n dishes on the menu, with n m. Assume that if you had tried all the dishes, you would have a definite ranking of them from 1 (your least favorite) to n (your favorite). If you knew which your favorite was, you would be happy to order it always (you never get tired of it). Before youve eaten at the restaurant, this ranking is completely unknown to you. After youve tried some dishes, you can rank those dishes amongst themselves, but dont know how they compare with the dishes you havent yet tried. There is thus an explorationexploitation tradeo : should you try new dishes, or should you order your favorite among the dishes you have tried before? A natural strategy is to have two phases in your series of visits to the restaurant: an exploration phase, where you try dierent dishes each time, and an exploitation phase, where you always order the best dish you obtained in the exploration phase. Let k be the length of the exploration phase (so m k is the length of the exploitation phase). Your goal is to maximize the expected sum of the ranks of the dishes you eat there (the rank of a dish is the true rank from 1 to n that you would give that dish if you could try all the dishes). Show that the optimal choice is k = p2(m + 1) 1, or this rounded up or down to an integer if needed. Do this in the following steps: (a) Let X be the rank of the best dish that you find in the exploration phase. Find the expected sum of the ranks of the dishes you eat, in terms of E(X). (b) Find the PMF of X, as a simple expression in terms of binomial coecients. (c) Show that E(X) = k(n + 1) k + 1 . Hint: Use Example 1.5.2 (about the team captain) and Exercise 18 from Chapter 1 (about the hockey stick identity). (d) Use calculus to find the optimal value of k.