Wikipedia:Reference desk/Archives/Mathematics/2008 December 21

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

December 21

Feynman Restaurant Problem

(This problem and its solution were invented by Michael Gottlieb based on a story told to him by Ralph Leighton. It can be found posted at www.feynmanlectures.info.)

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 is less than or equal to 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 <= 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?

Honestly I have no idea how you're supposed to answer this...any ideas? —Preceding unsigned comment added by 65.92.236.87 (talk) 03:51, 21 December 2008 (UTC)

A very similar, though simpler, problem is the secretary problem. Perhaps you will find something helpful there. Eric. 68.18.63.75 (talk) 05:03, 21 December 2008 (UTC)

A google search for "Feynman's restaurant problem" turns up a page with an expression for D in terms of M (I assume the OP has already seen this, as they state the problem with exactly the same words and notation). However, it doesn't say how this expression is derived. Also, as the given expression does not involve N, I am wondering if it is only an asymptotic solution for M << N. Gandalf61 (talk) 12:48, 21 December 2008 (UTC)

Wasn't getting very far with the discrete version of the problem as originally posed, so I thought let's assume M<<N and transition to a continuous version. So assume each dish has a "score" which is a real number normalised to be in the range [0,1], and when you choose a new dish, the score of this dish is uniformly distributed in [0,1]. You choose a new disk on the first D visits, then choose the best dish eaten so far on the remaining M-D visits. You don't know the scores of the dishes - you only know which dish out of those eaten so far has scored highest. Objective is to choose D so as to maximise the expected total score across all M visits.

After choosing new dishes on the first D visits, the expected total score so far is D/2. Suppose the expected score of the best dish after sampling k different dishes is b_k. Then you want to choose D so as to maximise (D/2) + (M - D)b_D.

I couldn't find a closed form for b_k, but I did find that

$b_{k+1}={\frac {1+b_{k}^{2}}{2}}$

which is sufficient to set up a spreadsheet model. For M = 10, 50, 100, 200 I get D = 4, 11, 16, 24. The expression in the link I referred to above gives D = 3.7, 9.1, 13.2, 19.0. So either I am over-estimating D or the link solution is under-estimating D. Gandalf61 (talk) 18:12, 21 December 2008 (UTC)

Okay, I think I am over-estimating D, as a numerical simulation shows better agreement with the values given by the link solution. I think my recursive expression for b_k must be wrong. Does anyone know what the expected value of the maximum of k values each drawn from a U(0,1) distribution is ? Gandalf61 (talk) 15:19, 22 December 2008 (UTC)

I've looked at this and if you try to find an exact expression of the function of M you're optimizing, you get a sum of expressions involving factorials, and I don't really know where to go from there. Namely, unless I've miscalculated, you need to pick M to maximize:

• ${\frac {M(N+1)}{2}}+{\frac {N-M}{M(N!)(N-M)!}}\sum _{k=M}^{N}{\frac {k!}{(k-M)!}}$ [This was a mistake - see below.]

Anybody know how to do this?

On the other hand, I think you can approximate the problem this way for large N: You get to eat N dishes. Each time you try a new dish, its quality is a random real number between 0 and 1. How many times should you try a new dish before settling?

Unless I've made a mistake, this problem can be solved almost exactly. By "almost" I mean you get M within 1.

