Probability notes from set theory to more advanced

Set theory

• Universal set (sample space) $\Omega$: all possible outcomes.
• Event: any subset $A \subseteq \Omega$.
• Empty event $\emptyset$: never occurs.
  Certain event $\Omega$: always occurs.
• Set operations:
  • Union: $A \cup B$ — “$A$ or $B$ happens.”
  • Intersection: $A \cap B$ — “$A$ and $B$ happen.”
  • Complement: $A^c = \Omega \setminus A$ — “$A$ does not happen.”
  • Difference: $A \setminus B = A \cap B^c$.
• Disjoint (mutually exclusive): $A \cap B = \emptyset$.

These operations satisfy Boolean algebra rules:

Sigma-algebra

collection of measurable events To define probabilities consistently, we use a σ-algebra $\mathcal{F}$ over $\Omega$:

1. $\Omega \in \mathcal{F}$.
2. If $A \in \mathcal{F}$, then $A^c \in \mathcal{F}$.
3. If $A_1, A_2, \ldots \in \mathcal{F}$, then $\bigcup_i A_i \in \mathcal{F}$.

This ensures we can take complements and countable unions safely.

Basic probability spaces

• Sample space: $\Omega$ (all outcomes). An event $A\subseteq\Omega$.
• Probability measure $\Pr[\cdot]$ satisfies $0\le\Pr[A]\le1$, $\Pr[\Omega]=1$, countable additivity.
• Example: fair coin $\Omega=\{H,T\}$, $\Pr[H]=\Pr[T]=1/2$.

Conditional probability & product rule

• Conditional probability of $A$ given $B$ (with $\Pr[B]>0$): $$\Pr[A\mid B]=\frac{\Pr[A\cap B]}{\Pr[B]}.$$
• Product rule (equivalent): $$\Pr[A\cap B]=\Pr[A\mid B]\Pr[B]=\Pr[B\mid A]\Pr[A].$$

Independence

• $A$ and $B$ are independent iff $$\Pr[A\cap B]=\Pr[A]\Pr[B],$$ equivalently $\Pr[A\mid B]=\Pr[A]$ (when $\Pr[B]>0$).
• For random variables $X,Y$: independence means events $\{X\in I\}$ and $\{Y\in J\}$ independent for all measurable $I,J$.

Law of total probability

• If $B_1,\dots,B_n$ partition $\Omega$ (mutually disjoint, $\bigcup_i B_i=\Omega$) then for any event $A$: $$\Pr[A]=\sum_{i=1}^n \Pr[A\mid B_i]\Pr[B_i].$$
• Useful to expand $\Pr[A]$ by conditioning on cases.

Expectation and indicator variables

• Indicator of event $A$: $1_A(\omega)=1$ if $\omega\in A$, else $0$.
• Expectation of indicator: $\mathbb{E}[1_A]=\Pr[A]$.
• Linearity: $\mathbb{E}[\sum_i X_i]=\sum_i\mathbb{E}[X_i]$ (no independence required).
• For a discrete r.v. $X$: $\mathbb{E}[X]=\sum_x x\Pr[X=x]$.

Useful identities

• $\Pr[A]=\mathbb{E}[1_A]$.
• $\Pr[A\cup B]=\Pr[A]+\Pr[B]-\Pr[A\cap B]$.
• If $B$ is a Bernoulli($p$) bit independent of other randomness: $\Pr[A]=\Pr[A\mid B=0]\Pr[B=0]+\Pr[A\mid B=1]\Pr[B=1]$ (special case of total law).

Short worked example from our paper (the paper’s setup)

Arthur chooses $b\in\{0,1\}$ uniformly. If $b=0$ he samples $x_0\sim u_k$; if $b=1$ he samples $x_1\sim p$. He sends $x_b$ to Merlin, who outputs $\hat b=1_{S_p}(x_b)$ where $S_p=\{x:p(x)\ge 1/k\}$. Arthur accepts iff $\hat b=b$.

Compute $\Pr[\hat b=b]$:

1. Condition on $b$ (law of total probability): $$\Pr[\hat b=b]=\Pr[\hat b=b\mid b=0]\Pr[b=0]+\Pr[\hat b=b\mid b=1]\Pr[b=1].$$
2. Evaluate each term:
   • If $b=0$: Merlin is correct iff $x_0\notin S_p$, so $\Pr[\hat b=b\mid b=0]=u_k(S_p^c)=1-u_k(S_p)$.
   • If $b=1$: Merlin is correct iff $x_1\in S_p$, so $\Pr[\hat b=b\mid b=1]=p(S_p)$.
3. Since $\Pr[b=0]=\Pr[b=1]=1/2$, $$\Pr[\hat b=b]=\tfrac12\big(1-u_k(S_p)+p(S_p)\big)=\tfrac12\big(1 + (p(S_p)-u_k(S_p))\big).$$
4. Using $p(S_p)-u_k(S_p)=d_{TV}(p,u_k)$ (Scheffé set), if $d_{TV}(p,u_k)\ge\varepsilon_2$ then $$\Pr[\hat b=b]\ge \tfrac12(1+\varepsilon_2).$$