tag:blogger.com,1999:blog-3722233.post6098480672803996666..comments2024-06-24T15:24:01.378-05:00Comments on Computational Complexity: I will be on instagram/If you have two reals in a box- Answer (Guest Post by David Marcus) Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger10125tag:blogger.com,1999:blog-3722233.post-15370846342844863052022-03-03T19:04:04.750-06:002022-03-03T19:04:04.750-06:00I think the problem is older than that paper.I think the problem is older than that paper.David Marcushttps://www.blogger.com/profile/07084520656051241766noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-15826356200671790502022-03-03T18:42:25.678-06:002022-03-03T18:42:25.678-06:00I had not seen that. He doesn't say that he or...I had not seen that. He doesn't say that he originated the problem.David Marcushttps://www.blogger.com/profile/07084520656051241766noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-3693876437306820282022-03-02T21:59:18.903-06:002022-03-02T21:59:18.903-06:00regarding (b).
https://isl.stanford.edu/people/cov...regarding (b).<br />https://isl.stanford.edu/people/cover/papers/paper73.pdf<br />Seems like a pointer. The link to the optimal stopping problem<br />is mentioned. @Marcus did you look into this?Evangelos Georgiadis (EG)noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-51994946839722442462022-03-02T21:19:32.501-06:002022-03-02T21:19:32.501-06:00Are you asking how to prove that the solutions wor...Are you asking how to prove that the solutions work?<br /><br />Strategy one: Let p be the probability that x is between the two numbers. So, p > 0. If x is between the two numbers, then you end up with the larger number. Otherwise, you have probability 1/2 of ending up with the larger number. So, your overall probability of ending up with the larger number is p + ( 1 - p ) ( 1/2 ) = 1/2 + p ( 1 - 1/2 ) = 1/2 + p/2 > 1/2.<br /><br />Strategy two: Let a be the smaller number and b be the larger number. If you select a from the box, you have probability 1 - f(a) of ending up with the larger number. If you select b from the box, you have probability f(b) of ending up with the larger number. So, your overall probability of ending up with the larger number is ( 1 - f(a) ) / 2 + f(b) / 2 = 1/2 + ( f(b) - f(a) ) / 2 > 1/2.<br /><br />I don't know the original source of the puzzle, nor does the person that I learned the puzzle from.David Marcushttps://www.blogger.com/profile/07084520656051241766noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1716527487078270142022-03-02T20:48:35.059-06:002022-03-02T20:48:35.059-06:00Intriguing. A few clarification questions on this....Intriguing. A few clarification questions on this.<br />(a) how would you go about proving this? too obvious?<br />(b) what is the provenance of this problem?<br />A previous commentator stated that the late Tom Cover covered this (and perhaps a more generalized) problem in a conference? source/proceedings? <br />Evangelos Georgiadis (EG)noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-66763709289662649792022-02-25T10:12:23.006-06:002022-02-25T10:12:23.006-06:00I'd rather say the two strategies are "re...I'd rather say the two strategies are "related" rather than being the "same". I noted that in my draft, but Bill edited it out!David Marcushttps://www.blogger.com/profile/07084520656051241766noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-49367786226852870082022-02-25T09:05:23.388-06:002022-02-25T09:05:23.388-06:00Consider, e.g., 1.7 and 2.0, then you will always ...Consider, e.g., 1.7 and 2.0, then you will always choose 1.7 so your probability of winning is zero. I guess that the point of the problem was that any deterministic strategy is not better than 1/2 in the worst case while an easy probabilistic one may be better than 1/2 uniformly.<br />Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-31541566558190607602022-02-25T08:54:05.785-06:002022-02-25T08:54:05.785-06:00Knowing that strategy, always having the numbers b...Knowing that strategy, always having the numbers be 1 and 2 gives you a 50/50 chance.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-79569052222655874912022-02-25T04:10:21.359-06:002022-02-25T04:10:21.359-06:00What about picking one of the two with probability...What about picking one of the two with probability 1/2, and if its fractional part is >= 0.5 (<= 0.5 for negative numbers) then keep it, otherwise pick the other?<br />(I'm totally unfamiliar with probabilities)Marzio De Biasihttps://www.blogger.com/profile/18441670787376943932noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-73977471434252999932022-02-24T14:19:22.906-06:002022-02-24T14:19:22.906-06:00These were the ones given in the two comments of t...These were the ones given in the two comments of the original post.<br /><br />Also, those are not two different strategies but the same one said in two different ways. The f in the second strategy is the cdf of the distribution from the first strategy. Anonymousnoreply@blogger.com