Author |
Topic: single file hat execution (Read 15437 times) |
|
rmsgrey
Uberpuzzler
    
Gender: 
Posts: 2873
|
 |
Re: single file execution (want hint)
« Reply #25 on: Aug 19th, 2003, 7:42am » |
 Quote  Modify
|
Super Sally knows the following probabilities:
Both follow: .09 M lives
Neither follow: .09 M lives
Only L follows: .81 M dies
Only M follows: .01 M dies
So if M dies, Sally knows that, with probability 81/82, M distrusted L and so she should trust L (assume he was right) and mentally correct what M said.
If M lives, then Sally has a 50% guess to make.
Net outcome is that Sally has a 90% chance of survival - just as if Mike wasn't there... In fact, running the numbers, you have the same chance of survival as you're best chance of correctly second-guessing one of the guys ahead of you.
Of course, this means that if you have Completely Credulous Clive, who believes whatever people tell him (which has provided many hours of entertainment to his fellow convicts) then everyone after Clive can automatically deduce whether the first guy told the truth.
With instantaneous executions, I believe Icarus is mistaken in his conclusion about death following transitions - because you know the actual colour of every hat other than your own, the only factor which influences your survival is whether you are right to trust/mistrust the first guy. All the death/survival of intervening people offers is information by which to judge the first guy's credibility (assuming you know something about the other guys credulity)
Of course, if you don't have the automatic correction provided by instant executions, then you do get the transitions die effect as Icarus said.
|
|
 IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: single file execution (want hint)
