tag:blogger.com,1999:blog-3722233.post7318863541466872803..comments2020-02-16T18:25:33.023-05:00Comments on Computational Complexity: Solution to the infinite hat problem/a point/a new problemLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger18125tag:blogger.com,1999:blog-3722233.post-56066576782397947952016-08-01T00:55:31.664-04:002016-08-01T00:55:31.664-04:00This reminded me of a result of Hardin and Taylor ...This reminded me of a result of Hardin and Taylor (https://www.math.upenn.edu/~ted/203S10/References/peculiar.pdf) that I came across on Steven Landsburg's blog where they use the axiom of choice to show the following: <br /><br />You are given an arbitrary function f from reals to reals (need not be continuous, differentiable etc; any function). Just an arbitrary function). Now suppose someone gives you the values of f from [-infinity, alpha) and you are supposed to find the value of f(alpha). Can one find hope to find a strategy to predict the value of f at alpha given the values of all beta < alpha? <br /><br />Thm: [Hardin-Taylor] There exists a strategy such that for an arbitrary function f: R -> R, the number of points alpha where the strategy will yield the wrong answer is countable. In other words, for an arbitrary function f, if the point alpha is chosen uniformly, the strategy outputs the right answer with probability 100%. <br /><br />The paper actually proves more, and the proof is the most beautiful example of Occam's razor (basically the strategy is just look at the set of all functions that extend the observed values, and answer according to the "smallest" (via well-ordering)). <br /><br />I felt this puzzle is a weaker form of this theorem but couldn't figure out the solution. <br /><br />RPhttps://www.blogger.com/profile/13391693683892043563noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-32527075935596752692016-07-19T21:48:17.067-04:002016-07-19T21:48:17.067-04:00Right, I understood that. I'm still skeptical...Right, I understood that. I'm still skeptical--I'd need to be convinced you can put a probability measure on which of the columns has the wrong answer. More details in my reply to the subsequent post.Lukehttps://www.blogger.com/profile/08867175989749027625noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-73703909355226197992016-07-19T09:12:51.601-04:002016-07-19T09:12:51.601-04:00The solution to the hat problem does not work.
Co...The solution to the hat problem does not work.<br /><br />Consider the equivalence class where exactly half<br />of the people have Red hats and the other half <br />have Blue hats. (The easiest way to generate this<br />is by flipping a coin independently each time and<br />decicde the color of the hat.)<br />The representative of this class, whoever he maybe,<br />will differ with an infinite number of participants<br />by a finite number of hat colors!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-32167932634392707802016-07-18T05:53:02.344-04:002016-07-18T05:53:02.344-04:00Yes: the probability distribution is on the column...Yes: the probability distribution is on the column that Bob select not to open. If he splits the boxes into m columns, only 1 of them *may* yield a wrong answer, so if he selects the column uniformly he has at least (m-1)/m chance of success. If he select the wrong column then of course we cannot define a probability of success in this case. Anonymoushttps://www.blogger.com/profile/18003763376837019360noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-63162570795891843362016-07-17T11:49:10.303-04:002016-07-17T11:49:10.303-04:00Can you actually put a probability measure on that...Can you actually put a probability measure on that solution though? My suspicion is no, in which case you can't say it's 99% certainty.Lukehttps://www.blogger.com/profile/08867175989749027625noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-72865615354334096352016-07-17T10:13:34.006-04:002016-07-17T10:13:34.006-04:00In your answer, there are uncountably infinite equ...In your answer, there are uncountably infinite equivalence classes, so even if players remember all the classes, to match the right representative of the right equivalence class could be uncomputable.<br />Am I right?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-77639008203777017972016-07-17T09:52:32.232-04:002016-07-17T09:52:32.232-04:00I saw this box problem in a logic exam :)
Here is...I saw this box problem in a logic exam :)<br /><br />Here is the solution (spoiler): Bob fixes once and for all his<br />representative $r$. Now he splits the boxes into 100 columns, fixes a number $1 \le j \le 100$ and opens all the boxes in the other 99 columns $i \ne j$. For each of those columns $i$, Bob can check at which point $n_i$ his representative coincide with the values of the boxes. Then he asks to open all the boxes in column $j$ except the $max_{i \ne j}(n_i)$ one. He then uses $r$ to guess the value of this box. This strategy wins as long as $n_j \le max_{i \ne j}(n_i)$, so Bob succeeds at least 99% of the time.<br />Anonymoushttps://www.blogger.com/profile/18003763376837019360noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-44819579446832124232016-07-17T00:40:52.332-04:002016-07-17T00:40:52.332-04:00An argument along the lines of the solution of the...An argument along the lines of the solution of the hat problem above seems to go through just fine but is meaningless because it allows finite errors and this problem is about a finite set of size one.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-48675410504146043672016-07-16T13:36:34.790-04:002016-07-16T13:36:34.790-04:00I read the statement of the problem as follows:
&...I read the statement of the problem as follows:<br /><br />"There exists Bob-strategy B such that, for all Alice-strategies A, B succeeds."<br />This is clearly false. Given a fixed Bob-strategy B, one can construct an Alice-strategy to defeat it -- namely, look at the boxes opened by B, see what B's prediction is, and choose to put a different value into the box.<br /><br />Alternatively, one may ask:<br />"For all alice-strategies A, there exists a Bob-strategy B that succeeds against A"<br />But what is the definition of an Alice-strategy in this context? Is it a random distribution on box contents?Davidhttps://www.blogger.com/profile/13818371550669837787noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-14384235877975000662016-07-15T18:32:32.446-04:002016-07-15T18:32:32.446-04:00Would any solution of it being possible really sat...Would any solution of it being possible really satisfy you? :)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-12943853385410038072016-07-14T23:20:51.384-04:002016-07-14T23:20:51.384-04:00A note about the hat problem: If instead of Axiom ...A note about the hat problem: If instead of Axiom of Choice you use a less-commonly investigated Set Theory where all sets are measurable, then the answer reverses: The hat colours can all be drawn independently and uniformly at random, and a probabilistic analysis (which is doable, since now all sets are measurable and hence describable outcomes are events with probabilities) will give you Probability 0 for guessing all but a finite number of hat colours.Eldar Fischernoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-81985662814782610602016-07-14T22:11:56.349-04:002016-07-14T22:11:56.349-04:00I think I'd rather be Chris. Chris plays fun ...I think I'd rather be Chris. Chris plays fun games with his/her friends.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-90072711753563713282016-07-14T21:29:27.584-04:002016-07-14T21:29:27.584-04:00The infinite hats solution does NOT satisfy me.The infinite hats solution does NOT satisfy me.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-73967496691521637772016-07-14T13:23:01.974-04:002016-07-14T13:23:01.974-04:00Alice could put a 1 in every box if she wanted to....Alice could put a 1 in every box if she wanted to.<br />She need not use all or even most of the numbers.<br />GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-3238324456321027712016-07-14T10:33:07.655-04:002016-07-14T10:33:07.655-04:00Very nice problem - it feels like a paradox to me....Very nice problem - it feels like a paradox to me.<br />On the one hand if Alice i.i.d. randomizes when choosing the natural number in each box, the number from any other box opend should not contain any information about the numbers in boxes not yet opend. This seems to suggest Alice can make her chance of winning arbitrarily close to one e.g. by choosing a sufficiently large number N and then uniformaly and indpendetly chosing random numbers from 1 to N for each box. <br />On the other hand, using the axiom of choice, an argument along the lines of the solution of the hat problem above seems to go through just fine and Bob can make the probability of winning arbitrarily close to one. <br />I am looking forward to the solution.<br /><br /> FHnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-35086739939209345262016-07-14T09:42:52.142-04:002016-07-14T09:42:52.142-04:00Since the natural numbers are countably infinite, ...Since the natural numbers are countably infinite, and since Bob has left only a finite number of boxes, does this mean the only natural numbers not seen yet reside in the unopened boxes? If so, I think Bob can calculate the exact probability of his guess.<br /><br />Bob guesses a number he has not already seen.<br /><br />Bob calculates the probability of his chosen number being in the chosen box as being 1 / (number of unopened boxes).<br /><br />Well, if the finite number of unopened boxes is arbitrary and left up to Bob, could he not leave only one unopened box and by the above formula have probability of unity for guessing the right answer?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-46833830479246913222016-07-14T09:37:42.333-04:002016-07-14T09:37:42.333-04:00I've added a clarification; however the answer...I've added a clarification; however the answer is that Alice can put any number in any box without restriction.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-92063152459156091572016-07-14T09:34:58.322-04:002016-07-14T09:34:58.322-04:00Two questions: are all the numbers Alice put in th...Two questions: are all the numbers Alice put in the boxes pairwise unique? And does Alice place every natural number in a box, or is she free to use a subset (say, just the odd numbers, or just the primes)?Abigailhttps://www.blogger.com/profile/14202894297731782841noreply@blogger.com