mirror of
https://github.com/janishutz/eth-summaries.git
synced 2025-11-25 18:44:24 +00:00
33 lines
1.7 KiB
TeX
33 lines
1.7 KiB
TeX
\newpage
|
|
\subsection{Independence}
|
|
\setcounter{all}{18}
|
|
\fancydef{Independence of two events} Two events $A$ and $B$ are called \textbf{independent} if
|
|
\[
|
|
\Pr[A \cap B] = \Pr[A] \cdot \Pr[B]
|
|
\]
|
|
|
|
\setcounter{all}{22}
|
|
\begin{definition}[]{Independence}
|
|
Events $A_1, \ldots, A_n$ are called \textit{independent}, if for all subsets $I \subseteq \{1, \ldots, n\}$ with $I = \{i_1, \ldots, i_k\}$ and $|I| = k$, we have that
|
|
\[
|
|
\Pr[A_{i_1} \cap \ldots \cap A_{i_k}] = \Pr[A_{i_1}] \cdot \ldots \cdot \Pr[A_{i_k}]
|
|
\]
|
|
\end{definition}
|
|
|
|
The same in simpler terms: If all events $A_1, \ldots, A_n$ are relatively disjoint, they are independent. We can determine if they are, if the probability of the intersection of all events is simply their individual probabilities multiplied with each other.
|
|
|
|
\begin{lemma}[]{Independence}
|
|
Events $A_1, \ldots, A_n$ are independent if and only if for all $(s_1, \ldots, s_n) \in \{0, 1\}^n$ we have
|
|
\[
|
|
\Pr[A_1^{s_1} \cap \ldots \cap A_n^{s_n}] = \Pr[A_1^{s_1}] \cdot \ldots \cdot \Pr[A_n^{s_n}]
|
|
\]
|
|
where $A_i^{0} = \overline{A_i}$ (i.e. $s_i = 0$) and $A_i^{1} = A_i$ (i.e. $s_i = 1$)
|
|
\end{lemma}
|
|
$\{0, 1\}^n$ is the space of $n$-bit binary numbers, representing subsets of the sample space, each of them being any of the subsets intersected with up to $n$ other subsets
|
|
|
|
The $s_i$ in this expression are very straight forward to understand as simply indicating if we consider the event or its complement.
|
|
|
|
\fancylemma{Let $A$, $B$ and $C$ be independent events. Then, $A\cap B$ and $C$ as well $A \cup B$ and $C$ are independent}
|
|
|
|
In this lecture, we are always going to assume that we can use actual random numbers, not just pseudo random numbers that are generated by PRNGs (Pseudo Random Number Generators).
|