# Proving finite additivity for this semi-algebra (infinite coin flips)

Background copied and pasted from another one of my questions:

Background: Consider flipping a coin $n$ times. Define the sample space as $$\Omega = \{(r_1,r_2,r_3,\dots); r_i = 0 \text{ or }1\}$$ Define subsets of the sample space as $$A_{a_1a_2\dots a_n} = \{(r_1,r_2,\dots )\in \Omega; r_i =a_i \text{ for } 1\leq i \leq n\}$$ where $r_i$ is $0$ if the $i$th coin flip is tails and $1$ if it is heads.

Define a set $\mathcal{J}$ by $$\mathcal{J} = \{ A_{a_1a_2\dots a_n}; n\in \mathbb{N}, a_1,a_2,\dots ,a_n \in \{ 0,1\}\} \cup \{\emptyset , \Omega\}$$

Let $P(A_{a_1a_2\dots a_n}) = 1/2^n$ for each set $A_{a_1a_2\dots a_n}$

Problem: I want to show that the above $\mathcal{J}$ and $P$ satisfy the following property for finite collections $\{D_n\}$:

$$P(\cup_n D_n)= \sum_n P(D_n) \text{ for } D_1,D_2,\dots \in \mathcal{J} \text{ disjoint with }\cup_nD_n \in \mathcal{J}$$ Hint: The hint I am given is: For a finite collection $\{D_n\}\in\mathcal{J}$, there is a $k\in \mathbb{N}$ such that the results of only coins $1$ through $k$ are specified by any $D_n$. Partition $\Omega$ into the corresponding $2^k$ subsets.

I have submitted what I think a solution, yet I would be very happy if someone can provide me with a cleaner/shorter solution (I believe one exists). Thanks.

Edit: Note: I changed my interpretation of $k$ from what I thought initially.

Edit: I have deleted my work since I think I found a solution and now simply want a nicer one. I think the cleaner look makes it more likely that I will get one.

• Your k seems right. Not sure I understand the exercise fully though: If $D_1 = A_{010}$ and $D_2 = A_{101}$, is $k > 3$? – BCLC Jan 5 '16 at 5:53
• stat.ualberta.ca/~schmu/stat571/n1.pdf – BCLC Jan 5 '16 at 6:01
• That's a good point... I would think that in your example then $k=0$, but then that doesn't make sense. So perhaps $k$ is simply the smallest length of some $D_i$. So if $D_1 = A_{0101}$ and $D_2 = A_{101}$, $k=3$, since $3<4$?. I will consider that and see if I get anywhere. Thanks. – majmun Jan 5 '16 at 17:46

Yes, you are right in your belief, and the following answer is based on the hint.

To simplify the answer, we shall use the following notations. For each natural $k$ let $\{0,1\}^k$ be the set of $0$-$1$ words of length $k$. For the convenience, as $\{0,1\}^0$ we denote the set consisting of empty word $\varnothing$. Put $\{0,1\}^\infty=\bigcup_{n=0}^\infty \{0,1\}^n$. Let $v,w\in \{0,1\}^\infty$ be words. We shall write $v\le w$, if the word $v$ is a prefix of the word $w$, that is if $w=vu$ for some (possibly, empty) word $u\in \{0,1\}^\infty$. In our notation, $\mathcal J=\{\varnothing\}\cup\bigcup_{v\in \{0,1\}^\infty} A_v$ (remark that $\Omega= A_\varnothing$).

Let $\mathcal D$ be a finite subcollection of the family $\mathcal J\setminus\{\varnothing\}$. Then there exists a finite subset $V$ of $\{0,1\}^\infty$ such that $\mathcal D=\{A_v:v\in V\}$. Since the collection $\mathcal D$ is finite, there exists a natural number $N$ such that $V\subset \bigcup_{n=0}^N \{0,1\}^n$. It is easy to check that $A_v=\bigcup \{A_w: w\in \{0,1\}^N$ and $v\le w\}$ and $$P(A_v)=\sum \{P(A_w): w\in \{0,1\}^N\mbox{ and }v\le w\}$$ for each $v\in V$. Put $W=\{w\in \{0,1\}^N:\exists v\in V: v\le w\}$. Put $A=\bigcup\mathcal D=\bigcup \{A_v:v\in V\}$. Then $A=\bigcup \{A_w: w\in W\}$. If $A\in\mathcal J$ then $A=A_u$ for some $u\in\{0,1\}^\infty$ and it is easy to check that $W=\{w\in \{0,1\}^N:u$ is a prefix of $w\}$. Then $$\sum_{D\in\mathcal D} P(D)=\sum_{v\in V} P(A_v)=\sum_{w\in W} P(A_w)=P(A_u)$$ (remark that the collection $\mathcal D$ should be disjoint in order to satisfy the second equality).

