Restaurant Problem

The expected value of the max of $k$ dishes chosen from $N$ without replacement is $(N+1) \frac{k}{k+1}$ (see this discussion for a proof), and the average rating of any of the first $k$ meals is just $\frac{N+1}2,$ so the expected average of the ratings is $\frac{N+1}2 \left( \frac{k}4 + \frac{4-k}4 \frac{2k}{k+1} \right) = \frac{9k-k^2}{8k+8} (N+1).$ This recovers Mark's explicit calculations for $k=1,2,3,4.$ A quick check shows that this is maximized when $k=2.$

Also, it generalizes: if we're eating $m$ total meals instead of $4,$ the formula is $\frac{(2m+1)k-k^2}{2mk+2m} (N+1).$ This is maximized at $k = \sqrt{2m+2}-1,$ so the solution will be either the floor or the ceiling of this number in general.

These algebraic solutions are very impressive, but aren't they using a sledgehammer to crack a nut? If we give ranks of 4 (best) to 1 (worst) of the four dishes we may or may not sample, then the mean ranks if we sample all four or just one are clearly 2.5. If we sample just two there are six possibilities: three including dish 4, two including dish 3 but not dish 4, and one with dishes 1 and 2. The mean for the first group is that of 4, 2, 4, 4, i.e. 3.5, for the second group it's that of 3, 1.5, 3, 3, i.e. 21/8, and for the last group it's that of 2, 1, 2, 2, i.e. 7/4. So overall mean is (3 x 3.5 + 2 x 21/8 + 7/4)/6 = 35/12. If we sample just three dishes then there are four possibilities, three including dish 4 with mean of 4 for the other 2 dishes, and one possibility with dishes 3, 2 and 1. The mean for the first group is that of 4, 2, 2 and 4, i.e. 3, and of second group is that of 3, 2, 1, 3, i.e. 2.25. So overall mean is (3 x 3 + 2.25)/4 = 45/16, which is less than 35/12. So sample of 2 is best. If N is greater than 4 we know nothing about the dishes we don't sample (they may be delicious!), so this makes no difference to our expectation. Unsubtle, but Occam would approve. For a general result, if we sample n out of N dishes and then stick to the highest ranking for the remaining (N-n) meals, then the mean rank equals {n(N+1)(2N-n+1)}/{2N(n+1)}. From this we can deduce that the optimal value of n is when SQRT(2N+2.25) - 1.5 < n < SQRT(2N+2.25) - 0.5. Certain values of N (2, 5, 9, 14, …, i.e. of type (k^2 + 3k)/2) give two co-optimal values, e.g. when N = 5, n =2 and n = 3 both give 3.6 as highest mean rank.

If $R_j$ is the expected average rating after four meals, given that the first $j$ choices have been made randomly, and the best of these options chosen thereafter, then $R_1 \; = \; \frac{1}{N}\sum_{a=1}^N \frac{a+a+a+a}{4} \; = \; \tfrac12(N+1)$ Let $D_2 = \{(a,b) : 1 \le a,b \le N\,,\,a \neq b\}$ . Then $R_2 \; = \; \frac{1}{N(N-1)}\sum_{(a,b) \in D_2} \frac{a + b +2\mathrm{max}(a,b)}{4}$ Now $\sum_{(a,b) \in D_2}a \; = \; \sum_{a=1}^N a(N-1) \; = \; \tfrac12(N-1)N(N+1)$ while $\sum_{(a,b) \in D_2}\mathrm{max}(a,b) \; = \; \sum_{m=2}^N m \big|\{(a,b) \in D_2\,:\, \mathrm{max}(a,b) = m\}\big| \; = \; \sum_{m=2}^N m \times 2(m-1) \; = \; \tfrac23(N-1)N(N+1)$ so that $R_2 \; = \; \frac{1}{4N(N-1)}\big[\tfrac12(N-1)N(N+1) + \tfrac12(N-1)N(N+1) + \tfrac43(N-1)N(N+1)\big] \; = \; \tfrac{7}{12}(N+ 1)$ Similarly, let $D_3 = \{(a,b,c): 1 \le a,b,c \le N \,,\, a,b,c\,\mathrm{distinct}\}$ , so that $R_3 \; = \; \frac{1}{N(N-1)(N-2)}\sum_{(a,b,c) \in D_3} \frac{a+b+c+\mathrm{max}(a,b,c)}{4}$ Now $\sum_{(a,b,c) \in R_3}a \; = \; \sum_{a=1}^N a(N-1)(N-2) \; = \; \tfrac12(N+1)N(N-1)(N-2)$ while $\sum_{(a,b,c) \in D_3}\mathrm{max}(a,b,c) \; = \; \sum_{m=3}^N m \big|\{(a,b,c) \in D_3\,:\, \mathrm{max}(a,b,c) = m\}\big| \; = \; \sum_{m=3}^N m \times 3(m-1)(m-2) \; = \; \tfrac34(N+1)N(N-1)(N-2)$ and hence $R_3 \; = \; \frac{1}{4N(N-1)(N-2)}\big[\tfrac32(N+1)N(N-1)(N-2) + \tfrac34(N+1)N(N-1)(N-2)\big] \; = \; \tfrac{9}{16}(N+1)$ Finally. if $D_4 = \{(a,b,c,d) : 1 \le a,b,c,d \le N \,,\, a,b,c,d\,\mathrm{distinct}\}$ , then $\sum_{(a,b,c,d) \in D_4}a \; = \; \sum_{a=1}^N a(N-1)(N-2)(N-3) \; = \; \tfrac12(N+1)N(N-1)(N-2)(N-3)$ and so $R_4 \; = \; \frac{1}{N(N-1)(N-2)(N-3)}\sum_{(a,b,c,d) \in D_4}\frac{a+b+c+d}{4} \; = \; \tfrac12(N+1)$ The largest of $R_1 = R_4 = \tfrac12(N+1)$ , $R_2 = \tfrac{7}{12}(N+1)$ and $R_3 = \tfrac{9}{16}(N+1)$ is $R_2$ for all $N$ , and so the answer is $\boxed{2}$ .

