egs@ulysses.UUCP (08/29/83)
I believe I may have come up with another strategy for the "largest of 10 numbers problem" that differs a little bit from the optimal M-strategy described previously. My argument may be specious, however, so I would appreciate corrections if any. Essentially, you apply the M-strategy to only the positive numbers of the 10 chosen ones. In the case of 10 numbers, I think this strategy yields a 0.4137 chance of getting the highest number using M=1 (as opposed to a 0.3987 chance following the straight M-strategy with M=3). I arrive at this result as follows: The ten numbers may be grouped into positive and negative sets with the following chances: case 0. 10 neg, 0 pos C(10,0)/2^10 1/1024 case 1. 9 neg, 1 pos C(10,1)/2^10 10/1024 case 2. 8 neg, 2 pos C(10,2)/2^10 45/1024 . . . case 10.0 neg, 10 pos C(10,10)/2^10 1/1024 Applying the modified M-strategy to each of these cases, you see that when case 0 occurs, the modified strategy will win by default 1/10 of the time since the last number will always be chosen. In case 1, you can get it right 1/10! of the time, since the positive number will occur in last place this many times (this case can be ignored for all practical purposes). For case j>1, you will guess right F(j,1) times (where F(N,M) was defined in my previous note as the chance of the straight M strategy working on N numbers). Multiplying these coefficients with the probability for each case and summing them gives a 0.4137 chance of guessing the right number using this modified M-strategy for N=10. I haven't given much thought to what happens as N gets large, but my gut feeling is that the optimal modified M-strategy for N numbers will perform no better than the straight M-strategy, and will most likely get close to a 1/e chance as well. Ed Sheppard BTL @ MH