6. Probability

Sample space: Set $\Omega =\{{\omega }_1,{\omega }_2,\dots \}$ of elementary events. $0\le \mathrm{Pr}[{\omega }_i]\le 1$ and ${\sum }_{\omega \in \Omega }\mathrm{Pr}[\omega ]=1$.

Event: Set $E\subseteq \Omega$. $\mathrm{Pr}[E]:={\sum }_{\omega \in E}\mathrm{Pr}[\omega ]$. $\bar{E}=\Omega \setminus E$.

Addition Theorem

Theorem

$A_1,\dots ,A_n$ pairwise disjunct. Then:

$$\mathrm{Pr}\left[\bigcup \right]$$

Wegen Siebformel:

$$N_k=k-\left(\genfrac{}{}{0ex}{}{k}{2}\right)+\left(\genfrac{}{}{0ex}{}{k}{3}\right)-\left(\genfrac{}{}{0ex}{}{k}{4}\right)+\dots \pm \left(\genfrac{}{}{0ex}{}{k}{k}\right)$$

Using binomic formula:

$$(x-y{)}^k=x^k-k\cdot x^{k-1}+\dots$$

for $x=y=1$: $⟹0=N_k-1$ $⟹N_k=1$

Independence

Def: $A_1,\dots ,A_n$ are independent if for all subsets $\mathrm{Pr}[A_{i_1}\cap \dots \cap A_{i_k}]=\mathrm{Pr}[A_{i_1}]\cdots \mathrm{Pr}[A_{i_k}]$

Intuition: After $A_{i_1},\dots ,A_{i_{k-1}}$ occurred, $A_{i_k}$ is as probable as before.

Lemma

$A_1,\dots ,A_n$ independent $⟺$ they are independent if we replace any number of $A_i$ by $\overline{A_i}$.

Lemma

$A,B,C$ independent $⟹$ $A\cap B$ and $C$ as well as $A\cup B$ and $C$ independent.

Stable Set

Independent variables