Anki Deck Changes

It is zero outside \(W_X\). The density function the random variable's distribution.

Paarweise \(\not \implies\) vollen Schnitt: Zwei faire Münzen, \(A=\)„\(M_1\) Kopf", \(B=\)„\(M_2\) Kopf", \(C=\)„Ergebnisse verschieden": je zwei Ereignisse sind unabhängig, aber \(\Pr[A\cap B\cap C]=0\neq\tfrac{1}{8}=\Pr[A]\Pr[B]\Pr[C]\).
Voller Schnitt \(\not \implies\) paarweise: Zufallszahl in \(\{1,\ldots,8\}\), \(A=\{1,2,3,4\}\), \(B=\{1,5,6,7\}\), \(C=B\): \(\Pr[A\cap B\cap C]=\tfrac{1}{8}=\Pr[A]\Pr[B]\Pr[C]\), aber \(\Pr[A\cap B]=\tfrac{1}{8}\neq\tfrac{1}{4}=\Pr[A]\Pr[B]\).

Beide Bedingungen zusammen sind nötig — daher fordert Def. 2.22 die Produktregel für alle nichtleeren Teilmengen.

Proof:
Using Lemma 2.29 (\(\mathbb{E}[X]=\sum_\omega X(\omega)\Pr[\omega]\)):
\[ \mathbb{E}[X]=\sum_\omega(a_1X_1(\omega)+\cdots+a_nX_n(\omega)+b)\Pr[\omega] =a_1\underbrace{\sum_\omega X_1(\omega)\Pr[\omega]}_{=\mathbb{E}[X_1]}+\cdots+b\underbrace{\sum_\omega\Pr[\omega]}_{=1}.\quad\square \]
The key is that the outer sum \(\sum_\omega\) distributes over the linear combination.

Proof:
\[ \mathbb{E}[X]=\sum_{x}x\cdot\Pr[X=x]\overset{\text{total prob.}}{=}\sum_x x\sum_i\Pr[X=x|A_i]\Pr[A_i] =\sum_i\Pr[A_i]\underbrace{\sum_x x\Pr[X=x|A_i]}_{=\mathbb{E}[X|A_i]}.\quad\square \]
(Uses the law of total probability to expand \(\Pr[X=x]\), then swaps summation order.)

The definition requires the product rule for every non-empty sub-intersection — not just pairwise intersections, and not just the full \(n\)-fold intersection. Both conditions alone are insufficient:
Pairwise \(\not \implies\) full intersection: two fair coins, \(A=\)"\(M_1\) heads", \(B=\)"\(M_2\) heads", \(C=\)"results differ" are pairwise independent but \(\Pr[A\cap B\cap C]=0\neq\Pr[A]\Pr[B]\Pr[C]\).
Full intersection \(\not \implies\) pairwise: \(A=\{1,2,3,4\}\), \(B=\{1,5,6,7\}\), \(C=B\) in \(\{1,\ldots,8\}\): \(\Pr[A\cap B\cap C]=\Pr[A]\Pr[B]\Pr[C]\) but \(A,B\) are not independent.

The total number of conditions to check for \(n\) events is \(2^n-1\) (all non-empty subsets of \(\{1,\ldots,n\}\)).

Proof: By definition \(\Pr[A_i|B]=\Pr[A_i\cap B]/\Pr[B]\). Numerator: \(\Pr[A_i\cap B]=\Pr[B|A_i]\cdot\Pr[A_i]\). Denominator: \(\Pr[B]=\sum_j\Pr[B|A_j]\Pr[A_j]\) (total probability). \(\square\)

Key use: "Invert" the direction of conditioning — from \(\Pr[B|A_i]\) (easy to measure) to \(\Pr[A_i|B]\) (what we want to know).

Proof:
\[ \mathbb{E}[X]=\sum_{x\in W_X}x\cdot\Pr[X=x]=\sum_{x\in W_X}x\cdot\sum_{\omega: X(\omega)=x}\Pr[\omega]=\sum_{\omega\in\Omega}X(\omega)\cdot\Pr[\omega].\quad\square \]
(Switch the order of summation: group by \(\omega\) instead of by value \(x\).)

Proof:
\[ \mathbb{E}[X]=\sum_{i=0}^{\infty}i\cdot\Pr[X=i]=\sum_{i=0}^{\infty}\sum_{j=1}^{i}\Pr[X=i]=\sum_{j=1}^{\infty}\sum_{i=j}^{\infty}\Pr[X=i]=\sum_{j=1}^{\infty}\Pr[X\ge j].\quad\square \]
(The key step is swapping the order of summation: instead of summing over \(i\) and counting 1 for each \(j\le i\), sum over \(j\) and count all \(i\ge j\).)

