Law of Total Probability (Discrete, From First Principles)

Short walkthrough of the law of total probability in the discrete setting, using notation common in TCS: a finite domain $\mathcal{X}$, distributions $p(x)$ on $\mathcal{X}$, and events as subsets of $\mathcal{X}$.

1. Discrete distributions on a finite domain

Let $\mathcal{X}$ be a finite domain of size $k$, $\mathcal{X} = [k] = \{1,2,\dots,k\}$.

A discrete distribution on $\mathcal{X}$ is a function

such that

For an event $A \subseteq \mathcal{X}$, define

Two basic rules:

1. Additivity for disjoint events
   If $A_1,\dots,A_m \subseteq \mathcal{X}$ are pairwise disjoint, then

   $$p\Big(\bigcup_{i=1}^m A_i\Big) = \sum_{i=1}^m p(A_i).$$

2. Conditional probability (with $p(B) > 0$):

   $$p(A \mid B) = \frac{p(A \cap B)}{p(B)}.$$

Rewriting:

2. Partitions and the law of total probability

A family of events $B_1, \dots, B_m \subseteq \mathcal{X}$ is a partition of $\mathcal{X}$ if

1. $B_i \cap B_j = \varnothing$ for all $i \neq j$ (disjoint),
2. $\bigcup_{i=1}^m B_i = \mathcal{X}$ (they cover the domain).

Exactly one $B_i$ holds for each $x \in \mathcal{X}$.

Take any event $A \subseteq \mathcal{X}$. Because the $B_i$ cover $\mathcal{X}$,

and the sets $(A \cap B_i)$ are disjoint.

By additivity,

Using $p(A \cap B_i) = p(A \mid B_i)\,p(B_i)$, we get

This is the law of total probability in this notation:

3. Coin example in this notation

We define the randomness of the process as a distribution $p$ over a finite domain $\mathcal{X}$.

Setup

There are two coins:

• Coin $F$ (fair): $p(\text{H} \mid F) = 0.5$
• Coin $B$ (biased): $p(\text{H} \mid B) = 0.9$

Step 1: pick a coin.

• $p(F) = 0.7$
• $p(B) = 0.3$

Step 2: flip the chosen coin once.

Define the domain

The distribution $p$ on $\mathcal{X}$ is:

• $p(F,H) = p(F)\,p(H \mid F) = 0.7 \cdot 0.5 = 0.35$
• $p(F,T) = 0.7 \cdot 0.5 = 0.35$
• $p(B,H) = 0.3 \cdot 0.9 = 0.27$
• $p(B,T) = 0.3 \cdot 0.1 = 0.03$

Check:

We care about the event

Then

Now let’s express the same calculation using the law of total probability.

Using a partition

Define events in $\mathcal{X}$:

• $B_1$: “coin is $F$”
  $B_1 = \{(F,H), (F,T)\}$
• $B_2$: “coin is $B$”
  $B_2 = \{(B,H), (B,T)\}$

$\{B_1,B_2\}$ is a partition of $\mathcal{X}$.

We have:

• $p(B_1) = p(F) = 0.7$

• $p(B_2) = p(B) = 0.3$

• $p(A \mid B_1) = p(\text{H} \mid F) = 0.5$

• $p(A \mid B_2) = p(\text{H} \mid B) = 0.9$

Apply the law:

Same result, but now written as a sum of conditional probabilities over a partition.

4. Randomized algorithms: how to use this

View the randomness of an algorithm as a distribution $p$ over a finite domain $\mathcal{X}$ (all possible random choices, random bits, etc.).

Let:

• $B_1, \dots, B_m \subseteq \mathcal{X}$ be a partition encoding cases:
  e.g. “pivot is good”, “pivot is bad”, or “hash function is $i$”.
• $A \subseteq \mathcal{X}$ be the event that the algorithm succeeds (or runs in time $\le T$, etc.).

Then

Decompose larger probability into smaller conditional pieces:

1. Partition into cases $B_1,\dots,B_m$:
   e.g. “Case 1: pivot is good”, “Case 2: pivot is bad”.
2. For each case $i$, compute or bound $p(A \mid B_i)$.
3. Compute or bound $p(B_i)$.
4. Plug into $$p(A) = \sum_{i=1}^m p(A \mid B_i)\,p(B_i).$$

This is exactly the law of total probability applied to the distribution $p$ induced by the algorithm’s randomness.

5. Summary

1. Fix a finite domain $\mathcal{X}$ and a distribution $p$ on it.
2. Choose a partition $B_1,\dots,B_m$ of $\mathcal{X}$.
3. For any event $A \subseteq \mathcal{X}$, write $$A = \bigcup_{i=1}^m (A \cap B_i)$$ with $(A \cap B_i)$ disjoint.
4. Use additivity: $$p(A) = \sum_{i=1}^m p(A \cap B_i).$$
5. Use conditional probability: $$p(A \cap B_i) = p(A \mid B_i)\,p(B_i).$$
6. Combine: $$p(A) = \sum_{i=1}^m p(A \mid B_i)\,p(B_i).$$