3
$\begingroup$

I'm looking for a combinatorial argument to complete a proof (below) of the following:

Claim: If $(\Omega,2^\Omega,P)$ is a probability space with finite $\Omega,$ then $\sum_{A\in2^\Omega}P(A)=2^{|\Omega|-1}.$

In other words, if $\Omega$ is finite and every subset of $\Omega$ is considered an event, then the sum of all the event-probabilities must equal $2^{|\Omega|-1}.$

Proof: Let $\Omega=\{\omega_1,...,\omega_n\}$ and $p_i=P(\{\omega_i\}).$ Then, by summing over subsets of successively larger size,
$$\begin{align*}&\sum_{A\in\cal 2^\Omega}P(A)\\ &=P(\emptyset)+\sum_{1\le i_1\le n}P\{\omega_{i_1}\}+\sum_{1\le i_1<i_2\le n}P(\{\omega_{i_1},\omega_{i_2}\})+...+\sum_{1\le i_1<...<i_t\le n}P(\{\omega_{i_1},...,\omega_{i_t}\})+...+P(\Omega)\\[3ex] &=\sum_{1\le i_1\le n}p_{i_1}+\sum_{1\le i_1<i_2\le n}(p_{i_1}+p_{i_2})+...+\sum_{1\le i_1<...<i_t\le n}(p_{i_1}+...+p_{i_t})+...+P(\Omega)\\[3ex] &\overset{(*)}{=}\binom{n-1}{1-1}+\binom{n-1}{2-1}+...+\binom{n-1}{t-1}+...+\binom{n-1}{n-1}\\[3ex] &=2^{n-1} \end{align*}$$

The step marked $\overset{(*)}{=}$ would be justified by showing that in every sum $\sum_{1\le i_1<...<i_t\le n}(p_{i_1}+...+p_{i_t}),$ for $t=1,...,n,$ each of the $p_i (i=1,...,n)$ appears exactly $\binom{n-1}{t-1}$ times (noting of course that the sum of the $p_i (i=1,...,n)$ is $1$).

For example, if $n=4$ then for $t=2$ we have

$\sum_{1\le i_1<i_2\le 4}(p_{i_1}+p_{i_2})=(p_1+p_2)+(p_1+p_3)+(p_1+p_4)+(p_2+p_3)+(p_2+p_4)+(p_3+p_4)=3,$

as we see that each $p_i$ appears $\binom{4-1}{2-1}=3$ times.

Can anyone provide insight as to why this is generally the case? (Or perhaps give an alternative method of proof?)


EDIT: As mentioned in comments, the accepted answer provides a method that proves the following much more general result:

If $(\Omega,\mathcal F,P)$ is a probability space with finite $\sigma$-field $\mathcal F$, then $\sum_{A\in\mathcal F}P(A)={1\over 2}|\mathcal F|.$

I.e., "the sum of all the event-probabilities must equal half the number of events".

$\endgroup$

2 Answers 2

12
$\begingroup$

I think it's simpler to use that $P(A) + P(\overline A) = 1$. Note that $2^\Omega = \{A | A \subseteq \Omega\} = \{\overline A | A \subseteq \Omega\}$. So, we have

$$2 \cdot \sum_{A \in 2^\Omega} P(A) = \sum_{A \in 2^\Omega} P(A) + \sum_{A \in 2^\Omega} P(\overline A) = \sum_{A \in 2^\Omega} P(A) + P(\overline A) = \sum_{A \in 2^\Omega} 1 = 2^{|\Omega|}$$

$\endgroup$
7
  • $\begingroup$ Very neat! If I'm not mistaken, we can do similarly even when the event-field $\cal F\ne 2^\Omega$; viz., $\mathcal F=\{A|A\in\mathcal F\}=\{\overline A|A\in\mathcal F\},$ so $2 \cdot \sum_{A \in \mathcal F} P(A) = \sum_{A \in \mathcal F} P(A) + \sum_{A \in \mathcal F} P(\overline A) = \sum_{A \in \mathcal F} 1 = |\mathcal F|.$ And I notice that the title claim still holds when $\Omega$ is not finite, as "half of infinity is infinity". In other words, the claim holds for all probability spaces $(\Omega,\mathcal F,P)$!? $\endgroup$
    – r.e.s.
    May 25 at 0:03
  • $\begingroup$ @r.e.s. What is the definition of a sum of more than a countably infinite set of real numbers? $\endgroup$ May 25 at 2:49
  • $\begingroup$ @DilipSarwate I should have been more careful, as I'm not sure there's a reasonable definition that allows the kind of statement I was making. Putting the infinite case aside, is it correct that the claim holds for all finite probability spaces, for any field of events? $\endgroup$
    – r.e.s.
    May 25 at 3:35
  • $\begingroup$ It holds for any finite space, but that's not interesting, as any finite space can be factored by relation "two points are equal if any event containing one contains the other". $\endgroup$
    – mihaild
    May 25 at 8:48
  • $\begingroup$ @DilipSarwate Still I wonder what can be said when the sigma-field is countably infinite; i.e., in that case are there really no conditions that would ensure a well-defined sum? $\endgroup$
    – r.e.s.
    May 25 at 14:09
3
$\begingroup$

Here is a proof by switching the order of summation. First, write $$ \sum_{A\subseteq\Omega } P(A) =\sum_{A\subseteq \Omega}\sum_{\omega\in A}P(\omega) $$ We can think of $\sum_{A\subseteq \Omega}\sum_{\omega\in A}P(\omega)$ as the sum of $P(\omega)$ over all ordered pairs $(\omega, A)$ such that $\omega\in A$. Switching the order of summation, we think of this as $\sum_{\omega\in \Omega}\sum_{A\ni \omega}P(\omega)$, where the inner summation ranges over all events $A$ which contain $\omega$. Since the summand $P(\omega)$ in the inner sum does depend on the summation index $A$, you can pull it out, resulting in $$ \sum_{A\subseteq \Omega}P(\omega)\sum_{A\ni\omega}1 $$ To compute this inner summation, you just need to count the number of events containing $\omega$. This number is obviously $2^{n-1}$, and the rest is easy.

$\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.