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

Question

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.

Answer 1

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).

Answer 2

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