Suppose we have a countably infinite fair lottery, in John Norton’s sense of label independence: in other words, probabilities are not changed by any relabeling—i.e., any permutation—of tickets. In classical probability, it’s easy to generate a contradiction from the above assumptions, given the simple assumption that there is at least one set A of tickets that has a well-defined probability (i.e., that the probability that the winning ticket is from A is well-defined) and that has the property that both A and its complement are infinite. John Norton rejects classical probability in such cases, however.
So, here’s an interesting question: How weak are the probability theory assumptions we need to generate a contradiction from a label independent countably infinite lottery? Here is a collection that works:
The tickets are numbered with the set N of natural numbers.
If A and B are easily describable subsets of the tickets that differ by an easily describable permutation of N, then they are equally probable.
For every easily describable set A of tickets, either A or its complement is (or both are) more likely than the empty set.
If A and B are disjoint and each is more likely than the empty set, then A ∪ B is more likely than A or is more likely than B.
Being at least as likely as is reflexive and transitive.
Here, Axioms 3 and 4 are my rather weak replacement for finite additivity (together with an implicit assumption that easily describable sets have a well-defined probability). Axiom 2 is a weak version of label independence, restricted to easily describable relabeling. Axiom 5 is obvious, and the noteworthy thing is that totality is not assumed.
What do I mean by “easily describable”? I shall assume that sets are “easily describable” provided that they can be described by a modulo 4 condition: i.e., by saying what value(s) the members of the set have to have modulo 4 (e.g., “the evens”, “the odds” and “the evens not divisible by four” are all “easily describable”). And I shall assume that a permutation of N is “easily describable” provided that it can be described by giving a formula fi(x) using integer addition, subtraction, multiplication and division for i = 0, 1, 2, 3 that specifies what happens to an input x that is equal to i modulo 4. (E.g., the permutation that swaps the evens and the odds is given by the formulas f2(0)=f0(x)=x + 1 and f3(x)=f1(x)=x − 1.)
Proof: Let A be the set of even numbers. By (3), A or N − A is more likely than the empty set. But A and N − A differ by an easily describable permutation (swap the evens with the odds). So, by (2) they are equally likely. So they are both more likely than the empty set. Let B be the subset of A consisting of the even numbers divisible by four and let C = A − B be the even numbers not divisible by 4. Then B and C differ by an easily describable permutation (leave the odd numbers unchanged; add two to the evens divisible by four; subtract two from the evens not divisible by four). Moreover, A and B differ by an easily (but less easily!) describable permutation. (Exercise!) So, A, B and C are all equally likely by (2). So they are all more likely than the empty set. So, A = B ∪ C is more likely than either B or C (or both) by (4). But this contradicts the fact that A is equally likely as B and C.
Do you need to be so specific about ‘easily describable’? All that seems to be needed are two sets P ⊂ Q such that P, Q\P and Qc (=complement of Q) are all infinite, and Q is more likely than the empty set. (To match to the post, take P = multiples of 4 and Q = even numbers.)
ReplyDeleteFirst, a lemma: for any sets A and B with A ⊂ B and A and B\A both infinite, A and B\A are equally likely (write as A ≈ B\A). Why? Because there is a permutation that switches A and B\A.
Applying the lemma, Q\P ≈ P ≈ Pc = Q\P ∪ Qc. But, by the lemma, Qc ≈ Q which is more likely than the empty set by assumption. Given your (4), this is a contradiction.
This sort of reasoning assumes all sets are comparable. Some problems for standard numerical probabilities are avoided by declaring some sets non-measurable. Maybe something similar could work for comparative probability.
Ian:
ReplyDeleteThe name of my game here is to work with as simple premises as possible.
One might worry that a re-labeling that cannot be described by us doesn't really count as the sort of re-labeling under which probabilities should be preserved. So I want to restrict to describable re-labelings. But there are lots of paradoxes in view once one starts to talk about "describability". (E.g., "the first indescribable ordinal" -- oops, haven't I just described it?) So instead of talking about describability in general, I restrict to an unproblematic simpler version.
Note that the reasoning does not assume that all sets are comparable. Rather, it assumes that (easily describable) re-labeling preserves probability.
*Correction:* As weak premises as possible, not as simple. :-)
ReplyDeleteYes, I had missed the point. I now see.
ReplyDelete