Monday, August 24, 2020

Hyperreal modeling of infinitely many coin flips

A lot of my work in philosophy of probability theory has been devoted to showing that one cannot use technical means to get rid of certain paradoxes of infinite situations. As such, most of the work has been negative. But here is a positive result. (Though admittedly it was arrived at in the service of a negative result which I hope to give in a future post.)

Consider the case of a (finite or infinite, countable or not) sequence of independent fair coin flips. Here is an invariance feature we would like to have for our coin flips. Suppose that ahead of time, I designate a (finite or infinite) set of locations in the infinite sequence. You then generate the sequence of independent fair coin flips, and I go through my pre-designated set of locations, and turn over each of the coins corresponding to that location. (For instance, if you will make a sequence of four coin flips, and I predesignate the locations 1 and 3, and you get HTTH, then after my extra flipping set the sequence of coin flips becomes TTHH: I turned over the first and third coins.) The invariance feature we want is that no matter what set of locations I predesignate, it won’t affect the probabilistic facts about the sequence of independent fair coin flips.

This invariance feature is clearly present in finite cases. It is also present if “probabilistic facts” are understood according to classical countably-additive real-valued probability theory. But what if we have infinitely many coins, and we want to be able to do things like comparing the probability of all the coins being heads to all the even-numbered coins being heads, and say that the latter is more likely than the former, with both probabilities being infinitesimal? Can we still have our reversal-invariance property for all predesignated sets of locations?

There are analogous questions for other probabilistic situations. For instance, for a spinner, the analogous property is adding an extra predesignated rotation to the spinner once the spinner stops, and it is well-known that one cannot have such invariance in a context that gives us “enough” infinitesimal probabilities (e.g., see here for a strong and simple result).

But the answer is positive for the coin flip case: there is a hyperreal-valued probability defined for all subsets of the set of sequences (with fixed index set) of heads and tails that has the reversal-invariance property for every set of locations.

This follows from the following theorem.

Theorem: Assume the Axiom of Choice. Let G be a locally finite group (i.e., every finite subset generates a finite subgroup) and suppose that G acts on some set X. Then there is a hyperreal finitely additive probability measure P defined for all subsets of X such that P(gA)=P(A) for every A ⊆ X and g ∈ G and P(A)>0 for all non-empty A.

To apply this theorem to the coin-flip case, let G be the abelian group whose elements are sets of locations with the exclusive-or operation (i.e., A ⊕ B = (A − B)∪(B − A) is the set of all locations that are in exactly one of A and B). The identity is the empty set, and every element has order two (i.e., A ⊕ A = ∅). But for abelian groups, the condition that every finite subset generates a finite subgroup is equivalent to the condition that every element has finite order (i.e., some finite multiple of it is zero).

Mathematical notes: The subgroup condition on G in the Theorem entails that every element of G has finite order, but is stronger than that in the non-abelian case (due to the non-trivial fact that there are infinite finitely generated torsion groups). In the special case where X = G, the condition that every element of G have finite order is necessary for the theorem. For if g has infinite order, let A = {gn : n ≥ 0}, and note that gA is a proper subset of A, so the condition that non-empty sets get non-zero measure and finite additivity would imply that P(gA)<P(A), which would violate invariance. It is an interesting question whether the condition that every finite subset generates a finite subgroup is also necessary for the Theorem if X = G.

Proof of Theorem: Let F be the partially ordered set whose elements are pairs (H, V) where H is a finite subgroup of G and V is a finite algebra of subsets of X closed under the action of H, with the partial ordering (H1, V1)≼(H2, V2) if and only if H1 ⊆ H2 and V1 ⊆ V2.

Given (H, V) in F, let BV be the basis of V, i.e., a subset of pairwise disjoint non-empty elements of V such that every element of V is a union of (finitely many) elements of BV. For A ∈ BV and g ∈ H, note that gA is a member of V since V is closed under the action of H. Thus, gA = B1 ∪ ... ∪ Bn for distinct elements B1, ..., Bn in BV. I claim that n = 1. For suppose n ≥ 2. Then g−1B1 ⊆ A and g−1B2 ⊆ A, and yet both g−1B1 and g−1B2 are members of V by H-closure. But since A is a basis element it follows that g−1B1 = A = g−1B2, and hence B1 = B2, a contradiction. Thus, n = 1 and hence gA ∈ BV. Moreover, if gA = gB then A = B, so each member g of H induces a bijection of BV onto itself.

Now let P(H, V) be the probability measure on V that assigns equal probability to each member of BV. Since each member of H induces a bijection of BV onto itself, it’s easy to see that P(H, V) is an H-invariant probability measure on V. And, for convenience, if A ∉ V, write P(H, V)(A)=0.

Let F* = {{B ∈ F : A ≼ B}:A ∈ F}. This is a nonempty set with the finite intersection property (it is here that we will use the fact that every finite subset of G generates a finite subgroup). Hence it can be extended to an ultrafilter U. This ultrafilter will be fine: {B ∈ F : A ≼ B}∈U for every A ∈ F. Let *R be the ultraproduct of the reals R over F with respect to U, i.e., the set of functions from F to R modulo U-equivalence. Given a subset A of X, let P(A) be the equivalence class of (H, V)↦P(H, V)(A).

It is now easy to verify that P has all the requisite properties of a finitely-additive hyperreal probability that is invariant under G and assigns non-zero probability to every non-empty set.


Alexander R Pruss said...

The condition that every finite subset generates a finite subgroup is necessary for the Theorem if X = G. This follows from:

IanS said...

Very nice! And beyond my analytical abilities to devise. :-)

I thought at first that this answered my question: Is the [coin-flip lottery] really fair? Alas, it shows that the lottery could be fair, but not that it must be.