Difference between revisions of "Theory of Stochastic Signals/Set Theory Basics"

Revision as of 22:18, 14 November 2021

Venn diagram, universal and empty set

Set representation in the Venn diagram

In later chapters, we will sometimes refer to set theory . Therefore, the most important basics and definitions of this discipline will be briefly summarized here. The topic is also covered in the (German language) learning video
"Mengentheoretische Begriffe und Gesetzmäßigkeiten" ⇒ "Set Theory – Terms and Regularities"

An important tool of set theory is the Venn diagramm according to the graph:

Applied to probability theory, here the events $A_i$ are represented as areas. For a simpler description we do not denote the events here with $A_1$, $A_2$ and $A_3$, but with $A$, $B$ and $C$ in contrast to the last chapter.
The total area corresponds to the "universal set" (or short: "universe") $G$. The universe $G$ contains all possible outcomes and stands for the certain event, which by definition occurs with probability „one”: ${\rm Pr}(G) = 1$. For example, in the random experiment "Throwing a die", the probability for the event "The number of eyes is less than or equal to 6" is identical to one.
In contrast, the empty set $ϕ$ does not contain a single element. In terms of events, the empty set specifies the impossible event with probability ${\rm Pr}(ϕ) = 0$ an. For example, in the experiment "Throwing a die", the probability for the event "The number of eyes is greater than 6" is identically zero.

Note that not every event $A$ with ${\rm Pr}(A) = 0$ can really never happen. For example:

The event "The noise value $n$ is identically zero" is vanishingly small and ${\rm Pr}(n \equiv 0) = 0$, if $n$ is described by a continuous (Gaussian) random variable.
Nevertheless, it is of course possible (although extremely unlikely) that at some point the exact noise value $n = 0$ will also occur.

Union set

Some set-theoretical relationss are explained now on the basis of the Venn diagram.

$\text{Definition:}$ The union set $C$ of two sets $A$ and $B$ contains all the elements that are contained either in set $A$ or in set $B$ or in both.

This relationship is expressed as the following formula:

$$\ C = A \cup B \hspace{0.2cm}(= A + B).$$

In the literature, especially in the Galois field $\rm GF(2)$ the term "sumset" is common, and the plus sign is sometimes used.

For example, in our tutorial we use this term in the book "Channel Coding".

Union set in the Venn diagram

Using the diagram, it is easy to see the following laws of set theory:

$$A \cup \it \phi = A \rm \hspace{3.6cm}(union \hspace{0.15cm}with \hspace{0.15cm}the \hspace{0.15cm}empty \hspace{0.15cm}set),$$

$$A\cup G = G \rm \hspace{3.6cm}(union \hspace{0.15cm}with \hspace{0.15cm}the \hspace{0.15cm}universe),$$

$$A\cup A = A \hspace{3.6cm}(\rm tautology),$$

$$A\cup B = B\cup A \hspace{2.75cm}(\rm commutative \hspace{0.15cm}property),$$

$$(A\cup B)\cup C = A\cup (B\cup C) \hspace{0.45cm}(\rm associative \hspace{0.15cm}property).$$

If nothing else is known about the event sets $A$ and $B$ then only a lower bound and an upper bound can be given for the probability of the union set:

$${\rm Max}\big({\rm Pr} (A), \ {\rm Pr} (B)\big) \le {\rm Pr} (A \cup B) \le {\rm Pr} (A)+{\rm Pr} (B).$$

The probability of the union set is equal to the lower bound if $A$ is a subset of $B$ or vice versa.
The upper bound holds for disjoint sets.

$\text{Example 1:}$ We consider again the experiment "throwing a die". The possible outcomes (number of points) are thus $E_μ ∈ G = \{1, 2, 3, 4, 5, 6\}$.

Consider the two events

$A :=$ "The outcome is greater than or equal to $5$"$ = \{5, 6\}$ ⇒ ${\rm Pr} (A)= 2/6= 1/3$,
$B :=$ "The outcome is even" $= \{2, 4, 6\}$ ⇒ ${\rm Pr} (B)= 3/6= 1/2$,