Proof sketch (⇒): Induction on the number of zeros in \((s_1,\ldots,s_n)\).
Base case (\(s_i=1\) for all \(i\)): direct from definition.
Inductive step (say \(s_1=0\)):
\(\Pr[\bar{A}_1\cap A_2^{s_2}\cap\cdots] = \Pr[A_2^{s_2}\cap\cdots]-\Pr[A_1\cap A_2^{s_2}\cap\cdots]\)
\(= \Pr[A_2^{s_2}]\cdots\Pr[A_n^{s_n}]-\Pr[A_1]\Pr[A_2^{s_2}]\cdots\Pr[A_n^{s_n}]\)
\(= (1-\Pr[A_1])\Pr[A_2^{s_2}]\cdots\Pr[A_n^{s_n}] = \Pr[\bar{A}_1]\Pr[A_2^{s_2}]\cdots\Pr[A_n^{s_n}]\). \(\square\)

It is non-decreasing, right-continuous, with \(F_X\to 0\) as \(x\to-\infty\) and \(F_X\to 1\) as \(x\to+\infty\).

The expected value is only defined if the sum converges absolutely, i.e., \(\sum_{x\in W_X}|x|\cdot\Pr[X=x]<\infty\).

If the sum does not converge absolutely (e.g., the positive and negative parts both diverge), \(\mathbb{E}[X]\) is undefined.

For finite probability spaces this is always satisfied (finitely many terms). For infinite spaces, care is needed.

\(\Pr[\text{first heads at flip }k] = (1/2)^k\).

The sum in Definition 2.27:
\[ \sum_{k=1}^{\infty}(-1)^{k-1}\cdot 2^k\cdot (1/2)^k = \sum_{k=1}^{\infty}(-1)^{k-1} = +1-1+1-1+\cdots \]
This series does not converge (it oscillates), so \(\mathbb{E}[G]\) is undefined.

Similarly: if the bank always pays \(2^k\), each term equals 1 and the sum diverges to \(+\infty\).

Need: \(\Pr[\bar{A}\cap B]=\Pr[\bar{A}]\cdot\Pr[B]\).

\[ \Pr[\bar{A}\cap B] = \Pr[B] - \Pr[A\cap B] = \Pr[B] - \Pr[A]\Pr[B] = (1-\Pr[A])\Pr[B] = \Pr[\bar{A}]\Pr[B]. \quad\square \]

Consequence: If \(A_1,\ldots,A_n\) are mutually independent, so is any family obtained by replacing some \(A_i\) with \(\bar{A}_i\) (Lemma 2.23).

Let \(B=A_1\cup\cdots\cup A_n\). We want \(\Pr[B]=1-\Pr[\bar{B}]\).

Note: \(I_{\bar{B}}=\prod_{i=1}^n(1-I_{A_i})\) (since \(\bar{B}\) occurs iff all \(A_i\) fail).

Expand the product:
\[ I_{\bar{B}}=1-\sum_{i}I_{A_i}+\sum_{i_1
Apply \(\mathbb{E}[\cdot]\) and use:
\(\mathbb{E}[I_{A_i}]=\Pr[A_i]\)
\(\mathbb{E}[I_{A_{i_1}}\cdots I_{A_{i_k}}]=\Pr[A_{i_1}\cap\cdots\cap A_{i_k}]\) (product of indicators = indicator of intersection)

Taking expectations gives exactly the inclusion-exclusion formula for \(\Pr[\bar{B}]=1-\Pr[B]\). \(\square\)

Proof:
Decompose: \(B = (B\cap A_1)\cup\cdots\cup(B\cap A_n)\) (disjoint parts).
Apply Additionssatz: \(\Pr[B] = \sum_i \Pr[B\cap A_i]\).
Use \(\Pr[B\cap A_i] = \Pr[B|A_i]\cdot\Pr[A_i]\) (from definition of conditional probability). \(\square\)

Use: Decompose a complex event into simpler cases (the \(A_i\) form a partition of the relevant universe).

Indicator variables are also called Bernoulli variables. They are the bridge between events and random variables: the probability of an event equals the expected value of its indicator.

Every indicator \(X_A\) is a \(\text{Bernoulli}(\Pr[A])\) random variable. The name "indicator" reflects the fact that \(X_A(\omega)=1\) precisely when \(\omega\) "indicates" that \(A\) has occurred.

Proof: \(\mathbb{E}[X_A]=1\cdot\Pr[X_A=1]+0\cdot\Pr[X_A=0]=\Pr[A].\quad\square\)

This is the bridge between events (probability) and random variables (expectation): an event's probability equals the expected value of its indicator.

This is because once we fix the conditioning event \(B\), all standard probability axioms apply within the conditional space.