On Friday I will be flying back to the East Coast. Here is a puzzle to keep blog readers occupied while I am traveling.
I write two different numbers, one on each hand. You choose one of my hands at random, I show you the number on that hand. You now guess whether the number you've seen is larger than the number you haven't seen. Find a strategy for guessing such that, no matter what two numbers I write, you have greater than a 50% chance of being correct. (Borrowed from there.)
What if I have three hands and at any time you can choose to either keep the number I show you or discard it and move on to choosing another hand?
Comments page (Usual comments link does not work properly, use this instead.)
Claire
If you had three hands, I think you would have other concerns beyond number guessing puzzles.
ReplyDeleteHmmm, the best I can come up is with the following strategy. Of course, a lot depends on how we interpret the question.
ReplyDeleteIf by "numbers", you mean positive integers (1, 2, 3, ...), if we get a number > 1 on the first hand, choose that hand. Otherwise choose the second hand.
For 3 hands, always exclude the first hand. If the number in the second hand is bigger than the number in the first hand, choose the second hand. Otherwise choose the third hand. It's easy to see that we have 50% chances of winning with that strategy. To go slightly beyond 50% , modify the strategy to choose the third hand in the case where we got 1, 2 in the first 2 hands.
I have been out of probability class for a long time now, but this is my crack at it ...
ReplyDeleteAssuming positive integers, I would use the strategy to always conclude that the number I have seen is less than the number I haven't seen. I say this because given any number N on then number line, seen on the first hand, there is 1/N-1 probability that the number we haven't seen will be smaller than the one that we have. There are N-1 choices that are < N. The probability that the number is larger than N, is infinite, because the number line goes to infinitity. So there will always be a greater probability that the number we haven't seen is greater than N. Always chosing less than, gives you more than a 50% chance of being correct when we are calculating the probability of the strategy.
For 3 hands, I would use the same strategy. The probabilities would change slightly - so if the first number is N, and the next number is < N, then the probability that the 3rd hand will show a number < N is 1/N-2. But if the 2nd number, P, is > N, then the probability that the 3rd number is a smaller number is 1/P-2. Still, the integers go to infiniity, so there is always a greater probability that the 3rd hand will reveal a larger number. So again, always choosing that the hands you see are less than the ones you have not seen yeilds the highest strategic probability.
Let f be a stritly increasing function from the numbers (whatever is meant by "numbers") to the open interval (0,1). It doesn't matter which.You can even let your adversary choose one.
ReplyDeleteWhen you see the number x, guess that it is the larger number with probability f(x), otherwise guess that the other number is larger.
If a is the smaller number and b is the larger, your probability of winning is 1/2f(b) + 1/2(1-f(a)) = 1/2(1+f(b)-f(a)) which is strictly greater than 1/2.
It may not be much greater than 1/2.
Let f be a stritly increasing function from the numbers to the open interval (0,1). You can even let your adversary choose one.
ReplyDeleteBut if you do, it is vital that she choose before you choose which hand to look at.
Very nice. This is a perfect example of a problem where a randomized algorithm really helps.
ReplyDeleteI have just a small doubt. Does such function necessarily exist? This would imply that any totally ordered set has at most the cardinality of the set of reals. Is that true?
Although I'm reasoning by intuition rather than mathematics, wouldn't the following also work:
ReplyDeleteBefore picking either hand, choose a random number yourself (technicality: from any distribution, you like, provided it has finite variance).
Assume your number is the number on the hand you don't see. Choose accordingly.
Ralph has the right solution. John Sidles is also right if he chooses his random number from a distribution where every number has some chance of being chosen.
ReplyDeleteI guess he's right if for any "number" the probability that that number is chosen is > 0. I mean his method wouldn't work if the set of numbers is the set of reals in (0, 1), say, even if he chooses the uniform distribution.
ReplyDeleteYes, his method still works if he chooses the uniform distribution over [0..1]. In general the method works iff the distribution has full support.
ReplyDeleteSidles and Ralph's methods are actually equivalent.
Hmmm, my mistake. John's method would work, say in [0..1], as long as the distribution he chooses is such that for any a, b in [0..1] , with a < b: P(a < x < b) > 0. (Is it that what "full support" means?...)
ReplyDeleteClaire is right, especially in saying that "the method works iff the [guesser's] distribution has full support".
ReplyDeleteFearlessly accepting the risk of looking like "the Rodney Dangerfield of complexity theory", I tried the "pick from a typical distribution" method, by randomly selecting numbers, from randomly selected distributions, using the following comprehensive list of Mathematica's built-in distributions:
distList = {
BetaDistribution[1,1],
CauchyDistribution[1,1],
ChiDistribution[1],
ChiSquareDistribution[1]
ExponentialDistribution[1],
ExtremeValueDistribution[1,1],
FRatioDistribution[1,1],
GammaDistribution[1,1],
HalfNormalDistribution[1],
LaplaceDistribution[1,1],
LogNormalDistribution[1,1],
LogisticDistribution[1,1],
NoncentralChiSquareDistribution[1,1],
NoncentralFRatioDistribution[1,1,1],
NoncentralStudentTDistribution[1,1],
NormalDistribution[1,1],
ParetoDistribution[1,1],
RayleighDistribution[1],
StudentTDistribution[1],
UniformDistribution[-1,1],
WeibullDistribution[1,1],
};
After 10^5 trials, the mean gain was 0.32596 -- so the method definitely yields an advantage whenever everyone picks from an "ordinary distribution of distributions".
The above calculation is full of interest. E.g., why select unity as the"ordinary" value of a distribution parameter, instead of (say) a google? A long essay could be written on this topic!
Instead, I will pose as a question, what "distribution of distributions" can the hand-writer adopt that will defeat the guesser FAPP (for all practical purposes)?
The instructive answer, will IMHO help the solver appreciate the informatic basis for Scott Aaronson's very interesting Quantum Learning Theorem.
Namely, foreknowledge that a quantum state is "interesting" is Bayesian information having similar (nonintuitive) informatic implications as knowing that a random number has been selected from an "ordinary" distribution.
Just to close out this now-dormant thread, here's an old chestnut from my undergraduate days, adapted to Claire's problem. If you haven't seen it before, you'll enjoy it.
ReplyDeletePick a random physical or mathematical constant and write its first digit on your left hand. Pick a different constant and write its first digit on your right hand. What is the guesser's optimum strategy? (assume ties don't count).
Answer here.
Oh yeah, the expected gain in the above Mathematica "distribution of distributions" list is precisely 1/3, even if "google" (or any other number) is substituted for unity as a parameter.