The probability, after M tries, that the best dish had quality ≤ t is t^M. Thus you get a probability density function by differentiating: Mt^{M - 1}. The expectancy of the best dish after M tries is the integral over [0,1] of t times this function, which gives M / (M + 1). So the thing you want to maximize is (1 / 2)M + (N - M)M / (M + 1). A little calculus (please correct me if I've miscalculated) shows that this function of a real variable M increases until it attains a maximum at the real number sqrt(2N + 2) - 1, and then decreases. Therefore the maximum is one of the two integers nearest sqrt(2N + 2) - 1.

If I haven't made a mistake, I imagine that with a lot of extra work, this could be turned into a proof that in the actual problem the optimal M is asymptotically equivalent to sqrt(2N). Joeldl (talk) 16:01, 22 December 2008 (UTC)

It seems I misinterpreted the problem. What was called D above, I called M, and for some reason I remembered the problem as having M and N identical. So in what I wrote, replace N with M and M with D, and N is sort of infinite. Also, the exact formula I gave first is for a special case. Sorry - I shouldn't have worked from memory. Joeldl (talk) 16:08, 22 December 2008 (UTC)

Okay, this might be a correct formula to maximize in terms of D:

• ${\frac {D(N+1)}{2}}+{\frac {M-D}{D(N!)(N-D)!}}\sum _{k=D}^{N}{\frac {k!}{(k-D)!}}$

• [Correction: The formula should have been ${\frac {D(N+1)}{2}}+{\frac {(M-D)D(N-D)!}{N!}}\sum _{k=D}^{N}{\frac {k!}{(k-D)!}}$ ]

The sum can be simplified

$\sum _{k=D}^{N}{\frac {k!}{(k-D)!}}=D!\sum _{k=D}^{N}{\binom {k}{D}}=D!\sum _{k=0}^{N-D}{\binom {k+D}{D}}=D!{\binom {N}{D+1}}={\frac {N!}{(D+1)(N-D-1)!}}$

Bo Jacoby (talk) 23:41, 22 December 2008 (UTC).

Uh, except that that's not correct. Take N = 4 and D = 2 for an example. Joeldl (talk) 05:37, 23 December 2008 (UTC)

Uh, how embarassing. Thank you. I ment to write

$\sum _{k=D}^{N}{\frac {k!}{(k-D)!}}=D!\sum _{k=D}^{N}{\binom {k}{D}}=D!\sum _{k=0}^{N-D}{\binom {k+D}{D}}=D!{\binom {N+1}{D}}={\frac {(N+1)!}{(N+1-D)!}}$

Your function becomes

• $(N+1)\left({\frac {D}{2}}+{\frac {M-D}{D(N-D)!(N+1-D)!}}\right)$

Bo Jacoby (talk) 09:41, 23 December 2008 (UTC).

Joeldl, can you explain how you derived your expression

${\frac {D(N+1)}{2}}+{\frac {M-D}{D(N!)(N-D)!}}\sum _{k=D}^{N}{\frac {k!}{(k-D)!}}$

Is it exact, or is it an approximation for M<<N ? Gandalf61 (talk) 09:21, 23 December 2008 (UTC)

It's exact. I'll get back to you in a bit, Gandalf.

Bo Jacoby, I think it's still wrong, but thanks for the idea, because I think the sum is

• $\sum _{k=D}^{N}{\binom {k}{D}}={\binom {N+1}{D+1}}$.

I get it: you count the number of D + 1 element subsets of {1,...,N + 1} by counting for each k how many of those subsets have k + 1 as their maximum. Joeldl (talk) 10:07, 23 December 2008 (UTC) . (Joeldl, you are right again. Bo Jacoby (talk) 22:47, 23 December 2008 (UTC).)

Actually, I screwed up the formula too. What I did was say that the thing we're trying to maximize is

• $D{\frac {N+1}{2}}+(M-D)E_{N,D}$

where E_N,D is the expectancy of the maximum of a randomly chosen D-element subset of {1,...,N}. The number of sets with maximum equal to k is ${\binom {k-1}{D-1}}$, so

• $E_{N,D}={\frac {\sum _{k=D}^{N}{k{\binom {k-1}{D-1}}}}{\binom {N}{D}}}={\frac {D(N-D)!}{N!}}\sum _{k=D}^{N}{\frac {k!}{(k-D)!}}$

and this can be further simplified, as we now know. So my formula was off. Joeldl (talk) 10:35, 23 December 2008 (UTC)

Actually, E_D,N simplifies to (N + 1)D / (D + 1). There must be a simpler argument for this! Joeldl (talk) 10:43, 23 December 2008 (UTC)

This means that the function to be maximized is

• $(N+1)[D/2+(M-D)D/(D+1)]$.

This shows that the optimal D depends only on M and not on N, and is one of the two integers closest to sqrt(2M + 2) - 1.

Now we need to figure out a simple argument for why this didn't depend on N. Joeldl (talk) 10:49, 23 December 2008 (UTC)

The preceding calculations may be intimidating, so let's reformulate the question. Basically, the question is this: Choose a D-element subset of {1,...,N} at random. Prove in a simple way that the maximum of the subset will have as its average value (N + 1)D / (D + 1). Joeldl (talk) 21:12, 23 December 2008 (UTC)

Okay, I think I've got it. Take a D-element subset T with maximum k. The average value of an element of a subset T of this kind, other than k itself, is the average of 1,...,k - 1, namely k / 2. So for a subset T with maximum k, the sum of all the elements of T will, on average, be (D - 1)k / 2 + k = (D + 1)k / 2. Thus, for an arbitrary random D-element subset T, the average sum of its elements will be (D + 1) / 2 times its average maximum. But the average sum of the elements is D times the average value of an element, which is (N + 1)/2. So the average maximum is D(N + 1) / 2 ÷ (D + 1) / 2 = (N + 1)D / (D + 1). This computes E_N,D above and leads to a solution. Joeldl (talk) 21:44, 23 December 2008 (UTC)

Btw, the answer is D = sqrt(2(M+1)) - 1... —Preceding unsigned comment added by 65.92.236.87 (talk) 06:45, 25 December 2008 (UTC)

Not exactly. sqrt(2M + 2) - 1 isn't always an integer, so that can't be the answer. As mentioned above, D will be one of the two integers closest to sqrt(2M + 2) - 1 if this last number is < N (and it would take some extra work to find out which one it would be for a given M). Otherwise D = N. Joeldl (talk) 20:38, 25 December 2008 (UTC)

Socks in drawer problem

I'm working through some probability problems and would appreciate help with this one: "There are 10 red socks and 20 blue socks in a drawer. If socks are pulled out at random, how many must be done for it to be more likely than not that all of the red ones have been chosen?" I reasoned that if n (>= 10) socks in all were to be chosen and 10 of them were to be red, then the remaining ones had to be blue which could be done in 20 C n-10 ways. The number of ways of choosing n socks from 30 is 30 C n, so the probability of picking all 10 red ones in n draws is p(n) = (20 C n-10)/(30 C n). Is this right so far?

Putting the expression another way, I got that p(n) = (20.19.18...)/(30.29.28...), with 30-n terms in numerator and denominator. Is this right? To get this to > 0.5 required n=29, as I calculated that p(28)=38/87 and p(29)=2/3. Is this right, too, and is there a better way of getting the required value of n than arithmetic evaluation?→86.132.165.135 (talk) 17:16, 21 December 2008 (UTC)

Sooner or later arithmetic evaluation would be necessary, but there is a slightly easier approach for this particular problem. Consider: what is the most number of socks that you can draw out of the drawer, so that there is more than a 1/2 chance of drawing only blue socks? Eric. 68.18.63.75 (talk) 18:33, 21 December 2008 (UTC)

Using the binomial coefficient notation: The probability to draw $i$ red socks out of $n$ socks in the sample is ${\tbinom {10}{i}}{\tbinom {20}{n-i}}/{\tbinom {30}{n}}$. So the probability to draw $10$ red socks out of $n$ socks in the sample is

$p(n)={\tbinom {10}{10}}{\tbinom {20}{n-10}}/{\tbinom {30}{n}}={\frac {n(n-1)(n-2)(n-3)(n-4)(n-5)(n-6)(n-7)(n-8)(n-9)}{30\cdot 29\cdot 28\cdot 27\cdot 26\cdot 25\cdot 24\cdot 23\cdot 22\cdot 21}}.$

Due to cancellation of factors it is easy to evaluate

$p(30)={\frac {30\cdot 29\cdot 28\cdot 27\cdot 26\cdot 25\cdot 24\cdot 23\cdot 22\cdot 21}{30\cdot 29\cdot 28\cdot 27\cdot 26\cdot 25\cdot 24\cdot 23\cdot 22\cdot 21}}=1\,$,

$p(29)={\frac {29\cdot 28\cdot 27\cdot 26\cdot 25\cdot 24\cdot 23\cdot 22\cdot 21\cdot 20}{30\cdot 29\cdot 28\cdot 27\cdot 26\cdot 25\cdot 24\cdot 23\cdot 22\cdot 21}}={\frac {20}{30}}={\frac {2}{3}}>{\frac {1}{2}}$

$p(28)={\frac {28\cdot 27\cdot 26\cdot 25\cdot 24\cdot 23\cdot 22\cdot 21\cdot 20\cdot 19}{30\cdot 29\cdot 28\cdot 27\cdot 26\cdot 25\cdot 24\cdot 23\cdot 22\cdot 21}}={\frac {20\cdot 19}{30\cdot 29}}<{\frac {1}{2}}.$

Bo Jacoby (talk) 03:16, 22 December 2008 (UTC).

PS. The approximation $\scriptstyle p(n)\approx \left({\frac {20}{30}}\right)^{30-n}$ makes it possible to solve $\scriptstyle p(n)=0.5$ analytically: $\scriptstyle n\approx 30-{\frac {\log(2)}{\log(3/2)}}\approx 28.290489.$ This is perhaps "a better way of getting the required value of n than arithmetic evaluation". Bo Jacoby (talk) 10:59, 22 December 2008 (UTC).

Thanks for the replies - it appears that my analysis of the problem was OK. →86.160.104.208 (talk) 20:16, 23 December 2008 (UTC)

Surely, your result is correct, but somehow your analysis didn't quite convince you ! Note that the function p(n) is characterized by the following properties

1. p(n) = 0 for n = 0,1,2,3,4,5,6,7,8,9 and p(30) = 1.
2. p is a polynomial of degree 10.

The first property is shown without algebra while the second property is perhaps less evident. The solution to the 10th degree equation p(n) = 1/2 cannot be expressed in closed form, while the solution to (3/2)ⁿ⁻³⁰ = 1/2 is elementary. Bo Jacoby (talk) 23:29, 23 December 2008 (UTC).

Elegant... as to the solution of p(n) = 1/2, or better of $\scriptstyle p(n)\leq 1/2<p(n+1),\ n\in \mathbb {N}$, I trust more the explicit arithmetic evaluation. As far as I understand the symbol $\approx$ here has only a qualitative meaning and does not tell us how close is n to the solution of the approximated equation. Making the computation rigorous would take more work than the arithmetic evaluation...--PMajer (talk) 14:43, 24 December 2008 (UTC)

Thanks for showing me the \scriptstyle feature! The problem $\scriptstyle p(n-1)\leq 1/2<p(n)$ is solved, and it seems pointless to keep beating a dead horse. However it may be nice to be able to find the solution $\scriptstyle n\approx 28.315016$ to the equation $\scriptstyle p(n)=1/2$. The equation of degree 10 in $\scriptstyle n$

$\prod _{i=0}^{9}{\frac {n-i}{30-i}}={\frac {1}{2}}$

can due to symmetry be reduced to an equation of degree 5 in $\scriptstyle r_{n}^{2}\,$,

$\prod _{i=0}^{4}{\frac {r_{n}^{2}-r_{i}^{2}}{r_{30}^{2}-r_{i}^{2}}}={\frac {1}{2}}$

where $\scriptstyle r_{i}=2i-9$ . Note that $\scriptstyle r_{9-i}=-r_{i}.\,$

The derivation of the simplification is

${\begin{aligned}\prod _{i=0}^{9}{\frac {n-i}{30-i}}&=\prod _{i=0}^{9}{\frac {(n-{\frac {9}{2}})-(i-{\frac {9}{2}})}{(30-{\frac {9}{2}})-(i-{\frac {9}{2}})}}=\prod _{i=0}^{9}{\frac {(2n-9)-(2i-9)}{(2\cdot 30-9)-(2i-9)}}=\prod _{i=0}^{9}{\frac {r_{n}-r_{i}}{r_{30}-r_{i}}}\\&=\left(\prod _{i=0}^{4}{\frac {r_{n}-r_{i}}{r_{30}-r_{i}}}\right)\cdot \left(\prod _{i=5}^{9}{\frac {r_{n}-r_{i}}{r_{30}-r_{i}}}\right)\\&=\left(\prod _{i=0}^{4}{\frac {r_{n}-r_{i}}{r_{30}-r_{i}}}\right)\cdot \left(\prod _{i=0}^{4}{\frac {r_{n}-r_{9-i}}{r_{30}-r_{9-i}}}\right)\\&=\left(\prod _{i=0}^{4}{\frac {r_{n}-r_{i}}{r_{30}-r_{i}}}\right)\cdot \left(\prod _{i=0}^{4}{\frac {r_{n}+r_{i}}{r_{30}+r_{i}}}\right)\\&=\prod _{i=0}^{4}{\frac {(r_{n}-r_{i})(r_{n}+r_{i})}{(r_{30}-r_{i})(r_{30}+r_{i})}}=\prod _{i=0}^{4}{\frac {r_{n}^{2}-r_{i}^{2}}{r_{30}^{2}-r_{i}^{2}}}\\&={\frac {(r_{n}^{2}-81)(r_{n}^{2}-49)(r_{n}^{2}-25)(r_{n}^{2}-9)(r_{n}^{2}-1)}{2520\cdot 2552\cdot 2576\cdot 2592\cdot 2600}}.\end{aligned}}$

Bo Jacoby (talk) 15:02, 25 December 2008 (UTC).

Nice... well, in my experience no dead horse is so dead that sooner or later he raises and give me back everything. So I will be thinking a little more to your equation p(x)=y, staying ready to run ;) --PMajer (talk) 21:33, 26 December 2008 (UTC)