then the union set contains four elements: $(A \cup B) = \{2, 4, 5, 6 \}$ ⇒ ${\rm Pr} (A \cup B) = 4/6 = 2/3$.

For the lower bound: ${\rm Pr} (A \cup B) \ge {\rm Max}\big({\rm Pr} (A),\ {\rm Pr} (B)\big ) = 3/6.$
For the upper bound: $ {\rm Pr} (A \cup B) \le {\rm Pr} (A)+{\rm Pr} (B) = 5/6.$

Intersection set

Another important set-theoretic linkage is the intersection.

$\text{Definition:}$ The intersection set $C$ of two sets $A$ and $B$ contains all those elements which are contained in both the set $A$ and the set $B$.

This relationship is expressed as the following formula:

$$C = A \cap B \hspace{0.2cm}(= A \cdot B).$$

In the literature, especially in the Galois field $\rm GF(2)$ the term "Cartesian product" is also common, and the multiplication sign is sometimes used.

For example, in our tutorial we use this term in the book "Channel Coding".

Intersection set in the Venn diagram

In the diagram, the intersection is shown in purple. Analog to the union set, the following regularities are to be mentioned here:

$$A \cap \it \phi = \it \phi \rm \hspace{3.75cm}(intersection \hspace{0.15cm}with \hspace{0.15cm}the \hspace{0.15cm}empty \hspace{0.15cm}set),$$

$$A \cap G = A \rm \hspace{3.6cm}(intersection \hspace{0.15cm}with \hspace{0.15cm}the \hspace{0.15cm}universe),$$

$$A\cap A = A \rm \hspace{3.6cm}(tautology),$$

$$A\cap B = B\cap A \rm \hspace{2.75cm}(commutative \hspace{0.15cm}property),$$

$$(A\cap B)\cap C = A\cap (B\cap C) \rm \hspace{0.45cm}(associative \hspace{0.15cm}property).$$

If nothing else is known about $A$ and $B$ , then no statement can be made for the probability of the intersection.
However, if ${\rm Pr} (A) \le 1/2$ and at the same time ${\rm Pr} (B) \le 1/2$ hold, then a lower bound and an upper bound can be given:

$$0 \le {\rm Pr} (A ∩ B) \le {\rm Min}\ \big({\rm Pr} (A),\ {\rm Pr} (B)\big ).$$

${\rm Pr}(A ∩ B)$ is sometimes called the "joint probability" and is denoted by ${\rm Pr}(A, \ B)$ .
${\rm Pr}(A ∩ B)$ is equal to the upper bound if $A$ is a subset of $B$ or vice versa.
The lower bound is obtained for the joint probability of disjoint sets.

$\text{Example 2:}$ We consider again the experiment "throwing a die". The possible outcomes (number of points) are thus $E_μ ∈ G = \{1, 2, 3, 4, 5, 6\}$. Consider the two events

$A :=$ „the outcome is greater than or equal to $5$”$ = \{5, 6\}$ ⇒ ${\rm Pr} (A)= 2/6= 1/3$, und
$B :=$ „the outcome is even”$ = \{2, 4, 6\}$ ⇒ ${\rm Pr} (B)= 3/6= 1/2$,

The intersection contains only one element: $(A ∩ B) = \{ 6 \}$ ⇒ ${\rm Pr} (A ∩ B) = 1/6$.

The upper bound is obtained as ${\rm Pr} (A ∩ B) \le {\rm Min}\ \big ({\rm Pr} (A), \, {\rm Pr} (B)\big ) = 2/6.$
The lower bound of the intersection here is zero because of ${\rm Pr} (A) \le 1/2$ and ${\rm Pr} (B) \le 1/2$ .

Complementary set

$\text{Definition:}$ The complementary set of $A$ is often denoted by a straight line above the letter $(\overline{A})$ . It contains all the elements that are not contained in the set $A$ and it holds for their probability:

$${\rm Pr}(\overline{A}) = 1- {\rm Pr}(A).$$