I couldn't find an online source for this, but in Matt Parker's book Things to Make and Do in the Fourth Dimension , he talks about an optimal dating algorithm where you use the first $\sqrt{n}$ potential matches to compare against all future dates. It's an adaptation of the "secretary problem", but looking that up online brings up the $n/e$ method, which, as I understand it, is more useful when you want the absolute best possible choice, but when you allow wiggle room with how good the final choice is, it is lacking.

Anyways, I just plugged 4 into the square root to get 2 as the number of trial choices.

(I admit, this was lazy and not entirely justifiable)

I took an educated guess using my intuition. Firstly, when n is 1, you will get a completely average restaurant experience as you are sampling the same random dish 4 times. Similarly, when n is 4, you are ordering 4 random dishes, which again will give you an average experience. So the question comes down to which gives a better outlook, ordering 2 random dishes and the best of the 2 for the two following days (n =2), or 3 random dishes and the best of the 3 for the fourth day (n = 3). When n = 2 on average your repeated meals will be above average. When n = 3 your repeated meal will be above average, and more so than the two repeated meals of n = 2, as it is the best of 3 instead of the best of 2. However, due to the shape of the normal distribution, there would be diminishing returns when sampling more meals. Thus I intuited that 2 random meals and the best repeated twice would yield a higher average rating than 3 random reals and the best repeated once, and my answer was $\boxed{n=2}$ .

Try Restaurant Problem 2 and Secretary Problem .

I will investigate the cases $N=4$ , $N=5$ and $N=\infty$ and then do an educated guess. Note

• the distinction between N (the number of dishes on the menu) and n (the number of trial days).
• n=1 and n=4 both reflect an effectively random choice and the expected quality is that of the average dish.
• the expected quality $Q(n)$ is defined on different scales for different menu sizes N and can only be compared between different trial periods n, if they belong to the same N.

Case $N=4$ : We simply write out the cases. Let Q be the average expected quality of a meal over all days: n=1, n=4: these both reflect a random choice and the expected quality Qis that of the average dish. $Q(1)=Q(4)=\frac{1+2+3+4}{4}=2.5$

n=2: the pair 1,2 gives best result 2, and overall sum 1×1+3×2=7; the pair 1,3 gives best result 3 and overall sum 1×1+3×3=10, etc. Thus we find $Q(2)=\frac{7+10+13+11+14+15}{6×4}=2.916..$

n=3: the triplet 1,2,3 gives best result 3 and overall sum 1+2+3+3=9, etc. Thus we find: $Q(3)=\frac{9+11+12+13}{4×4}=2.812..$ So for the case N=4, the optimum is at n=2.

Case $N=5$ : Similarly we find

n=1, n=4: $Q(1)=Q(4)=\frac{15}{5}= 2.5$

n=2: $Q(2)=\frac{140}{40} = 3.5$

n=3: $Q(3)=\frac{135}{40} = 3.375$

So for the case N=5, the optimum is at n=2.

Case $N=\infty$ : The quality of the best meal after n trial days can be modeled by having the dish quality vary from 0 to 1 on each dimension of an n-dimensional cube, and integrate the maximum of the coordinates over the generalized volume.

n=1, n=4:

$\int_0^1{x}dx=\frac{1}{2}$

$Q(1)=Q(4)=\frac{1}{4}(4×\frac{1}{2})=\frac{1}{2}$

n=2:

$\int_0^1{\int_0^1{max(x,y)}dy}dx=\int_0^1{(\int_0^x{x}dy+\int_x^1{y}dy})dx=\int_0^1{(x^2+\frac{1}{2}(1^2-x^2)})dx=\frac{1}{2}\int_0^1{(x^2+1})dx=\frac{1}{2}(\frac{1}{3}+1)dx=\frac{2}{3}$

$Q(2)=\frac{1}{4}(2×\frac{1}{2}+2×\frac{2}{3})=\frac{7}{12}$

n=3:

$\int_0^1{\int_0^1{\int_0^1{max(x,y,z)}dz}dy}dx=$ $\int_0^1{\int_0^1{(\int_0^{max(x,y)}{max(x,y)dz+\int_{max(x,y)}^1{z}dz)}}dy}dx=$ $\frac{1}{2}\int_0^1{\int_0^1{(max^2(x,y)+1)}dy}dx=$ $\frac{1}{2}\int_0^1{(\int_0^x{x^2+1dy}+\int_x^1{y^2+1}dy)}dx=$ $\frac{1}{2}\int_0^1{x(x^2+1)+\frac{1}{3}(1^3-x^3)+1-x}dx=$ $\frac{1}{2}\int_0^1{\frac{2}{3}x^3+\frac{4}{3}}dx=$ $\frac{1}{2}(\frac{1}{6}+\frac{4}{3})=\frac{3}{4}$

$Q(3)=\frac{1}{4}(3×\frac{1}{2}+1×\frac{3}{4})=\frac{9}{16}$

So for cases $N=4$ , $N=5$ and $N=\infty$ the optimum is at $\boxed{n=2}$ and my educated guess is that that is the right answer.