This is a technical post arising from a question Rob Koons asked me.
An infinite sequence of fair and independent coin flips determines a sequence of zeroes and ones (e.g., zero = tails, one = heads). Let Ω be the set of all infinite sequences of zero/one sequences, equipped with the probability measure P corresponding to the fair and independent coin flips.
Notice an invariance property capturing at least part of the independence and fairness assumption. If ρn is the operation of flipping the nth element in the sequence, and ρnA for a subset A of Ω is the set obtained by applying ρn to every sequence in A, then P(ρnA)=P(A) whenever A is measurable. Moreover, intuition extends this idea beyond the measurable sets: A and ρnA are always going to be probabilistically on par.
Let Ω0 be the subset of Ω consisting of those sequences that have only finitely many ones in them. There is a natural one-to-one correspondence between Ω0 and the natural numbers N. Suppose a=(a0,a1,...,ak,0,0,0,...) is a member of Ω0. Then let N(a) be the natural number whose binary digits are ak...a1a0. Conversely, given a natural number n with binary digits ak...a1a0, let n* be the sequence (a0,a1,...,ak,0,0,0,...) in Ω0. Thus, we can interpret the members of Ω0 as binary numbers written least significant digit first.
For any members a and b of Ω, write a#b for the sequence whose nth element is the sum modulo 2 (xor) of the nth elements of a and b. For a subset B of Ω, let a#B = { a#b : b∈B }. We can think of a#B as a twist of B by a. If a is in Ω0, I will call it a finite twist. Any finite twist can be written as a finite sequence of flips ρn, where the positions n correspond to the non-zero digits in the sequence we twist by. Thus, if A is measurable, a finite twist of it will have the same probability as A does, and even if A is not measurable, a finite twist will be intuitively equivalent to A.
Say that a~b if and only if a and b differ in only finitely many places. Thus, a~b if and only if a#b is a member of Ω0. This is an equivalence relation. By the Axiom of Choice, there is a set A0 such that for every b in Ω, there is a unique a in A0 with a~b. (Thus, A0 contains exactly one member of each equivalence class.) For any natural number n other than 0, let An=n*#A0 and it's easy to check that this equation holds for n=0 as well.
It's easy to see that the An are disjoint and their union is all of Ω. They are disjoint because if a is in n*#A0 and m*#A0, then a=n*#b and a=m*#c for b and c in A0. It follows that b~c. But A0 contains only one member from each equivalence class, so b=c, and so n*#b=m*#b, from which it obviously follows that n*=m* and so n=m. Their union is all of Ω, because if b is in Ω, and a is the unique member of A0 such that a~b, then N(a#b)*#a=(a#b)#a=b (by obvious properties of addition modulo 2), and so b is a member of AN(a#b).
But all the An are going to be intuitively probabilistically on par: they are each a finite twist of A0.
Our lottery is now obvious. Given a random sequence of coin flips, we take its representation a in Ω and choose the unique number n such that a is in An.
This is really the Vitali-set construction applied directly to sequences of coin flips. Note that along the way we basically showed that Ω has nonmeasurable subsets. For the sets An cannot be measurable with respect to P, since they would all have equal probability, and so by countable additivity they would have to have probability zero, which would violate the total probability axiom.
The construction in this post is more complicated than the one here, I guess, but it has the advantage that it always works, while that construction only worked with probability 1.
An infinite sequence of fair and independent coin flips determines a sequence of zeroes and ones (e.g., zero = tails, one = heads). Let Ω be the set of all infinite sequences of zero/one sequences, equipped with the probability measure P corresponding to the fair and independent coin flips.
Notice an invariance property capturing at least part of the independence and fairness assumption. If ρn is the operation of flipping the nth element in the sequence, and ρnA for a subset A of Ω is the set obtained by applying ρn to every sequence in A, then P(ρnA)=P(A) whenever A is measurable. Moreover, intuition extends this idea beyond the measurable sets: A and ρnA are always going to be probabilistically on par.
Let Ω0 be the subset of Ω consisting of those sequences that have only finitely many ones in them. There is a natural one-to-one correspondence between Ω0 and the natural numbers N. Suppose a=(a0,a1,...,ak,0,0,0,...) is a member of Ω0. Then let N(a) be the natural number whose binary digits are ak...a1a0. Conversely, given a natural number n with binary digits ak...a1a0, let n* be the sequence (a0,a1,...,ak,0,0,0,...) in Ω0. Thus, we can interpret the members of Ω0 as binary numbers written least significant digit first.
For any members a and b of Ω, write a#b for the sequence whose nth element is the sum modulo 2 (xor) of the nth elements of a and b. For a subset B of Ω, let a#B = { a#b : b∈B }. We can think of a#B as a twist of B by a. If a is in Ω0, I will call it a finite twist. Any finite twist can be written as a finite sequence of flips ρn, where the positions n correspond to the non-zero digits in the sequence we twist by. Thus, if A is measurable, a finite twist of it will have the same probability as A does, and even if A is not measurable, a finite twist will be intuitively equivalent to A.
Say that a~b if and only if a and b differ in only finitely many places. Thus, a~b if and only if a#b is a member of Ω0. This is an equivalence relation. By the Axiom of Choice, there is a set A0 such that for every b in Ω, there is a unique a in A0 with a~b. (Thus, A0 contains exactly one member of each equivalence class.) For any natural number n other than 0, let An=n*#A0 and it's easy to check that this equation holds for n=0 as well.
It's easy to see that the An are disjoint and their union is all of Ω. They are disjoint because if a is in n*#A0 and m*#A0, then a=n*#b and a=m*#c for b and c in A0. It follows that b~c. But A0 contains only one member from each equivalence class, so b=c, and so n*#b=m*#b, from which it obviously follows that n*=m* and so n=m. Their union is all of Ω, because if b is in Ω, and a is the unique member of A0 such that a~b, then N(a#b)*#a=(a#b)#a=b (by obvious properties of addition modulo 2), and so b is a member of AN(a#b).
But all the An are going to be intuitively probabilistically on par: they are each a finite twist of A0.
Our lottery is now obvious. Given a random sequence of coin flips, we take its representation a in Ω and choose the unique number n such that a is in An.
This is really the Vitali-set construction applied directly to sequences of coin flips. Note that along the way we basically showed that Ω has nonmeasurable subsets. For the sets An cannot be measurable with respect to P, since they would all have equal probability, and so by countable additivity they would have to have probability zero, which would violate the total probability axiom.
The construction in this post is more complicated than the one here, I guess, but it has the advantage that it always works, while that construction only worked with probability 1.
No comments:
Post a Comment