Complementary set in the Venn diagram

In the Venn diagram shown, the set complementary to $A$ is shaded. From this diagram, some set-theoretic relationships can be seen:

The complementary set of the complementary set of $A$ is the set $A$ itself:

$$\overline{\overline{A}} = A.$$

The union of a set $A$ with its complementary set gives the universal set:

$${\rm Pr}(A \cup \overline{A}) = {\rm Pr}(G) = \rm 1.$$

The intersection of $A$ with its complementary set gives the empty set:

$${\rm Pr}(A \cap \overline{A}) = {\rm Pr}({\it \phi}) \rm = 0.$$

$\text{Example 3:}$ We consider again the experiment "throwing a die". The possible outcomes (number of points) are thus $E_μ ∈ G = \{1, 2, 3, 4, 5, 6\}$. Starting from the set

$A :=$ „the outcome is smaller than $5$” $= \{1, 2, 3, 4\}$ ⇒ ${\rm Pr} (A)= 2/3$

the corresponding complementary set is

$\overline{A} :=$ „the outcome is greater than or equal to $5$”$ = \{5, 6\}$ ⇒ ${\rm Pr} (\overline{A})= 1 - {\rm Pr} (A) = 1 - 2/3 = 1/3.$

Strict subset – improper subset

Subsets in the Venn diagram

$\text{Definitions:}$ One calls $A$ a strict subset of $B$ and writes for this $A ⊂ B$,

if all elements of $A$ are also contained in $B$ ,
but not all elements of $B$ are also contained in $A$.

In this case, the probabilities are:

$${\rm Pr}(A) < {\rm Pr}(B).$$

This set-theoretic relation is illustrated by the sketched Venn diagram.

On the other hand, $A$ is called a subset of $B$ and uses the notation

$$A \subseteq B = (A \subset B) \cup (A = B),$$

wenn $A$ entweder eine echte Teilmenge von $B$ ist oder wenn $A$ und $B$ gleiche Mengen sind.

The relation ${\rm Pr} (A) \le {\rm Pr} (B)$ then applies to the probabilities.
The equality sign is only valid for the special case $A = B$.

In addition, however, the two equations known as the laws of absorption also apply:

$$(A \cap B) \cup A = A ,$$

$$(A \cup B) \cap A = A,$$

since the intersection $A ∩ B$ is always a subset of $A$ , but at the same time $A$ is also a subset of the union $A ∪ B$ .

$\text{Example 4:}$ We consider again the experiment "throwing a die". The possible outcomes (number of points) are thus $E_μ ∈ G = \{1, 2, 3, 4, 5, 6\}$. Consider the two events

$A :=$ „the outcome is uneven”$ = \{1, 3, 5\}$ ⇒ ${\rm Pr} (A)= 3/6$, und
$B :=$ „the outcome is a prime number” $= \{1, 2, 3, 5\}$ ⇒ ${\rm Pr} (B)= 4/6$.

It can be seen that $A$ is a (strict) subset of the set $B$ . Accordingly, ${\rm Pr} (A) < {\rm Pr} (B)$is also true.

Theoreme von de Morgan

rechts

Bei vielen Aufgaben aus der Mengenlehre sind die beiden Theoreme von de Morgan äußerst nützlich. Diese lauten:

$$\overline{A \cup B} = \overline{A} \cap \overline{B},$$

$$\overline{A \cap B} = \overline{A} \cup \overline{B}.$$

Diese Gesetzmäßigkeiten sind im Schaubild veranschaulicht:

Die Menge $A$ ist rot dargestellt und die Menge $B$ blau.
Die Komplentärmenge $\overline {A}$ von $A$ ist in horizontaler Richtung schraffiert.
Die Komplentärmenge $\overline {B}$ von $B$ ist in vertikaler Richtung schraffiert.
Das Komplement $\overline{A \cup B}$ der Vereinigungsmenge ${A \cup B}$ ist sowohl horizontal als auch vertikal schraffiert.
Es ist damit gleich der Schnittmenge $\overline{A} \cap \overline{B}$ der beiden Komplentärmengen von $A$ und $B$:

