tag:blogger.com,1999:blog-3722233.post8773596742691138566..comments2020-01-23T21:34:59.362-05:00Comments on Computational Complexity: Solution to the Alice-Bob-Box problem. Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger10125tag:blogger.com,1999:blog-3722233.post-49071009497517626592016-07-25T00:52:32.896-04:002016-07-25T00:52:32.896-04:00Here is a nice discussion of the problem: http://m...Here is a nice discussion of the problem: http://mathoverflow.net/questions/151286/probabilities-in-a-riddle-involving-axiom-of-choicedomhttps://www.blogger.com/profile/05790539025733385232noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-71947261744549023852016-07-21T14:42:07.778-04:002016-07-21T14:42:07.778-04:00Wow, brilliant, I was completely fooled! So to sum...Wow, brilliant, I was completely fooled! So to summarize, Alice is more likely to win if they both must have a "measurable" strategy, and if not, then it doesn't make sense to ask what's more likely.domhttps://www.blogger.com/profile/05790539025733385232noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-66067459017194489582016-07-21T09:46:30.037-04:002016-07-21T09:46:30.037-04:00No, I don't like it. The solutions violate the...No, I don't like it. The solutions violate the implied rules.<br /><br />I would object to a puzzle solution that required a person to take different actions depending on whether a given TM halted or not (unless the problem statement implied that it is allowed). But the halting function definitely exists, and is a much simpler (or at least smaller) object than the choice functions used in these solutions. Evaluating it only requires countably infinite computation. I don't really know how to talk about the amount of computation required to implement these solutions, but I doubt it is countable.<br /><br />The halting function is unique, but the choice functions are *very* far from that (I'm not sure, but I think there may be one for every subset of the reals). The axiom of choice certainly does not imply that it is possible for infinitely many agents to agree on a common choice function (as required by the hat problem) by any means whatsoever, even with an uncountable amount of communication.<br />Ralph Hartleynoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-45583246579782755462016-07-20T13:14:56.020-04:002016-07-20T13:14:56.020-04:00The probability is not on the values of X and Y (w...The probability is not on the values of X and Y (which as you point out I am pretty sure are not measurable anyways). We don't give a measure of probability to the way Alice put her numbers in the box. What we do is the following: *once* Alica has put her numbers, and Bob splits into 100 columns, only one of these columns may give a wrong answer. There is no probability at all in this statement. Now if Bob selects uniformly the column he leaves unopened (this is perfectly defined on the finite set {1,...,100}), he has 99% chance of not getting the "wrong" column.<br /><br />If I go back to the hat problem, what may be confusing is the following: assume the color is white or black and is chosen uniformly at random for each hat. Then for each set of N persons, there is an esperance of N/2 of them getting the correct color. Yet with the strategy outlined in the previous blog post over the naturals there is only a finite number of wrong calls. This simply means that the esperance is not continuous (which we would not expect: we have a simply converging sequence of functions which are not bounded by a L^1 function).<br /><br />Another way to understand the "paradox": the cardinal of a set is not continuous (where a limit of a sequence of sets is when the lim sup of their indicator function is equal to the lim inf, or in other words when the union of the intersections is equal to the intersection of the unions). Here is my favorite story that showcase this: a man earns 2 coins every day that he adds to the top of his coin stack and spends one. Should he take the one he spends on the top or on the bottom of the stack? The answer is that it should take the one on the top because if he takes the one on the bottom then the limit of the stack of coins is the empty set!Damien Roberthttps://www.blogger.com/profile/18003763376837019360noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-80086800790450380642016-07-19T21:59:21.452-04:002016-07-19T21:59:21.452-04:00I believe this is correct. The problem with the p...I believe this is correct. The problem with the presented solution is that if you try to formalize it, you'll find "the prob that x(8) is the largest" requires a probability measure to be assigned. But--as you may guess from using the axiom of choice--you don't have measurable sets. So it's not correct to speak of probabilities of the event. <br /><br />Despite having 100 symmetrical events, and knowing one of them must occur, we can't talk about probabilities of the events! We need the events to be measurable.<br /><br />The intuitive solution is correct: Alice can win 1-1/N probability for any N, by putting a uniform random number selected from 1 to N in each box. She can generate these numbers, for example, by picking a random real number between 0 and 1 and writing it in base N. The event of any box containing a particular number is a measurable set, and so we can prove that Bob has at most 1/N chance of guessing right.Lukehttps://www.blogger.com/profile/08867175989749027625noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-86262898213225362592016-07-18T18:03:19.787-04:002016-07-18T18:03:19.787-04:00There is some subtle problem, related to the relat...There is some subtle problem, related to the relation of the Choice Axiom and immeasurable sets. Take a deep breath, this one is long.<br /><br />Let's assume for now two rows, and all numbers being 0 or 1 (essentially the hats problem). Now assume that each number is independently chosen to be 0 or 1 with uniform probability. By "strategy" I mean a family of one representative from each equivalence class of almost-equal number sequence.<br /><br />Let X be the highest index mismatch in the first row, Y be the highest index mismatch in the second row.<br /><br />These look like random variables, but they are not. The existence of a strategy implies that there are immeasurable sets. In other words, it cannot be that all sets of type "X=j" are events with probabilities, as otherwise they would all be Probability 0, while their sum is Probability 1 (if X were a random variable it would always get some value...)<br /><br />Back to us: Unlike the hat problem, the solution to the box problem actually mentions probabilities, so now there is the question of whether we analyse probabilities of measurable sets. Even if "X=j" is not measurable, maybe "X<=Y", which is the type of thing we actually analyse, is measurable?<br /><br />My claim is that at least for some strategies this is not a measurable set, or in other words we cannot say anything about "the probability of X<=Y".<br /><br />Let's assume that the strategy has an additional feature: If an equivalence class of sequences A is obtained from B by removing the first item of each sequence and shifting the others one place down, then the representative of A is the corresponding shift of the representative of B.<br /><br />It is not immediate how to show the existence of such a strategy, but I believe it can be done through Zorn's Lemma (which is equivalent to the Choice Axiom).<br /><br />Now assume we have such a strategy, and that "X>=Y" is measurable (i.e. an event). But then instead of the original two rows, we can feed the first row, and then the shift of the second row - call the largest mismatch there Y'. Since the probability space is the same, "X>=Y'" is also measurable and with the same probability. But "X>=Y'" is the exact same set as "X>=Y-1" (due to our special strategy). So, by taking event difference we get that "X=Y-1" is measurable, and specifically an event of Probability 0.<br /><br />But we can do more of these gymnastics, and get that every set of the type "X-Y=j" for any j (positive negative or zero) is in fact a Probability 0 event. But this cannot be, because X-Y will always equal something.Eldar Fischernoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-17485298315243567512016-07-18T15:59:57.170-04:002016-07-18T15:59:57.170-04:00You are right, in fact, there is no such thing as ...You are right, in fact, there is no such thing as infinite random permutation of the naturals, we cannot even uniformly select a single natural number, so STEP1 is incorrect.domhttps://www.blogger.com/profile/05790539025733385232noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-18169846079109482982016-07-18T13:41:20.363-04:002016-07-18T13:41:20.363-04:00Let's make Bob's job easier by restricting...Let's make Bob's job easier by restricting Alice's box-filling options as follows:<br /><br />-------------<br /><b>The Restricted Alice-Bob Box Game</b> Alice's Turing Machine (TM) puts natural numbers in the boxes 1,2,3,4,... Alice's TM accepts an input tape of any finite length, such that Alice can design her TM to put any number in any box. Her TM can put the number 12 in two boxes. Her TM can refuse to put primes in any box. The world is Alice's TM-defined burrito!<br />-------------<br /><br /><b>Question</b> Is it valid to argue that if Bob has a strategy that wins the general Alice-Bob Box Game with probability >1-eps, then that same strategy necessarily will win the restricted Alice-Bob Box Game with probability >1-eps?<br /><br />The answer is "yes" (as I understand the statement of the problem), and the point of this comment is to suggest that there is nothing particularly counterintuitive about this answer, in the sense that strings generated by Alice's TM necessarily have finite Kolmogorov complexity, and these strings therefore present informatic order that Bob's algorithm can exploit.John Sidleshttps://www.blogger.com/profile/16286860374431298556noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-31549571409136853202016-07-18T12:15:33.694-04:002016-07-18T12:15:33.694-04:00So, is the resolution of the seeming "paradox...So, is the resolution of the seeming "paradox" that - under the axiom of choice - Alice simply cannot uniformaly and indpendetly chose random numbers from 1 to N for an infinite number of boxes? (Eddie Fisher's comment seems to point that way.)<br />A second question: Is it obvious/clear that in Step 1 Bob can pick a infinite random permutation of the naturals so that whatever he does next Alice cannot have anticipated? FHnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-26370357787013060922016-07-18T11:50:33.886-04:002016-07-18T11:50:33.886-04:00What's the purpose of Bob choosing a random pe...What's the purpose of Bob choosing a random permutation of the natural numbers? It seems that everything works even without this (with randomness only used in choosing which row to look at last).Patrickhttps://www.blogger.com/profile/09956803907225354566noreply@blogger.com