Multiple events

When we have more than two events, there can be many different degrees of independence. Let $A_1,\ldots, A_n$ be events. We say that they are pairwise independent if every pair $A_i$ and $A_j$ are independent for all $i \neq j$. Pairwise independence is a relatively weak form of independence. These events $A_1,\ldots, A_n$ are said to be (fully) independent if, for every subset $I \subseteq [n]$, we have

${\mathbb P}[\bigcap_{i \in I} A_i] = \prod_{i \in I} {\mathbb P}[A_i]$

Example 38

Toss two unbiased coins. Let $A$ be the event that the first coin is head; $B$ the event that the second coin is head; and $C$ that the number of heads is exactly one. Therefore we have that ${\mathbb P}[A]= {\mathbb P}[B] = {\mathbb P}[C] = 1/2$. These events are not fully independent, i.e., ${\mathbb P}[C \mid A \cap B] = 0 < {\mathbb P}[C]$, so they are not fully independent. However, they are pairwise independent. It is easy to see that $A$ and $B$ are independent. As for $A$ and $C$, notice that $A \cap C = \{10\}$, so ${\mathbb P}[A \cap C] = 1/4 = {\mathbb P}[A] \cdot {\mathbb P}[C]$.

Exercise 98

Prove: If $A_1,\ldots, A_n$ are independent, then $\overline{A}_1, A_2,\ldots, A_n$ are independent.

Exercise 99

Define $A^1 = A$ and $A^{-1} = \overline{A}$. Prove: If $A_1,\ldots, A_n$ are independent, then so are $A_1^{\epsilon_1}, A_2^{\epsilon_2},\ldots, A_n^{\epsilon_n}$ for all choices of $\epsilon_1,\ldots, \epsilon_n \in \{-1,1\}$.

Exercise 100

Consider the probability space of (unbiased) coin tossing. Let $A_i$ be the event that the $i$-th coin toss is head. Prove that the events $\{A_i\}$ are fully independent.

Exercise 101 (Independence is expensive)

Assume that in our sample space, there are $n$ (different) nontrivial and independent events. Show that $|\Omega| \geq 2^n$.

In computer science, when we design randomized algorithms, we are often interested in saving space consumption. Roughly, if the sample space is $\Omega$, then the space needed is at least $\lg_2 |\Omega|$. The above exercise implies that if our algorithm relies on a lot of independent events, the algorithm necessarily consumes a lot of space!

Example 39

Construct a sample space where there are $n$ pairwise balanced (probability is $1/2$) events and $|\Omega| \leq 2n$.

Proof:

Let $k \in {\mathbb N}$ so that $2^{k-1} \leq n \leq 2^k-1$ (do you see why such $k$ always exists?). Consider the uniform probability space on $\Omega = \{0,1\}^k$ (so these are $k$ tossings of a fair coin). We claim that there are $2^k-1$ pairwise independent events in this space. For each non-empty subset $S \subseteq [k]$, we define an event $E_S = \{x \in \Omega: \bigoplus_{i \in S} x_i = 1\}$ (the notation is for XOR). We claim that these events are pairwise independent (see Exercise below).

We will argue that ${\mathbb P}[E_S] = 1/2$ (balanced). This can be proved by the following induction hypothesis:

$I(q): {\mathbb P}[E_S] = 1/2\ (\forall S: |S|=q>0)$

When $q=1$, it is clear that ${\mathbb P}[E_S]=1/2$. Otherwise, assume that $I(q)$ is true and consider the set $S$ of size $q+1$. Let $i \in S$ and $T = S \setminus \{i\}$. We write $\bigoplus_{j \in S} x_j = x_i \oplus (\bigoplus_{j \in T} x_j)$. Therefore,

${\mathbb P}[E_S] = {\mathbb P}[x_i =0] \cdot {\mathbb P}[E_T \mid x_i=0] + {\mathbb P}[x_i=1]\cdot {\mathbb P}[\overline{E_T} \mid x_i = 1]$

Since the event $E_T$ is independent of event $(x_i =1)$, we have that ${\mathbb P}[E_T \mid x_i=0]= {\mathbb P}[E_T] =1/2$ and ${\mathbb P}[\overline{E_T} \mid x_i =1] = {\mathbb P}[\overline{E_T}] = 1/2$ (by induction hypothesis). Substituting this back into the equation gives ${\mathbb P}[E_S]= 1/2$. Notice that we have $2^k-1 \geq n$ events, and the size of sample space is $2^k$ (which is at most $2n$). This completes the proof.

Exercise 102

Prove that the events $\{E_S\}_{S \subseteq [k]: S \neq \emptyset}$ are pairwise independent. In particular, show that for $S \neq T$, we have ${\mathbb P}[E_S \cap E_T] = {\mathbb P}[E_S] \cdot {\mathbb P}[E_T]$.

Between full independence and pairwise independence lies the whole hierarchy of increasingly high degree of independence, that we call $k$-wise independence. In particular, events $A_1,\ldots, A_n$ are $k$-wise independent if, for every $k$-subset $I \subseteq [n]$, the events $(A_i)_{i \in I}$ are independent.