$$\overline{A \cup B} = \overline{A} \cap \overline{B}.$$

Auch die zweite Form des de Morgan-Theorems lässt sich mit diesem Venndiagramm grafisch verdeutlichen:

Die Schnittmenge $A ∩ B$ (im Bild violett dargestellt) ist weder horizontal noch vertikal schraffiert.
Das Komplement $\overline{A ∩ B}$ der Schnittmenge ist dementsprechend entweder horizontal, vertikal oder in beiden Richtungen schraffiert.
Nach dem zweiten Theorem von de Morgan ist das Komplement der Schnittmenge gleich der Vereinigungsmenge der beiden Komplentärmengen von $A$ und $B$:

$$\overline{A \cap B} = \overline{A} \cup \overline{B}.$$

$\text{Beispiel 5:}$ Wir betrachten die beiden Mengen

$A : =$ „die Augenzahl ist ungeradzahlig” $= \{1, 3, 5\}$,
$B : =$ „die Augenzahl ist größer als $2$” $= \{3, 4, 5, 6\}$.

Daraus folgen die beiden komplementären Mengen

$\overline {A} : =$ „die Augenzahl ist geradzahlig” $= \{2, 4, 6\}$,
$\overline {B} : =$ „die Augenzahl ist kleiner als $3$” $= \{1, 2\}$.

Weiter erhält man mit den obigen Theoremen die folgenden Teilmengen:

$$\overline{A \cup B} = \overline{A} \cap \overline{B} = \{2\}\hspace{0.5 cm}\rm und \hspace{0.5cm} \overline{\it A \cap \it B} =\overline{\it A} \cup \overline{\it B} = \{1,2,4,6\}.$$

Disjunkte Mengen

$\text{Definition:}$ Zwei Mengen $A$ und $B$ nennt man disjunkt (englisch: disjoint) oder miteinander unvereinbar,

wenn es kein einziges Element gibt,
das sowohl in $A$ als auch in $B$ enthalten ist.

rechts

Das Schaubild zeigt zwei disjunkte Mengen $A$ und $B$ im Venndiagramm.

In diesem Sonderfall gelten die folgenden Aussagen:

Die Schnittmenge zweier disjunkter Mengen $A$ und $B$ ergibt stets die leere Menge:

$${\rm Pr}(A \cap B) = {\rm Pr}(\phi) = \rm 0.$$

Die Wahrscheinlichkeit der Vereinigungsmenge zweier disjunkter Mengen $A$ und $B$ ist immer gleich der Summe der beiden Einzelwahrscheinlichkeiten:

$${\rm Pr}( A \cup B) = {\rm Pr}( A) + {\rm Pr}(B).$$

$\text{Beispiel 6:}$ Bei unserem Standardexperiment sind die beiden Mengen

$A :=$ „die Augenzahl ist kleiner als $3$”$ = \{1, 2\}$ ⇒ ${\rm Pr}( A) = 2/6$, und
$B :=$ „die Augenzahl ist größer als $3$” $ = \{4, 5,6\}$ ⇒ ${\rm Pr}( B) = 3/6$

zueinander disjunkt, da $A$ und $B$ kein einziges gemeinsames Element beinhalten.

Die Schnittmenge ergibt die leere Menge: ${A \cap B} = \phi$.
Die Wahrscheinlichkeit der Vereinigungsmenge ${A \cup B} = \{1, 2, 4, 5, 6\}$ ist gleich ${\rm Pr}( A) + {\rm Pr}(B) = 5/6.$

Additionstheorem

Nur bei disjunkten Mengen $A$ und $B$ gilt für die Wahrscheinlichkeit der Vereinigungsmenge der Zusammenhang ${\rm Pr}( A \cup B) = {\rm Pr}( A) + {\rm Pr}(B)$. Wie errechnet sich diese Wahrscheinlichkeit aber bei allgemeinen, nicht notwendigerweise disjunkten Ereignissen?

