131–140 of 146 posts
The nice thing about this is that we can use Dot-town as a halting oracle, which can then be used to solve any specific undecidable problem we'd want to solve. Make the machine output a set of dots after running some unknown computation, such as a search for twin primes. The residents will kill themselves depending on the results.
How so?
I found the "trick" solution to Unwanted Expansion to be unsatisfying: unless I am mistaken, it assumes that all of the values must be positive integers, which was not stated as being the case.
no, it's about the structure of the expression expanding indefinitely. if that happened then if all the values were positive then the value of the expression would also tend to infinity
Earlier quoted context omitted.
Because of the particular distributions that you happen to have chosen. Alice doesn't have to pick uniformly at random. Since 0^p=0 and 1^p=1 we can experiment with different distributions by using "Math.pow(Math.random(),p)" in place of "Math.random()". For example: var prior = Math.pow(Math.random(),1); var hand1 = Math.pow(Math.random(),10); var hand2 = Math.pow(Math.random(),10); > Win probability: 0.5757182 and…
> the win probability will always be >0.5 so long as the "prior" probability distribution has a nonzero probability of being between Alice's two numbers. Wow. This is the key piece of information that makes the problem interesting, IMO. That's quite unintuitive. If you know anything at all about how your opponent chooses numbers, you win in the long term.
Earlier quoted context omitted.
> the win probability will always be >0.5 so long as the "prior" probability distribution has a nonzero probability of being between Alice's two numbers. Wow. This is the key piece of information that makes the problem interesting, IMO. That's quite unintuitive. If you know anything at all about how your opponent chooses numbers, you win in the long term.
It also tells us what Alice's optimal strategy is: pick the first number at random, and then select an adjacent integer as the second number. Thus, there's no space between them that your prior can assign any probability to.
Another very counterintuitive (for me) problem: how do you do better that break even in the following game: 'A' chooses two distinct integers, writes them on slips of paper and holds one out in each hand in a fist. You choose a hand and reveal a number. You must then guess whether the other number is higher or lower than the revealed one, winning $1 if you guess right and losing $1 otherwise.
The Dot Town Suicides appears to be incorrect as stated. Suppose there are 100 residents and 2 blue dots. The stranger tells everyone "there are not 98 blue dots" This meets the condition of the question's "non-trivial" but the residents can relax: nobody has learned anything new. The proposed induction is broken, in my opinion.
But this isn't correct. Let's say n = 6, a-c are blue, d-f are red, and the information is that there is at least one blue dot. a knows there are at least two, but thinks b may believe there is only one blue dot. Moreover, a believes b may believe that c may believe that there are no blue dots.
So if a was red, the information would mean that b would commit suicide if c did not initially commit suicide, but since neither has happened, a must have a blue dot and therefore must commit suicide.
A convoluted process to be sure but does it make sense how the information transmits by ruling out hypotheticals?
Earlier quoted context omitted.
> if Alice picks 10 and 20 and opens 10 first then you have a 0% chance of winning. No because you pick the hand (i.e. it’s essentually random), so you still have 50% chance of first revealing 20 and gettingit right.
Good point. So our methods are similar, but yours puts the randomness in the choice of hand rather than the choice of integer. But in the (10,20) case your method gets exactly 50% and not more than 50%.
Earlier quoted context omitted.
Why does this work with probability 2/3 then? https://jsfiddle.net/q4qbewp1/
Because of the particular distributions that you happen to have chosen. Alice doesn't have to pick uniformly at random. Since 0^p=0 and 1^p=1 we can experiment with different distributions by using "Math.pow(Math.random(),p)" in place of "Math.random()". For example: var prior = Math.pow(Math.random(),1); var hand1 = Math.pow(Math.random(),10); var hand2 = Math.pow(Math.random(),10); > Win probability: 0.5757182 and…
I'm not sure if that always holds true. Let's say Alice flips a coin and picks 3 or 4 for num1, then Alice flips another coin and picks either num1 - 2 or num1 + 2 for num2.
You come along and pick a number between 1 and 6. You have a non-zero chance of having picked a number between Alice's two numbers, but your chances of winning are not > 0.5.
If you picked a number between 2 and 5 though, your chances of winning are now > 0.5. Like jstanley said, you'd have to know how Alice picks numbers in order to win in the long run.
The Dot Town Suicides appears to be incorrect as stated. Suppose there are 100 residents and 2 blue dots. The stranger tells everyone "there are not 98 blue dots" This meets the condition of the question's "non-trivial" but the residents can relax: nobody has learned anything new. The proposed induction is broken, in my opinion.
> “Non-trivial” means here that there is some number of blue dots for which the statement would not have been true.
I think this is supposed to say "Trivial means..."
If there were 98 blue dots, your statement would not have been true, so it was trivial information.
Essentially, if the people of dot town can figure it out themselves, then you've given them a trivial piece of information. They know there aren't 98 blue dots, because they can already see that for themselves.
Earlier quoted context omitted.
> there's no way to retain or communicate any information about a particular prisoner's actions The communication happens before the people go in to open the boxes. In the 2-person 2-box 1-choice example, person 1 says to person 2 "I'll open box 1 and you open box 2". With person 1 always opening box 1 and person 2 always opening box 2, what do you feel their chances are? List out the permutations and see.
I'll grant that with two people, they have a 50% chance of survival, because there's no way that only one of them can be right. But with more than two, the odds seem to get worse in a hurry. Presumably the same exclusion principle that improves their odds from the "obvious" 25% to 50% will apply to any larger number of participants, and converge near 30%... but it's certainly unintuitive.
Worse, they actively confuse the issue by making the warden an adversary and adding another layer of randomness that's just a red herring. Instead imagine they just put their names in alphabetical order so box 1 is Andy, box 2 is Bob, and so on.
First consider if they were randomly ordered buttons and everyone had to press their button. The people can plan out any order of pressing buttons, it doesn't matter because each person has to win their own separate 50 in 100 bet. So this should be intuitive. (1/2)^100 is impossible odds.
The key part is this: "He then looks into the box belonging to the name he just found".
They are picking an order that's based on the arrangement of names in boxes so they are no longer acting independently from the random box-name arrangement. If everybody was assigned some arbitrary starting box, they are not making 100 separate choices anymore they are making 1 collective choice. But it's the same chance! Instead of making 100 separate fairly likely choices, they are making 1 very unlikely choice (that the starting box order they picked is right).
The second key is starting with the box assigned to their own name.
So imagine this problem as a directed graph. Each person's box is a node and the name within is a directed edge to another node. Every node has exactly one edge to it and one edge from it, and the edges are all random. It's incredibly unlikely to be one full circuit though, instead there are little isolated circuits. For example, box 1 could have "Bob" and box 2 could have "Andy" and if anybody else picked box 1 as their starting box they would never find their name, instead finding 25 Bobs and 25 Andys.
By picking their own box, they're guaranteed to be on a circuit that has their name on it and they are excluding all other random arrangements, so Conan getting stuck on an Alex-Bob circuit of 2 is impossible. The only question is if it will take more than 50 steps.
Now imagine you are randomly constructing this directed graph one step at a time. You open box 1 (Andy's box) and randomly put in Conan, open box 3 (Conan's box) and put in Xavier - can't be Conan because you already used that name! Every next step in a chain has an increasing chance of coming back to the beginning. So on the second step there's 99 names left and one of them is Andy, on the third step there's 98 left and one is Andy. The longer the chain, the more likely it is to end and become a circuit. The warden won't be following this process to assign names, but since every step is random it's the same result as any other random way to assign names to boxes.
So the longer the chain the more likely to become a circuit, and the shorter every other circuit has to be, is finally the reason why the win chance is higher than seems possible.
Why it's 30.5% instead of 23% or something else. Well, imagine the first chain being constructed. The chance of it getting longer than 50 is (99/100)(98/99)...(50/51) which works out to 50%. So the first person (Andy) opening his box has a 50% chance that his chain got longer than 50 before it become a circuit - exactly what you'd expect for the first box. But the chance of building the second chain longer than 50 is much smaller because the first one took a lot of names out of the hat, so say first circuit is 25 long, second chain is (74/75)(73/74)... so you'll have to ask a math genius how to estimate that, but intuitively it's much less likely.