Probabilistic Events

Previously, we convinced ourselves that given various kinds of finite sets $K$ , we have many techniques to compute $|K|$ . Why we care is to compute probabilities: given a finite set $\Omega$ , we can define the probability measure $\mathbb P := | \cdot |/|\Omega| : \mathcal P(\Omega) \to [0, 1]$ . We say that we are computing the probabilities of events, since the elements of $\mathcal P(\Omega)$ satisfy several desirable properties.

Theorem 1. Call a collection $\mathcal F \subseteq \mathcal P(\Omega)$ a $\sigma$ -algebra over $\Omega$ if it satisfies the following properties:

$\emptyset, K \in \mathcal F$ ,
for any $K \in \mathcal F$ , $\Omega\backslash K \in\mathcal F$ ,
for any $K_1,K_2,\dots \in \mathcal F$ , $\bigcup_{i=1}^\infty K_i \in \mathcal F$ .

Elements of $\mathcal F$ are then called events. Then $\mathcal P(\Omega)$ is a $\sigma$ -algebra.

Henceforth, let $\Omega$ denote a sample space and $\mathcal F$ denote any $\sigma$ -algebra on $\Omega$ .

For any measure $\mu$ on $\mathcal F$ with $\mu(\Omega) < \infty$ , $\mathbb P_{\mu} := \mu(\cdot) / \mu(\Omega)$ is a probability measure on $\mathcal F$ . In particular, these properties hold if $\Omega$ is a finite set and $\mu = | \cdot |$ .

The reason for these seemingly trivial observations and the definition of a $\sigma$ -algebra becomes more apparent when we consider $\Omega$ being an infinite set, say $\mathbb R$ . The collection $\mathcal P(\Omega)$ does still form a $\sigma$ -algebra over $\Omega$ , but it’s entirely unclear how we might assign a meaningful probability measure on $\mathcal P(\Omega)$ . We will explore this idea later on.

For now, let’s take a look at the elements of $\mathcal F$ .

Lemma 1. For any $K, L \in \mathcal F$ , $K \cap L, K \backslash L \in \mathcal F$ . Furthermore, for any $K, L \in \mathcal F$ , there exists $K_0, L_0 \in \mathcal F$ such that $K \cup L = K_0 \cup L_0$ and $K_0 \cap L_0 = \emptyset$ . In the latter, we say that $K, L$ are mutually exclusive.

Proof. By set complementation and de Morgan’s laws,

$K \cap L = \Omega \backslash (\Omega \backslash (K \cap L)) = \Omega \backslash (\Omega \backslash K \cup \Omega \backslash L) \in \mathcal F.$

Similarly, $K \backslash L = K \cap (\Omega \backslash L) \in \mathcal F$ . For the disjoint union claim, define $L_0 := K \backslash L \in \mathcal F$ .

Furthermore, we state the various measure properties on $\mathcal F$ . One key property defining measures is countable additivity, of which we get finite additivity as a special case:

$\mu(K \sqcup L) = \mu(K) + \mu(L),\quad K, L \in \mathcal F.$

Here, we write the disjoint union $K \sqcup L$ to refer to the set $K \cup L$ if $K \cap L = \emptyset$ .

Lemma 2. We have the following properties for any measure $\mu$ :

for $K, L \in \mathcal F$ , $\mu(K) = \mu(K \backslash L) + \mu(K \cap L)$ ,
if there exists $K \in \mathcal F$ such that $\mu(K) < \infty$ , then $\mu(\emptyset) = 0$ ,
for $K, L \in \mathcal F$ , $\mu(K \cup L) + \mu(K \cap L) = \mu(K) + \mu(L)$ ,
for $K, L \in \mathcal F$ , if $K \subseteq L$ , then $\mu(K) \leq \mu(L)$ .

Proof. For the set-difference claim,

$\begin{aligned} K &= K \cap \Omega \\ &= K \cap (L \sqcup \Omega \backslash L) \\ &= (K \cap L) \sqcup (K \cap \Omega \backslash L) \\ &= (K \cap L) \sqcup K \backslash L. \end{aligned}$

Then the result becomes immediate since

$\mu(K) = \mu(K \cap L) + \mu(K \backslash L).$

For the empty-set claim, the first result yields

$\mu(K) = \mu(K \cap K) + \mu(K \backslash K) = \mu(K) + \mu(\emptyset).$

Since $\mu(K) < \infty$ , subtracting on both sides yields $\mu(\emptyset) = 0$ .

For the set-union claim,

$\begin{aligned} \mu(K \cup L) &= \mu(K \sqcup L \backslash K) \\ &= \mu(K) + \mu(L \backslash K).\end{aligned}$

Adding $\mu(K \cap L)$ on both sides,

$\begin{aligned} \mu(K \cup L) + \mu(K \cap L) &= \mu(K) + \mu(L \backslash K) + \mu(K \cap L) \\ &= \mu(K) + \mu(L). \end{aligned}$

Finally, for the subset claim, we recall that $K \subseteq L$ implies that $K \cup L = L$ and replace $L$ with $L \backslash K$ and use the empty-set claim to obtain

$\begin{aligned} \mu(K) &\leq \mu(K) + \mu(L \backslash K) \\ &= \mu(K \cup L \backslash K) + \mu(K \cap L \backslash K) \\ &= \mu(K \cup L) + \mu(\emptyset) \\ &= \mu(L) + 0 = \mu(L). \end{aligned}$

Theorem 2. For any probability measure $\mathbb P$ on $\mathcal F$ , we have the following properties:

$\mathbb P(\emptyset) = 0$ ,
for $K, L \in \mathcal F$ , $\mathbb P(K \cup L) = \mathbb P(K) + \mathbb P(L) - \mathbb P(K \cap L)$ ,
for $K, L \in \mathcal F$ , if $K \subseteq L$ , then $\mathbb P(K) \leq \mathbb P(L)$ .

In fact, these properties hold if $\mathbb P$ is replaced by any finite measure $\mu$ .

Proof. For any $K \in \mathcal F$ , $K \subseteq \Omega$ and $\mathbb P(K) \leq \mathbb P(\Omega) = 1$ , and all properties hold for Lemma 2.

Mutually exclusive events therefore help us take advantage of the measure properties to do case-splitting analysis whenever needed, summarised by the law of total probability:

Theorem 3. Suppose there exists $K_1, \cdots , K_n \in \mathcal F$ such that $\Omega = \bigsqcup_{i=1}^n K_i$ . Then for any $K \in \mathcal F$ ,

$\displaystyle \mathbb P(K) = \sum_{i=1}^n \mathbb P(K \cap K_i).$

Proof. Apply finite additivity onto the decomposition

$\displaystyle K = K \cap \Omega = K \cap \bigsqcup_{i=1}^n K_i = \bigsqcup_{i=1}^n (K \cap K_i).$

—Joel Kindiak, 25 Jun 25, 2312H

KindiakMath

Probabilistic Events

Response

Leave a reply to The Union Bound – KindiakMath Cancel reply

Probabilistic Events

Share this:

Response

Leave a reply to The Union Bound – KindiakMath Cancel reply