Zum Additionstheorem der Wahrscheinlichkeitsrechnung

Betrachten Sie das rechte Venndiagramm mit der violett dargestellten Schnittmenge $A ∩ B$.

Die rote Menge beinhaltet alle Elemente, die zu $A$ gehören, aber nicht zu $B$.
Die Elemente von $B$, die nicht gleichzeitig in $A$ enthalten sind, sind blau dargestellt.
Alle roten, blauen und violetten Flächen zusammen ergeben die Vereinigungsmenge $A ∪ B$.

Aus dieser mengentheoretischen Darstellung erkennt man folgende Zusammenhänge:

$${\rm Pr}(A) \hspace{0.8cm}= {\rm Pr}(A \cap B) + {\rm Pr}(A \cap \overline{B}),$$

$${\rm Pr}(B) \hspace{0.8cm}= {\rm Pr}(A \cap B) \rm +{\rm Pr}(\overline{A} \cap {B}),$$

$${\rm Pr}(A \cup B) ={\rm Pr}(A \cap B) +{\rm Pr} ({A} \cap \overline{B}) \rm + {\rm Pr}(\overline{A} \cap {B}).$$

Addiert man die ersten beiden Gleichungen und subtrahiert davon die dritte, so erhält man:

$${\rm Pr}(A) \rm +{\rm Pr}(B) -{\rm Pr}(A \cup B) = {\rm Pr}(A \cap B).$$

$\text{Definition:}$ Durch Umstellen dieser Gleichung kommt man zum sogenannten Additionstheorem (englisch: Addition Rule) für zwei beliebige, nicht notwendigerweise disjunkte Ereignisse:

$${\rm Pr}(A \cup B) = {\rm Pr}(A) + {\rm Pr}(B) - {\rm Pr}(A \cap B).$$

$\text{Beispiel 7:}$ Wir betrachten die beiden Mengen

$A :=$ „die Augenzahl ist ungeradzahlig” $= \{1, 3, 5\}$ ⇒ ${\rm Pr}(A) = 3/6$, und
$B :=$ „die Augenzahl ist größer als $2$”$ = \{3, 4, 5, 6\}$ ⇒ ${\rm Pr}(B) = 4/6$.

Damit ergeben sich für die Wahrscheinlichkeiten

der Vereinigungsmenge ⇒ ${\rm Pr}(A ∪ B) = 5/6$, und
der Schnittmenge ⇒ ${\rm Pr}(A ∩ B) = 2/6$.

Die Zahlenwerte zeigen die Gültigkeit des Additionstheorems: $5/6 = 3/6 + 4/6 − 2/6$.

Vollständiges System

Im letzten Abschnitt zu diesem Kapitel betrachten wir wieder mehr als zwei mögliche Ereignisse, nämlich allgemein $I$. Diese Ereignisse werden im Folgenden mit $A_i$ bezeichnet, und es gilt für den Laufindex: $1 ≤ i ≤ I$.

$\text{Definition:}$ Eine Konstellation mit den Ereignissen $A_1, \hspace{0.1cm}\text{...}\hspace{0.1cm} , A_i, \hspace{0.1cm}\text{...}\hspace{0.1cm} , A_I$ bezeichnet man dann und nur dann als ein vollständiges System, wenn die beiden folgenden Bedingungen erfüllt sind:

(1) Alle Ereignisse sind paarweise disjunkt:

$$A_i \cap A_j = \it \phi \hspace{0.15cm}\rm f\ddot{u}r\hspace{0.15cm}alle\hspace{0.15cm}\it i \ne j.$$

(2) Die Vereinigung aller Ereignismengen ergibt die Grundmenge:

$$\bigcup_{i=1}^{I} A_i = G.$$

Aufgrund dieser beiden Voraussetzungen gilt dann für die Summe aller Wahrscheinlichkeiten:

$$\sum_{i =1}^{ I} {\rm Pr}(A_i) = 1.$$

