I'm taking a signal analysis course with a strong emphasis on probability. Long story short, the professor is assigning homework from the text which he said was optional, and expects us to learn the material straight out of that text. Many of these problems have to do with probability spaces, something which I feel completely lost with, not to mention set theory in general.

I have here an example problem but would love if someone could help explain a solution in very general terms applying to probability spaces as a whole. Please bear in mind I'm basically floundering in the water until my textbook comes in the mail, and would appreciate a very simple explanation.

The Problem:
A receiver listens to the data stream of zeros until the first one appears.


$S = (0,01, 001, ...)$.


$A = 2^S$

and show that

$(S, A, P)$

is a probability space. Use your own probability measure $P$.

My approach:

I'm dimly aware of the criteria for a probability space, but I'm probably wrong somewhere:

  1. $S$ must be a set: Check.

  2. $A$ must be a sigma-algebra of $S$:

    i) $S \in A$ : What does it mean if $S$ is in $2^S$? How is this expressed in terms of sets?

    ii) $ x \in A \Rightarrow \bar{x} \in A $: What would be the complement of some element in $A$ here? My best guess would be the next element in the sequence; i.e. the complement of 001 would be 0001 because the sequence continues if a 0 is chosen in the third place instead of a one. However, that also works for the infinite elements following 001, and surely they can't all be complements?

    iii) $ x, y \in A \Rightarrow x \cup y \in A$: I'm not sure how to express a union here. Isn't there only one set, the "union" of which would be itself?

  3. $P$ must be a (countably additive) probability measure of $S$:

    The biggest issue here is not with the criteria but the actual construction of this probability measure. It seems to me that each term in the series has half the probability of the one preceding it; i.e. the $nth$ term has a $1/(2^n)$ chance of defining the actual event. This is a geometric series adding to 1, and links to the definition of the sigma-algebra from before, but how do I express this as a probability measure?

    i) $P(S) = 1$ : Check.

    ii) $P($any element of $A) \geq 0 $: Check.

    iii) $P(A \cup B) = P(A) + P(B), A \cap B = \varnothing$: What is the significance of A and B here? An example would be very helpful.

Thanks for any help you can offer, and sorry if the formatting is bad. I made an account and learned a bit of LaTex just to post this conundrum!


I'm guessing what $S$ is supposed to be is something like $\{1, 01, 001, \ldots\}$, the set of all strings of zeroes that end in a one — though you could also set $S = \mathbb{Z}^+$, the set of positive integers: The information we care about in $S = \{1, 01, 001, \ldots\}$ is how long it takes the first one to appear — i.e., the length of the string.

By $\mathcal{A} = 2^S$, we mean the so-called power set of $S$; this is a collection of sets, namely all the subsets of $S$. So, for example, $O = \{1, 001, 00001, \ldots \}$ is a subset of $S$. (Note that $O$ is the subset of all elements in $S$ of odd length.) Perhaps somewhat confusingly, $O$ is an element of $\mathcal{A}$; $\mathcal{A}$ and $S$ live on different levels, with $\mathcal{A}$, a collection of sets, being a higher-order structure than $S$, a set. If $E=\{01, 0001, 000001, \ldots \}$ is the set of all strings of even length, then $E=O^c$. Since both $E$ and $O$ are subsets of $S$, they're both elements of $\mathcal{A}$.

As for your questions —

$S$ is a subset of itself, and so, since $\mathcal{A} = 2^S$ is the collection of all of $S$'s subsets, $S \in \mathcal{A}$. In fact, the definition of the power set oughta cover all of your $\sigma$-algebra questions: Complements and unions of subsets are themselves subsets, and so are included in the power set.

Given the definition of $S$, I can see why it might seem mysterious how one should define $P$: Those things in $S$ aren't numbers. How about this? Let $s_n \in S$ be defined as the string of length $n$ (note that it's unique). For any $A \in \mathcal{A}$, define $P(A) = \sum_{n \; : \; s_n \in A} 1 / 2^n$.

On the final issue, I'll point out that if you show that $P(A\cup B) = P(A) + P(B)$, then you're showing that $P$ is finitely additive. However, you need countable additivity — i.e., $P(\bigcup_{k=1}^\infty A_k) = \sum_{k=1}^\infty P(A_k)$, for any collection of disjoint sets $\{A_k\}_{k=1}^\infty$. We can show this holds like so:

$$P\left(\bigcup_{k=1}^\infty A_k\right) = \sum_{n\; : \;s_n \in \bigcup_{k=1}^\infty A_k} \frac{1}{2^n} = \sum_{k=1}^\infty \sum_{n\; : \;s_n \in A_k} \frac{1}{2^n} = \sum_{k =1}^\infty P(A_k)$$