I simplified (and corrected!) my simplification above a little. (The horse was not quite dead!) Note that if you can solve the degree 10 equation right away, then the simplification is not necessary, and if you cannot solve the degree 5 equation anyway, then the simplification is not sufficient. However, the precision of standard floating point computation may sometimes be sufficient for evaluating a degree 5 polynomial but not for evaluating a degree 10 polynomial. So simplification is good strategy. Bo Jacoby (talk) 08:58, 27 December 2008 (UTC).

Assuming that you want the solution expressed by formulas that can be evaluated by pre-computer tools such as pencil and slide rule. Then an approximation is called for. The degree 5 polynomial $\scriptstyle q(x)$ satisfy $\scriptstyle q(1)=q(9)=q(25)=q(49)=q(81)=0$ and $\scriptstyle q(r_{30}^{2})=q(2601)=1$. That means that approximately $\scriptstyle q(x)\approx \left({\frac {x-r}{2601-r}}\right)^{5}$ where $\scriptstyle r$ is chosen between $\scriptstyle 1$ and $\scriptstyle 81$, say $\scriptstyle r=41$ . The solution to $\scriptstyle \left({\frac {x-41}{2601-41}}\right)^{5}={\frac {1}{2}}$ is $\scriptstyle x=41+2560{\sqrt[{5}]{\frac {1}{2}}}=2270$ giving the fine result $\scriptstyle n\approx {\frac {9+{\sqrt {x}}}{2}}=28.32$. Bo Jacoby (talk) 14:25, 31 December 2008 (UTC).

