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.
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.
I 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.
ReplyDeleteHmmm, 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.