• I haven't finished looking going through the proof yet, but quick question: For the definition of prefix, when you say $w=vu$, what is the operation for $vu$? Is it concatenation? I ask because if it is concatenation then we are combining two infinite words of length $\infty$. – majmun Jan 8 '16 at 16:57
• @majmun Yes, it is a concatenation, but of finite words from the set $\{0,1\}^\infty=\bigcup_{n=0}^\infty \{0,1\}^n$ – Alex Ravsky Jan 8 '16 at 17:05
• Is this correct? The first equality follows by definition, the second equality follows from the fact that $A_v=\bigcup \{A_w: w\in \{0,1\}^N$ and $v\leq w\}$ for each $v\in V$, and the third equality follows from $A=\bigcup \{A_w: w\in W\}$. However, it still needs to be proven that the second equality is true, right (doesn't seem hard, though)? And the reason $\mathcal{D}$ must be disjoint is because otherwise we would add the same $P(A_w)$ twice? So if not disjoint, could we just subtract the overlap? Also, $\mathcal{D}$ is supposed to be disjoint -- I had typo in question. – majmun Jan 9 '16 at 2:30
• @majmun Yes, all you arguments are right. The second equality holds because if the word $v$ has length $n$ then $P(A_v)=2^{-n}$ and there are exactly $2^{N-n}$ words $w$ of length $N$ (which implies $P(A_w)=2^{-N}$) such that $v\le w$. If the family $\mathcal D$ is not disjoint, and we just subtract the overlap of $A_w$’s, it will be essentially the same as the third equality. – Alex Ravsky Jan 10 '16 at 19:15

Let $\{D_n\}$ be a finite collection of $D_i \in \mathcal{J}$. Note that every element in $\mathcal{J}$ is of the form $A_{a_1a_2\dots a_m}$, so every element of the collection $\{D_n\}$ has some length (I'm using length as : the length of $A_{a_1a_2 \dots a_m}$ is $m$).

Let $k$ be the smallest length in $\{D_n\}$ (it is the smallest $m$). Denote the element with this length by $L$. Now, partition $\Omega$ into $2^k$ disjoint partitions, denoted $B_j, j\in \{1,2,\dots, 2^k) = J$. At least one of these is $L$, denote it $B_{j_L}$.

Consider $$\sum_{j=1}^{2^k}P(B_j) = P(B_{j_L})+ \sum_{j\in J\setminus j_L}P(B_j) =1$$ If there exists any other $D_i \in \{D_n\}$ (besides $B_{j_L}$) such that $D_i = B_j, j\not = j_L$ denote them by $B_{j_{s}}, s\in S$, where $S$ is a set containing the indexes of all such elements.

To simplify the notation, let $S' = S\cup j_L$. That is, $S'$ is $S$ with the index for $j_L$ added. Let $q =|S'|$, the cardinality of $S'$ Now we have: $$\sum_{j=1}^{2^k}P(B_j) = \sum_{i\in S'}P(B_i)+ \sum_{j\in J\setminus S'}P(B_j) =1$$

For any remaining $D_i \in \{D_n\}$ s.t. $D_i \not = B_i, i\in S'$, let $\{B_l\}$ be the set of all $B_j$ whose $k$ coin toss results match the first $k$ coin toss results of at least one $D_i \in \{D_n\}$ Let $Q$ denote the set of indices for the $B_l$'s; that is, let $\{B_l\} = \{B_q\}_{q \in Q}$

For every $B_q q\in Q$, Let $t_q$ be the sequence $a_1a_2\dots a_m$ of $D_i$, for whichever $D_i$ shares the same $k$ coin results with $B_q$. If $B_q$ shares the first $k$ results with more than one $D_i$, choose the longest $t_q$. Let $k_q$ be the length of each $t_q$ Let $\Omega_{k_q} = \Omega = \{(r_1,r_2,r_3,\dots r_{k_q}); r_i = 0 \text{ or }1\}$. Note that $\forall q, B_q = \cup_{i\in \Omega_{k_q}} A_i$ Therefore,

$$\sum_{j=1}^{2^k}P(B_j) = \sum_{i\in S'}P(B_i)+ \sum_{q\in Q}\sum_{i\in\Omega_{k_q}}P(A_i) \sum_{j\in J\setminus S''}P(B_j) = 1$$ where $S'' = S'\cup Q$. We can write this as $$\sum_{i\in S'}P(B_i)+ \sum_{q\in Q}\sum_{i\in\Omega_{k_q}}P(A_i\setminus \{D_i\}) + \sum_{q\in Q}\sum_{i\in\Omega_{k_q}}P(A_i\setminus \{D_i\}^c) + \sum_{j\in J\setminus S''}P(B_j)=1$$ rearranging further gives $$\sum_{i\in S'}P(B_i) + \sum_{q\in Q}\sum_{i\in\Omega_{k_q}}P(A_i\setminus \{D_i\}^c) =1- \sum_{j\in J\setminus S''}P(B_j) - + \sum_{q\in Q}\sum_{i\in\Omega_{k_q}}P(A_i\setminus \{D_i\})$$ The RHS which is $P(\cup D_i), D_i \in \{D_n\}$, because it is one minus the probability of the complement

• I am not marking this as answered because I feel like there should be a much more elegant solution, and also because I'm not sure this solution is correct. Particularly, at the end I would need to show that we have one minus the probability of the complement (which I believe can be done by writing $B_j$ as a union and combining the terms, but I am not sure). – majmun Jan 5 '16 at 21:45
• I don't understand why the $k$ here is chosen to be the shortest one. Why not take $k$ to be the longest, and partition $\Omega$ into a set of equivalence classes using "$A$ and $B$ are equivalent if the first $k$ coin tosses they specify are exactly the same". Now, each set $D_i \in \{ D_n \}$ gets partitioned into equivalence classes such that the total number of equivalence classes created (from all $D_i$) is equal to the number of equivalence classes $\bigcup D_i$ is partitioned into. From there, I think you can make an argument that $\sum_i P(D_i) = P \bigg ( \bigcup D_i \bigg )$. – Marcel Mar 10 at 10:29
• e.g., if $k = 3$, then $A_{01}$ would get partitioned into $A_{01} = A_{010} \cup A_{011}$. You could then make an argument that $P(A_{01}) = P(A_{010} \cup A_{011}) = \frac{ \# \{\text{classes }A_{01} \text{is partitioned into} \} }{2^k} = \frac{2}{8} = \frac{1}{8} + \frac{1}{8} = P(A_{010}) + P(A_{011})$ – Marcel Mar 10 at 10:34
• @Marcel It's been a while since I looked at this, and I'm not able to think it over to give you a good answer anytime soon, sorry. It is entirely possible that there is a better way to answer the problem -- perhaps look at the other answers if you haven't already --, or that I have made a mistake. Thanks for taking the time to think about this question though and to share your thoughts. – majmun May 21 at 2:13

Here is my solution (re-posted from my blog).

PROBLEM STATEMENT:

Suppose that we wish to model the flipping of a countably infinite number of coins. Let the sample space $$\Omega$$ be $$\{(r_{1},r_{2},\ldots) \vert r_{i} = 0$$ or $$1\}$$.

For each $$n \in \mathbb{N}$$ and each $$a_{1},\ldots,a_{n} \in \{0,1\}$$, let $$A_{a_{1}\ldots a_{n}} \subseteq \Omega$$ be $$\{(r_{1},r_{2},\ldots) \in \Omega \vert r_{i} = a_{i}$$ for $$i \leq i \leq n\}$$. It is straightforward to show that the set of all such $$A_{a_{1}\ldots a_{n}}$$ along with $$\{\emptyset,\Omega\}$$ forms a semialgebra. Call this set $$\mathbb{I}$$. Define a function $$P$$ on this set with $$P(A_{a_{1}\ldots a_{n}})=\frac{1}{2^n}$$, $$P(\emptyset)=0$$, and $$P(\Omega)=1$$.

The exercise is to show that $$P$$ is "finitely additive" on $$\mathbb{I}$$ in the following sense: whenever $$A=\cup_{i=1}^{n}A_{i}$$ with $$A,A_{1},\ldots ,A_{n}$$ disjoint elements of $$\mathbb{I}$$, then $$P(A)=\Sigma_{i=1}^{n} P(A_{i})$$. (This is a step towards applying Carathéodory's extension theorem, which allows us to conclude that $$P$$ can be extended to a probability measure defined on a $$\sigma$$-algebra $$\mathbb{F}$$ with $$\mathbb{I} \subseteq \mathbb{F}$$.)

SOLUTION:

Say that the "length" of an element $$A_{a_{1}\ldots a_{n}}$$ of $$\mathbb{I}$$ is $$n$$. (Also define the length of $$\emptyset$$ to be 0 and the length of $$\Omega$$ to be $$\infty$$.) For any $$k>n$$, $$A_{a_{1}\ldots a_{n}}$$ is the disjoint union of all sets of the form $$A_{a_{1}\ldots a_{n} a_{n+1} \ldots a_{k}}$$, where $$a_{n+1} \ldots a_{k}$$ ranges over all possible assignments of $$0$$ and $$1$$ to those values. Notice that there are $$2^{(k-n)}$$ such sets, each of which has $$P(A_{a_{1}\ldots a_{n} a_{n+1} \ldots a_{k}})=\frac{1}{2^{k}}$$. Label these sets (in whatever order you like) as $$B_j$$, $$j \in \{1,2,\ldots,2^{(k-n)}\}$$. It follows, then, that $$P(A_{a_{1}\ldots a_{n}} )=\frac{1}{2^n}=\Sigma_{j=1}^{2^{(k-n)}}P(B_{j})$$, since $$\Sigma_{j=1}^{2^{(k-n)}}P(B_{j})=2^{k-n}\frac{1}{2^k}=\frac{1}{2^n}$$. To put this observation informally, the probabilities work out "correctly" when you decompose a length $$n$$ element into a disjoint union of length $$k$$ elements, where $$k>n$$.

Suppose that A is a non-empty set such that $$A=\cup_{i=1}^{n}A_{i}$$ with $$A,A_{1},\ldots ,A_{n} \in \mathbb{I}$$. Let $$k$$ be the maximum length of $$A,A_{1},\ldots ,A_{n}$$. Decompose each $$A,A_{1},\ldots ,A_{n}$$ into a disjoint union of elements of $$\mathbb{I}$$, all of which have length $$k$$. Let the length $$k$$ sets associated with $$A_{i}$$ be called $$B_{ij}$$. Say that the number of such sets involved in the decomposition of $$A_{i}$$ is $$n_{i}$$.

We have already shown above that $$P(A_{i})=\Sigma_{j=1}^{n_{i}}P(B_{ij})$$. Now, if we decompose $$A$$ into a disjoint union of length $$k$$ elements of $$\mathbb{I}$$, these length $$k$$ elements must be precisely $$\{B_{ij}\}$$. Thus, $$P(A)=\Sigma_{i,j}P(B_{ij})$$. If we group the terms of this sum appropriately and use the identity $$P(A_{i})=\Sigma_{j=1}^{n_{i}}P(B_{ij})$$, we obtain the identity that we wanted: $$P(A)=\Sigma_{i=1}^{n} P(A_{i})$$.

The argument above assumed that $$A$$ was non-empty. The case of $$A=\emptyset$$ is trivial, since the only disjoint union of element of $$\mathbb{I}$$ that equals $$A=\emptyset$$ is the union of $$\emptyset$$ and nothing else, in which case finite additivity also holds.