« Reply #26 on: Aug 19th, 2003, 5:32pm » |
Quote Modify
|
on Aug 19th, 2003, 7:42am, rmsgrey wrote:With instantaneous executions, I believe Icarus is mistaken in his conclusion about death following transitions - because you know the actual colour of every hat other than your own, the only factor which influences your survival is whether you are right to trust/mistrust the first guy. All the death/survival of intervening people offers is information by which to judge the first guy's credibility (assuming you know something about the other guys credulity)
Of course, if you don't have the automatic correction provided by instant executions, then you do get the transitions die effect as Icarus said. |
|
My conclusion posted above for instaneous executions was that everyone can live. Death after transitions was only for the no-information case. (In the other thread I assumed that you would not know the outcomes of previous answers).
When I considered the other case above I rushed it too much and therefore missed that the result as stated only applies when player #1 is truthful. Those following the strategy I described (which could also be stated as "reverse the answer of anyone >1 who dies"), will live if player #1 also follows it. Those who do the reverse will die. If player #1 gives the opposite answer, everyone who follows the strategy will die and those who reverse it will live.
So in the "you know what happens behind you" situation, you live iff you correctly judge whether or not prisoner #1 answered according to the strategy, whereas in the other situation, you live iff you correctly judge whether or not the the prisoner immediately behind you answered according to the strategy.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: single file execution (want hint)
« Reply #27 on: Aug 20th, 2003, 10:06am » |
Quote Modify
|
Actually, for the delayed execution case, survival if you match the guy behind you assumes that you take what everyone says at face value, and then choose to follow or not the pattern based on what was said. If you know that several people behind you are going to go counter to the pattern, then you might be tempted to mentally correct what they say...
If you only have probabilistic information on other prisoners strategies, your best bet is to be speaking immediately after the prisoner you have the best chance to second guess.
In the instant execution case, there's rather more calculation involved.
|
|
IP Logged |
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: single file execution (want hint)
« Reply #28 on: Aug 20th, 2003, 11:06am » |
Quote Modify
|
I shall model the problem as follows: there is a random sequence of 10 bits. There is a row of prisoners that will compute the XOR of the bits in front of them, and then, with probability Pi, report that answer correctly, XORed with the answer of the first prisoner. This Pi is meant to indicate whether they are likely to trust the answer of the first person, and P10 is your a-priori estimate of the probability that the first person would tell the truth.
To calculate the probability in the most general way, we examine two cases: either the first prisoner to speak lied, or he told the truth. Either way has the possibility of leading to the observed combination of prisoners deaths.
P(first prisoner lied and this scenario happened) = [prod]prisoners i<10 that lived(P10(1-Pi)+(1-P10)Pi)*[prod]prisoners i<10 that died(P10Pi+(1-P10)(1-Pi))
P(first prisoner told truth and this scenario happened) = [prod]prisoners i<10 that died(P10(1-Pi)+(1-P10)Pi)*[prod]prisoners i<10 that lived(P10Pi+(1-P10)(1-Pi))
Now using Bayes' theorem, it should be evident that whichever one of these gives a higher number is the more likely under this model. If one of them is quite near 1, then you should be saying "aha! just what I would have predicted". In the real world, if your Pis are accurate, one should be significantly larger than the other. This is similar to approaches used in communication theory to decode messages (you take the observed bits and compute the most probable message that was sent).
This is a very basic model and does not take into account each prisoners' perception of the other prisoners, but it does allow the assessment of all the prisoners who have answered so far and their execution (or lack of same).
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: single file execution (want hint)
« Reply #29 on: Aug 20th, 2003, 4:24pm » |
Quote Modify
|
on Aug 20th, 2003, 10:06am, rmsgrey wrote:| Actually, for the delayed execution case, survival if you match the guy behind you assumes that you take what everyone says at face value, and then choose to follow or not the pattern based on what was said. If you know that several people behind you are going to go counter to the pattern, then you might be tempted to mentally correct what they say... |
|
Since accurately predicting the strategy of your predecessor guarantees your survival, if you are able to do this, any attempt to adjust your answer because of the responses of other prisoners can only lower your chance of survival. The only reason for trying to determine the strategies of other prisoners would be to help you in determining the strategy of that guy right behind you. He alone you must match - nothing else matters.
Quote:
If you only have probabilistic information on other prisoners strategies, your best bet is to be speaking immediately after the prisoner you have the best chance to second guess.
|
|
Regardless of what information you have, this is still true.
Quote:
In the instant execution case, there's rather more calculation involved. |
|
No - I would say that if anything, there is less. Now your survival depends on determining whether or not the 1st prisoner's response will be in accordance to the strategy or not. Regardless of the other players, if you can do this (by calculation or luck), you will live, if you cannot, you will die. Since the first prisoner's response is not influenced any of the other prisoners' responses, it might be easier to "get inside his head", than it would be to do so for the guy right behind you.
Thinking it over: The instantaneous execution situation gives you a choice: If there is anyone behind you whose approach you can definitely figure out, you are guaranteed to live:
Say that you know prisoner L so well, that you can predict what he will say in any situation. By luck, he is somewhere behind you. For your part, your only interest in the answers of those before L is in deciding what L will answer on his turn if he sees an odd number of white hats in front of him. If his actual answer is what you expected, treat it a response of "white", otherwise as a response of "Black". Everyone after L, you use their fate to correct the response (count "White & lived" or "Black & died"). If the result of the count plus the number of white hats before you is odd, say "white", otherwise "black". Effectively, this allows you to treat prisoner L, whom you can best predict, as if he were the first prisoner.
So my conclusion: If you don't know the outcomes of earlier prisoners, you need to correctly predict the response of the prisoner immediately behind you (dependent on how many white hats they see). If you do know the outcomes, you only need to predict the response of any one prisoner behind you.
If P(n) is the probability of your correctly predicting the response of Prisoner #n, given what they have heard and what they see, and if you are prisoner N, then the probability of your survival is (at least) P(N-1) for the no-outcomes-information case, and Max(P(1), P(2), ... , P(N-1)) for the other case (assuming you know which one is highest).
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: single file execution (want hint)
« Reply #30 on: Aug 28th, 2003, 7:25am » |
Quote Modify
|
on Aug 20th, 2003, 4:24pm, Icarus wrote:
If P(n) is the probability of your correctly predicting the response of Prisoner #n, given what they have heard and what they see, and if you are prisoner N, then the probability of your survival is (at least) P(N-1) for the no-outcomes-information case, and Max(P(1), P(2), ... , P(N-1)) for the other case (assuming you know which one is highest). |
|
That was my first thought, but then I spotted that, in some cases, you're better off taking the combined evidence of everyone else than just basing your answer on one person - for instance if you have P(5)=.9 and P(1...4)=.89 and people 1-4 all give you the same optimum choice while 5's information suggests the opposite, you're clearly better off going with the majority and assuming you guessed wrong with number 5.
I haven't actually done the maths to see whether this simplifies, or if, in general, James' equations have to be solved for each case to determine your survival chances.
|
|
IP Logged |
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: single file execution (want hint)
« Reply #31 on: Aug 28th, 2003, 8:37am » |
Quote Modify
|
on Aug 28th, 2003, 7:25am, rmsgrey wrote:
That was my first thought, but then I spotted that, in some cases, you're better off taking the combined evidence of everyone else than just basing your answer on one person - for instance if you have P(5)=.9 and P(1...4)=.89 and people 1-4 all give you the same optimum choice while 5's information suggests the opposite, you're clearly better off going with the majority and assuming you guessed wrong with number 5. |
|
That's what I was thinking of when I developed my formula. Hopefully it would suggest you go with the majority, as common sense predicts.
In fact, if things were this one-sided, then you'd be quite certain (p=.998 I think) that this was the correct decision.
But the beauty of the formula is that it allows you to get information when you know only a little about each person, and also when you think people will guess the opposite (paranoid delusional people). For instance, you might have probabilities in the 0.6 - 0.8 range, which would be difficult to weigh without doing a rigorous calculation.
For me, the most interesting thing about the formula is that it works even if the first person guessing doesn't know about the scheme. You just have to convince the other people that he does, (this might be a good opportunity to assess their probabilities).
I'm still thinking about the case where everybody knows that he first person doesn't know about the scheme, and how that might affect other people's strategy.
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print