$\text{Beispiel 8:}$ Die Ereignismengen $A_1 := \{1, 5\}$ und $A_2 := \{2, 3\}$ ergeben beim Zufallsexperiment "Werfen eines Würfels" zusammen mit der Menge $A_3 := \{4, 6\}$ ein vollständiges System, nicht jedoch beim Experiment "Werfen einer Roulettekugel".

$\text{Beispiel 9:}$ Ein weiteres Beispiel für ein vollständiges System ist die diskrete Zufallsgröße $X = \{ x_1, x_2, \hspace{0.1cm}\text{...}\hspace{0.1cm} , x_I\}$ mit den Auftrittswahrscheinlichkeiten entsprechend der folgenden Wahrscheinlichkeitsfunktion:

$$P_X(X) = \big [ \hspace{0.1cm} P_X(x_1), P_X(x_2), \hspace{0.05cm}\text{...}\hspace{0.15cm}, P_X(x_I) \hspace{0.05cm} \big ] = \big [ \hspace{0.1cm} p_1, p_2, \hspace{0.05cm}\text{...} \hspace{0.15cm}, p_I \hspace{0.05cm} \big ] \hspace{0.05cm}$$

$$\Rightarrow \hspace{0.3cm} p_1 = P_X(x_1) = {\rm Pr}(X=x_1) \hspace{0.05cm}, \hspace{0.2cm}p_2 = {\rm Pr}(X=x_2) \hspace{0.05cm},\hspace{0.05cm}\text{...}\hspace{0.15cm},\hspace{0.2cm} p_I = {\rm Pr}(X=x_I) \hspace{0.05cm}.$$

Die möglichen Ergebnisse $x_i$ der Zufallsgröße $X$ sind paarweise zueinander disjunkt und die Summe aller Auftrittswahrscheinlichkeiten $p_1 + p_2 + \hspace{0.1cm}\text{...}\hspace{0.1cm} + \hspace{0.05cm} p_I$ liefert grundsätzlich das Ergebnis $1$.

$\text{Beispiel 10:}$ Es gelte $X= \{0, 1, 2 \}$ und $P_X (X) = \big[0.2, \ 0.5, \ 0.3\big]$. Dann gilt:

$${\rm Pr}(X=0) = 0.2 \hspace{0.05cm}, \hspace{0.2cm} {\rm Pr}(X=1) = 0.5 \hspace{0.05cm}, \hspace{0.2cm} {\rm Pr}(X=2) = 0.3 \hspace{0.05cm}.$$

Bei der Zufallsgröße $X = \{1, \pi, {\rm e} \}$ und gleichem $P_X(X) = \big[0.2, \ 0.5, \ 0.3\big]$ lauten die Zuordnungen:

$${\rm Pr}(X=1) = 0.2 \hspace{0.05cm}, \hspace{0.2cm} {\rm Pr}(X=\pi) = 0.5 \hspace{0.05cm}, \hspace{0.2cm} {\rm Pr}(X={\rm e}) = 0.3 \hspace{0.05cm}.$$

Hinweise:

Die Wahrscheinlichkeitsfunktion $P_X(X)$ macht nur Aussagen über die Wahrscheinlichkeiten, nicht über den Wertevorrat $\{x_1, x_2, \hspace{0.1cm}\text{...}\hspace{0.1cm} , x_I\}$ der Zufallsgröße $X$.
Diese zusätzliche Information liefert die Wahrscheinlichkeitsdichtefunktion (WDF).

Aufgaben zum Kapitel

Aufgabe 1.2: Schaltlogik (D/B-Wandler)

Aufgabe 1.2Z: Ziffernmengen

Aufgabe 1.3: Fiktive Uni Irgenwo

Aufgabe 1.3Z: Gewinnen mit Roulette?

@@ Line 151: / Line 151: @@
-In addition, however, the two equations known as the&nbsp; '''laws of absorption'''&nbsp also apply:
+In addition, however, the two equations known as the&nbsp; '''laws of absorption'''&nbsp; also apply:
 :$$(A \cap B)  \cup A  =  A ,$$
 :$$(A  \cup B) \cap A  =  A,$$