tag:blogger.com,1999:blog-3722233.post115586886927911907..comments2024-11-13T15:38:29.005-06:00Comments on Computational Complexity: Guess the maxLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger8125tag:blogger.com,1999:blog-3722233.post-1156189779378398672006-08-21T14:49:00.000-05:002006-08-21T14:49:00.000-05:00Just to close out this now-dormant thread, here's ...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.<BR/><BR/>Pick 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).<BR/><BR/><A HREF="http://en.wikipedia.org/wiki/Benford's_law" REL="nofollow">Answer here</A>.<BR/><BR/>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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1156097877805223372006-08-20T13:17:00.000-05:002006-08-20T13:17:00.000-05:00Claire is right, especially in saying that "the me...Claire is right, especially in saying that "the method works iff the [guesser's] distribution has full support".<BR/><BR/>Fearlessly accepting the risk of looking like "the <A HREF="http://en.wikipedia.org/wiki/Rodney_Dangerfield" REL="nofollow">Rodney Dangerfield</A> of complexity theory", I <B>tried</B> 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:<BR/><BR/>distList = {<BR/> BetaDistribution[1,1],<BR/> CauchyDistribution[1,1],<BR/> ChiDistribution[1],<BR/> ChiSquareDistribution[1]<BR/> ExponentialDistribution[1],<BR/> ExtremeValueDistribution[1,1],<BR/> FRatioDistribution[1,1],<BR/> GammaDistribution[1,1],<BR/> HalfNormalDistribution[1],<BR/> LaplaceDistribution[1,1],<BR/> LogNormalDistribution[1,1],<BR/> LogisticDistribution[1,1],<BR/> NoncentralChiSquareDistribution[1,1],<BR/> NoncentralFRatioDistribution[1,1,1],<BR/> NoncentralStudentTDistribution[1,1],<BR/> NormalDistribution[1,1],<BR/> ParetoDistribution[1,1],<BR/> RayleighDistribution[1],<BR/> StudentTDistribution[1],<BR/> UniformDistribution[-1,1],<BR/> WeibullDistribution[1,1],<BR/> };<BR/><BR/>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".<BR/><BR/>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!<BR/><BR/>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)?<BR/><BR/>The instructive answer, will IMHO help the solver appreciate the informatic basis for Scott Aaronson's very interesting <A HREF="http://www.scottaaronson.com/blog/" REL="nofollow">Quantum Learning Theorem</A>. <BR/><BR/>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.Doug Mouncehttps://www.blogger.com/profile/10917054134517643425noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1156037792854956532006-08-19T20:36:00.000-05:002006-08-19T20:36:00.000-05:00Hmmm, my mistake. John's method would work, say in...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?...)Alexhttps://www.blogger.com/profile/10531171312916299127noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1156024365063032742006-08-19T16:52:00.000-05:002006-08-19T16:52:00.000-05:00I guess he's right if for any "number" the probabi...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.Alexhttps://www.blogger.com/profile/10531171312916299127noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1155943640888879112006-08-18T18:27:00.000-05:002006-08-18T18:27:00.000-05:00Although I'm reasoning by intuition rather than m...Although I'm reasoning by intuition rather than mathematics, wouldn't the following also work:<BR/><BR/>Before picking either hand, choose a random number yourself (technicality: from any distribution, you like, provided it has finite variance).<BR/><BR/>Assume your number is the number on the hand you don't see. Choose accordingly.Doug Mouncehttps://www.blogger.com/profile/10917054134517643425noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1155931142897360372006-08-18T14:59:00.000-05:002006-08-18T14:59:00.000-05:00Very nice. This is a perfect example of a problem ...<B>Very</B> nice. This is a perfect example of a problem where a randomized algorithm really helps.<BR/><BR/>I 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?Alexhttps://www.blogger.com/profile/10531171312916299127noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1155919763016922292006-08-18T11:49:00.000-05:002006-08-18T11:49:00.000-05:00Hmmm, the best I can come up is with the following...Hmmm, the best I can come up is with the following strategy. Of course, a lot depends on how we interpret the question.<BR/><BR/>If 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.<BR/><BR/>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.Alexhttps://www.blogger.com/profile/10531171312916299127noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1155912412950970012006-08-18T09:46:00.000-05:002006-08-18T09:46:00.000-05:00If you had three hands, I think you would have oth...If you had three hands, I think you would have other concerns beyond number guessing puzzles.Hughhttps://www.blogger.com/profile/08767952337717767032noreply@blogger.com