# Deriving a lower bound of $2^k$ for the size of the sample space $\Omega$

I am trying to derive a lower bound of $$2^k$$ for the size of the sample space $$\Omega$$ given that in the probability space there exists $$k$$ non-trivial independent events. I am not looking for a solution per se, but rather a hint.

I suppose I don't fully understand the connection between the size of an event and the surrounding sample space. Namely I do understand that the fact that the events $$E_1, \dots, E_k$$ are non trivial mean that $$\mathrm{Pr}(E_i) \in (0, 1)$$ or equivalently that each event contains at least one element, but no event contain all elements of the space. But how do you go about deriving the lower bound from this? To me $$2^k$$ speaks that some element has a binary choice to be or not to be included in all of the $$k$$ events in the probability space. $$2^k$$ could also mean the number of possible subsets for $$k$$ elements. However I don't see how either of these reasoning strategies yields anything useful, as they don't take into account the relationships between the events $$E_1, \dots, E_k$$.

• If there are $k$ mutually disjoint events covering the space, each with positive probability, then clearly you can take the power set of these as a subset of the sigma-algebra, though one element of the power set (the empty event) will have probability $0$ and one (the universal event) will have probability $1$, so that would suggest to me $2^n-2$ for your lower bound Apr 26, 2021 at 12:09
• @Henry I just noticed a deadly typo in my text: The events $E_1,\dots,E_k$ should be independent. So the exact form in my material is that given that there are $k$ non-trivial independent events, show that the sample space has a size of at least $2^k$. Apr 26, 2021 at 12:17

For $$\alpha\in \{0,1\}^k$$, consider the event $$C_{\alpha}\equiv \bigcap_{i=1}^kA_i$$, where $$A_i=E_i$$ if $$\alpha_i=0$$ and $$A_i=E_i^c$$ if $$\alpha_i=1$$. Now, $$\mathcal{C}\equiv\{C_{\alpha}:\alpha\in\{0,1\}^k\}$$ is a collection of disjoint (non-empty) events, and $$|\mathcal{C}|=2^k$$.
• So the trick was to model the events in the sample space as binary strings of length $k$? Apr 26, 2021 at 14:36
• If you refer by an event to $C_\alpha$, then why are the elements of $\mathcal{C}$ disjoint? Isn't $C_{\alpha_1} \cap C_{\alpha_2} \neq \varnothing$ if some $A_i = 1$ in both $C_{\alpha_1}$ and $C_{\alpha_2}$? Apr 26, 2021 at 15:18
• No because for $\alpha_1\ne \alpha_2$, $C_{\alpha_1}\cap C_{\alpha_2}\subset E_i\cap E_i^c=\emptyset$ for some $1\le i\le k$.