3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – BCLC Jan 5 '16 at 5:53
  • $\begingroup$ stat.ualberta.ca/~schmu/stat571/n1.pdf $\endgroup$ – BCLC Jan 5 '16 at 6:01
  • $\begingroup$ 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. $\endgroup$ – majmun Jan 5 '16 at 17:46
2
+100
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – majmun Jan 8 '16 at 16:57
  • $\begingroup$ @majmun Yes, it is a concatenation, but of finite words from the set $\{0,1\}^\infty=\bigcup_{n=0}^\infty \{0,1\}^n$ $\endgroup$ – Alex Ravsky Jan 8 '16 at 17:05
  • $\begingroup$ 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. $\endgroup$ – majmun Jan 9 '16 at 2:30
  • $\begingroup$ @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. $\endgroup$ – Alex Ravsky Jan 10 '16 at 19:15
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – majmun Jan 5 '16 at 21:45
  • $\begingroup$ 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 )$. $\endgroup$ – Marcel Mar 10 at 10:29
  • $\begingroup$ 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})$ $\endgroup$ – Marcel Mar 10 at 10:34
  • $\begingroup$ @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. $\endgroup$ – majmun May 21 at 2:13
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.