>>107 「Terence Tao "one’s intuition on probability should not be trusted here”」で検索 文字化けを修正する気が無いので、原文を math.stackexchange.com/questions/886180/formal-approach-to-countable-prisoners-and-hats-problem probability theory - Formal approach to (countable) prisoners and hats problem. - Mathematics Stack Exchange: asked 2 years ago asked Aug 3 '14 at 10:25 (抜粋) I've found this nice puzzle about AC (I'm referring to the countable infinite case, with two colors). The puzzle has been discussed before on math.SE, but I can't find any description of what is happening from a formal point of view. I'm not really into probability theory, therefore I apologize in advance if I do any mistake or if I can't understand something which is obvious. In particular, I don't know much about infinite sequences of random variables.
Intuitively, the solution is quite paradoxical, and this seems to be the reason: it seems that each prisoner has 50% chance to go free and 50% chance to be killed and nothing (i.e. no strategy) can change this probability, since each prisoner gets no data about his hat from the others and from "the environment". Furthermore, every prisoner's guess is independent from the others. Thus, for the way we intuitively think about probability, it seems that the expected value of prisoners going free should be "a half of N " (whatever this means). It turns out that (using AC) there exists a strategy which allows all but a finite number of prisoners go free (and for sure this is not "a half of N", whatever this means). つづく
>>115 つづき Now, the above intuitive explanation seems really bugged and unclear to me. For example, even the fact that the prisoners can adopt any kind of strategy seems to me a "violation of the rules" (doesn't that change the probability distribution, since the choice is not random anymore?).
Therefore I would like to understand what is formally happening. If you look at the
123 名前：comments in that page, it seems that many people are quite confused about a formal explanation (someone writes even about non-standard integers). つづく []
つづき The only comment which does really make sense to me is Terence Tao's one: This paradox is actually very similar to Banach-Tarski, but involves a violation of additivity of probability rather than additivity of volume.
Consider the case of a finite number N of prisoners, with each hat being assigned independently at random. Your intuition in this case is correct: each prisoner has only a 50% chance of going free. If we sum this probability over all the prisoners and use Fubini’s theorem, we conclude that the expected number of prisoners that go free is N/2. So we cannot pull off a trick of the sort described above.
If we have an infinite number of prisoners, with the hats assigned randomly (thus, we are working on the Bernoulli space ZN2), and one uses the strategy coming from the axiom of choice, then the event Ej that the j^th prisoner does not go free is not measurable, but formally has probability 1/2 in the sense that Ej and its translate Ej+ej partition ZN2 where ej is the j^th basis element, or in more prosaic language, if the j^th prisoner’s hat gets switched, this flips whether the prisoner gets to go free or not. The “paradox” is the fact that while the Ej all seem to have probability 1/2, each element of the event space lies in only finitely many of the Ej.
This can be seen to violate Fubini’s theorem ? if the Ej are all measurable. Of course, the Ej are not measurable, and so one’s intuition on probability should not be trusted here. (Terence Tao's 終わり) つづく
つづき So, the trick seems to be that we can't expect probability to be σ-additive and to measure the probability of every event, at the same time (which seems really similar to Vitali's and Banach-Tarski's arguments). This explanation makes quite sense to me, but I can't fully understand it. How is the event Ej formally defined? And how is Tao precisely using Fubini's theorem in order to get to a contradiction? Could someone give me a formal definition of Ej and a formal proof which shows that, for every j∈N, Ej is not measurable?
これも文字化けを修正する気が無いので、原文を https://cornellmath.wordpress.com/2007/09/13/the-axiom-of-choice-is-wrong/ The Axiom of Choice is Wrong | The Everything Seminar: by Greg Muller This entry was posted on September 13, 2007 (抜粋) When discussing the validity of the Axiom of Choice, the most common argument for not taking it as gospel is the Banach-Tarski paradox. Yet, this never particularly bothered me. The argument against the Axiom of Choice which really hit a chord I first heard at the Olivetti Club, our graduate colloquium. It’s an extension of a basic logic puzzle, so let’s review that one first.
100 prisoners are placed in a line, facing forward so they can see everyone in front of them in line. The warden will place either a black or white hat on each prisoner’s head, and then starting from the back of the line, he will ask
128 名前： each prisoner what the color of his own hat is (ie, he first asks the person who can see all other prisoners). Any prisoner who is correct may go free. Every prisoner can hear everyone else’s guesses and whether or not they were right. If all the prisoners can agree on a strategy beforehand, what is the best strategy?
The answer to this in a moment; but first, the relevant generalization.
A countable infinite number of prisoners are placed on the natural numbers, facing in the positive direction (ie, everyone can see an infinite number of prisoners). Hats will be placed and each prisoner will be asked what his hat color is. However, to complicate things, prisoners cannot hear previous guesses or whether they were correct. In this new situation, what is the best strategy?
Intuitively, strategy is impossible since no information can be conveyed from anyone who knows your hat color to you, so it would seem that everyone guessing blindly. However, all but a finite number of prisoners can go free! つづく []
>>120 つづき Terence Tao Says: September 13, 2007 at 9:58 pm | Reply
This paradox is actually very similar to Banach-Tarski, but involves a violation of additivity of probability rather than additivity of volume.
Consider the case of a finite number N of prisoners, with each hat being assigned independently at random. Your intuition in this case is correct: each prisoner has only a 50% chance of going free. If we sum this probability over all the prisoners and use Fubini’s theorem, we conclude that the expected number of prisoners that go free is N/2. So we cannot pull off a trick of the sort described above.
If we have an infinite number of prisoners, with the hats assigned randomly (thus, we are working on the Bernoulli space {\Bbb Z}_2^{\Bbb N}), and one uses the strategy coming from the axiom of choice, then the event E_j that the j^th prisoner does not go free is not measurable, but formally has probability 1/2 in the sense that E_j and its translate E_j + e_j partition {\Bbb Z}_2^{\Bbb N} where e_j is the j^th basis element, or in more prosaic language, if the j^th prisoner’s hat gets switched, this flips whether the prisoner gets to go free or not. The “paradox” is the fact that while the E_j all seem to have probability 1/2, each element of the event space lies in only finitely many of the E_j. This can be seen to violate Fubini’s theorem ? if the E_j are all measurable. Of course, the E_j are not measurable, and so one’s intuition on probability should not be trusted here.
There is a way to rephrase the paradox in which the axiom of choice is eliminated, and the difficulty is then shifted to the construction of product measure. Suppose the warden can only assign a finite number of black hats, but is otherwise unconstrained. The warden therefore picks a configuration “uniformly at random” among all the configurations with finitely many black hats (I’ll come back to this later). Then, one can again argue that each prisoner has only a 50% chance of guessing his or her own hat correctly, even if the prisoner gets to see all other hats, since both remaining configurations are possible and thus “equally likely”. But, of course, if everybody guesses white, then all but finitely many go free. Here, the difficulty is that the group \lim_{n \to \infty} {\Bbb Z}_2^n is not compact and so does not support a normalised Haar measure. (The problem here is similar to the two envelopes problem, which is again caused by a lack of a normalised Haar measure.)
A countable infinite number of prisoners are placed on the natural numbers, facing in the positive direction (ie, everyone can see an infinite number of prisoners). Hats will be placed and each prisoner will be asked what his hat color is. However, to complicate things, prisoners cannot hear previous guesses or whether they were correct. In this new situation, what is the best strategy?
(I won't link the best strategy in case someone wants to give it a go but note that my question is about the solution)
and I recall my friend and I were trying to come up with a formal argument for why the probability is ill-defined. We kept going in circles so we left it in the end. つづく
>>124 つづき Recently though I stumbled upon the page and I see Terrence Tao's comment, where I copied the relevant paragraph,
If we have an infinite number of prisoners, with the hats assigned randomly (thus, we are working on the Bernoulli space ZN2), and one uses the strategy coming from the axiom of choice, then the event Ej that the jth prisoner does not go free is not measurable, but formally has probability 1/2 in the sense that Ej and its translate Ej+ej partition ZN2 where ej is the jth basis element, or in more prosaic language, if the jth prisoner’s hat gets switched, this flips whether the prisoner gets to go free or not. The “paradox” is the fact that while the Ej all seem to have probability 1/2, each element of the event space lies in only finitely many of the Ej. This can be seen to violate Fubini’s theorem ? if the Ej are all measurable. Of course, the Ej are not measurable, and so one’s intuition on probability should not be trusted here.
It feels like he concludes the non-measurability of Ej from a violation of Fubini, but I don't see it. Can someone flesh this argument out for me? It has been nagging me for a long time now and I would be very grateful :)
>>115-126 ３つサイトから、”Of course, the Ej are not measurable, and so one’s intuition on probability should not be trusted here.” Terrence Tao's comment を紹介した
しかし、出所は１つで、>>121 "September 13, 2007 at 9:58 pm | Reply"だ
しかも、 １．時枝問題ではなく、(countable) prisoners and hats problemに関するコメントであって ２．”Of course, the Ej are not measurable, and so one’s intuition on probability should not be trusted here.”の意味するところは、Ｔさんの>>89の主張とは真逆じゃないかね？ 私もよく読めていないが・・
>>127 > １．時枝問題ではなく、(countable) prisoners and hats problemに関するコメントであって >２．”Of course, the Ej are not measurable, and so one’s intuition on probability should not be trusted here.”の意味するところは、Ｔさんの>>89の主張とは真逆じゃないかね？ 私もよく読めていないが・・
>Taoは「infinity hat problemで助からない人数は有限」は真だと言っている(同じcornellのサイトにTaoの別のレスがある)。 >これは決定番号dが必ず有限になるという主張と等価。
それはこの部分かな？ https://cornellmath.wordpress.com/2007/09/13/the-axiom-of-choice-is-wrong/ Terence Tao Says: September 19, 2007 at 1:45 am | Reply (抜粋) Furthermore, while non-standard models of, say, ZFC, certainly exist (assuming of course that ZFC is consistent ), so do standard models, and the statement “all but finitely many prisoners go free” is also true in the standard model. So it does not seem possible to rigorously reach a conclusion that non-standard numbers exist without some additional external assumption which is not true in the standard model. 引用おわり
>>142 つづき しかし、問題の箇所は”so do standard models, and the statement “all but finitely many prisoners go free” is also true in the standard model. ”だと思うが ここから、”Taoは「infinity hat problemで助からない人数は有限」は真だと言っている”は導けないんじゃないかい さらに、「infinity hat problemで助からない人数は有限」→”決定番号dが必ず有限になるという主張”と等価が導けるのかい
そこも読み違えている気がする えーと、>>121のこの部分だろ ”The “paradox” is the fact that while the E_j all seem to have probability 1/2, each element of the event space lies in only finitely many of the E_j. This can be seen to violate Fubini’s theorem ? if the E_j are all measurable. Of course, the E_j are not measurable, and so one’s intuition on probability should not be trusted here.”
で、Taoが否定しているのは、安易に”to have probability 1/2”に考えるなと このprobability 1/2に相当するのは、時枝解法の99/100の部分だろう？
そもそも、Taoは、https://cornellmath.wordpress.com/2007/09/13/the-axiom-of-choice-is-wrong/ Terence Tao Says: September 19, 2007 at 1:45 am | Reply
で、Terence Tao ”Your arguments are interesting, but I am not sure I see how to make them fully rigorous.”と書いている で、これを借りれば、時枝先生の記事は”fully rigorous”じゃないってこと
>>151 > そもそも、Taoは、https://cornellmath.wordpress.com/2007/09/13/the-axiom-of-choice-is-wrong/ > Terence Tao Says: September 19, 2007 at 1:45 am | Reply > > で、Terence Tao ”Your arguments are interesting, but I am not sure I see how to make them fully rigorous.”と書いている > で、これを借りれば、時枝先生の記事は”fully rigorous”じゃないってこと
１．で、>>142-143に書いたように、問題の箇所は”so do standard models, and the statement “all but finitely many prisoners go free” is also true in the standard model. ”だねと聞いたんだ。それでＯＫだね？ ２．”Taoは「infinity hat problemで助からない人数は有限」は真だと言っている(同じcornellのサイトにTaoの別のレスがある)。 これは決定番号dが必ず有限になるという主張と等価。”>>130 だったよね ３．だから、私が思ったのは、“all but finitely many prisoners go free” is also true→Taoは「infinity hat problemで助からない人数は有限」は真だと言っている→これは決定番号dが必ず有限になるという主張と等価 と貴方が考えたんだろうと ４．で、問題は“all but finitely many prisoners go free”→「infinity hat problemで助からない人数は有限」が導けるのか ５．「infinity hat problemで助からない人数は有限」→これは決定番号dが必ず有限になるという主張と等価 が導けるのか ６．上記の４と５については、解釈したＴさんが”導ける”ということを示す責任があると思うけど ７．個人的には４の方が問題が大きいと思うけど。それはともかく、「私がまったく分かってない」というふうに問題をすり替えているように聞こえるんだが
>>153 > >>143 > > ここから、”Taoは「infinity hat problemで助からない人数は有限」は真だと言っている”は導けないんじゃないかい > > 違う。 > > Barak Pearlmutterとのやり取りをよく読みなさい。 > > > しかし、問題の箇所は”so do standard models, and the statement “all but finitely many prisoners go free” is also true in the standard model. ”だと思うが > > nonstandard modelを持ち出すBarakに対してTaoはstandard modelでも命題は真だと言っているんだよ。 > > >>145 > > で、Taoが否定しているのは、安易に”to have probability 1/2”に考えるなと > > このprobability 1/2に相当するのは、時枝解法の99/100の部分だろう？ > > 違う。 > probability 1/2に相当するのは時枝問題では確率0。 > すなわち1つの箱の中身を当てる確率だ。 > > まったく分かってないじゃないか。 > 英語が読めないのか？