Boubaker polynomials (3): Mr. Boubaker, please come and give your personal definition

I'm not an expert in special functions and orthogonal polynomials, and I confess that I never heard about "Boubaker polynomials" before. However, I suspect that there is something to rectify in the article. It states that the $\scriptstyle B_{n}$ are linear combinations of the Chebyshev polynomials; precisely, $\scriptstyle B_{m}(x)=-2T_{m}(x)+4xU_{m-1}(x)$. If so, the recursive relation should be the same as the $\scriptstyle T_{m}$ and $\scriptstyle U_{m}$, thus ${\color {Cerulean}\scriptstyle B_{m}(x)=2xB_{m-1}(x)-B_{m-2}(x)}$; but it's reported as ${\color {YellowOrange}\scriptstyle B_{m}(x)=xB_{m-1}(x)-B_{m-2}(x)}$. The generating function also does not match: if the denominator is really $\scriptstyle 1-t(t-x)$ then the stable linear recursive relation should be ${\color {Green}\scriptstyle B_{m}(x)=-xB_{m-1}(x)+B_{m-2}(x)}$. Finally, an explicit formula is quoted, giving $\scriptstyle B_{m}$ as linear combination of m-th powers of $\scriptstyle x+{\sqrt {x^{2}-1}}$ and $\scriptstyle x-{\sqrt {x^{2}-1}}$; in this case we would have ${\color {Magenta}\scriptstyle B_{m}(x)=2xB_{m-1}(x)-B_{m-2}(x)}$. Discouraged, I made no further experiments... Well, I've just had a glance to the list of colors, there are so beautiful ones that I am tempted to revise the whole arcticle. But let us give an end to this Carnival... so, which one is the right formula? PMajer (talk) 23:06, 21 December 2008 (UTC)

You may want to ask User:Luoguozhang who appears to be largerly responsible for this fairly new article Nil Einne (talk) 18:26, 22 December 2008 (UTC)

You may also want to mention this at talk:Boubaker polynomials. Michael Hardy (talk) 23:42, 22 December 2008 (UTC)

Done. Personally, I think that definitions in mathematics non sint multiplicanda praeter necessitatem, but it is right that people be free to give names to any object if they wish.--PMajer (talk) 12:57, 23 December 2008 (UTC)