I hesitate to say that $A$ and $B$ have any significance, per se: They're supposed to be arbitrary sets, at least aside from the fact that they're disjoint. I suppose I would think of them as allowing you to break down a set into smaller sets, which may be easier to work with. As an example, let's say I want the probability that the first one does not appear in a position that's divisible by three — the probability that the length of the string isn't divisible by three. Let $T = \{s_{3n} \in S \}$. Then $1 = P(S) = P(T\cup T^c) = P(T) + P(T^c) = \sum_{k=1}^\infty 1/2^{3k} + P(T^c) = 1/7 + P(T^c)$. So $P(T^c) = 6/7$.

  • $\begingroup$ Thank you, I think I understand the majority of your post. One area where I'm still confused is countability. I understand your example, but another question on this homework references an elementary event in a set S and its probability measure, and says to prove that this information is enough to define the probability space. It then says to "extend this to S-countable or S-uncountable". What does this mean for a probability measure? $\endgroup$ Sep 15 '16 at 13:11
  • $\begingroup$ @ForestLeBlanc An elementary event is one that subsumes a single outcome, for example $\{s_n\}$, for some positive integer $n$. (See en.wikipedia.org/wiki/Elementary_event.) From what you've written, it seems like you're talking about a finite sample space $S$ to start, and then moving on to countable and uncountable. Given $P$, it should be possible to do something like what I have above to show that the three properties hold for finite and countable $S$. [...] $\endgroup$
    – dmk
    Sep 16 '16 at 1:45
  • $\begingroup$ @ForestLeBlanc As for uncountable $S$, I'm by no means an expert on this, but in every uncountable sample space I know of, the probability of an elementary event is $0$. Even if you take the (disjoint) union of all elementary events, you're still adding up a bunch of zeroes: You'll never get $1$. On countability: Basically this means you can enumerate all the elements in $S$, even if it takes forever; for example, it's easy to list those in $S$ above. If a set is uncountable, you can't--e.g., between any two real numbers, there are infinitely more. $\endgroup$
    – dmk
    Sep 16 '16 at 1:48
  • $\begingroup$ Actually, I can think of an uncountable sample space containing elementary events with nonzero probability. (A mixed distribution, for example.) However, it wouldn't need to hold for an arbitrary uncountable sample space. For example, any distribution that's uniform on $[a,b]$ has $P[X=x]=0$ for any $x\in [a,b]$. $\endgroup$
    – dmk
    Sep 16 '16 at 1:54

$2^S$ is a notation for the powerset of $S$; also denoted as $\mathcal P(S)$; the set of all subsets of $S$ (including itself and the emptyset).   That is: $2^S = \{X\mid X\subseteq S\}$

  • $S\in 2^S$ by definition, and is $\varnothing$, since:
    • $S\subseteq S, \varnothing \subseteq S$

The relative complement of $X$ to $S$, is $\overline {X} = S\setminus X = \{y\in S\mid y\notin X\}$

  • Because $\overline X\subset S $ therefore $\overline X \in 2^S$; for any $X\in 2^S$
    • Can you show this?

Since $2^S$ is a set of sets, its elements are sets (and, in fact, subsets of $S$, by definition).

  • $\forall X:\big[X\in 2^S \to X\subseteq S\big]$
    • So can you show $\forall X\,\forall Y :\Big[\big((X\subseteq S)\wedge( Y\subseteq S)\big)~\to~X\cup Y\subseteq S\Big]$

For countably additive, the property you are after is that the probability of the union of countablely many disjoint subsets is the sum of the probability measure of the subsets.   That is $A,B$ must be any two disjoint elements of $2^S$. (Again, that is subsets of $S$.)

  • Does $\forall A\in 2^S\, \forall B\in 2^S:\Big[ A\cap B=\varnothing \to \mathsf P(A\cup B)=\mathsf P(A)+\mathsf P(B)\Big]$
  • $\begingroup$ Thanks, I think I understand the set and subset relation along with the place of disjoint sets. It looks like something went wrong with your definition of complements; I'm getting a math processing error. Can you please elaborate on what a complement is for some element of S? $\endgroup$ Sep 15 '16 at 13:02
  • $\begingroup$ @ForestLeBlanc It's not defined on elements of $S$, but on subsets. $\bar X = S\cap X^\complement$ = $S\setminus X~$ The relative complement of $X$ is the set of elements in $S$ that are not in $X$. $$\bar X = \{y\mid y\in S\wedge y\not\in X\}$$ $\endgroup$ Sep 15 '16 at 13:18

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.