Prove that independence of events implies independence of arbitrary collection of said events and their complements

I am using the following definition of independence:

Let $$A_1,...,A_n$$ be independent events. Then for any index set $$J \subseteq \{1,...,n\}$$, we have $$P(\cap_{j \in J} A_j) = \prod_{j \in J} P(A_j)$$

I am trying to prove the following theorem:

If $$A_1,...,A_n$$ are independent events, and $$E_1,...,E_n$$ are events such that $$E_k \in \{A_k,A^c_k\}$$ for all $$k \in \{1,...,n\}$$, then the events $$E_1,...,E_n$$ are independent.

I know how to do this for two events $$A_1,A_2$$, by simply exhausting all possible cases. We can prove that $$A_1$$ and $$A^c_2$$ are independent, as follows:

\begin{align} P(A_1 \cap A^c_2) &= P(A_1 \cap A_2) + P(A_1 \cap A^c_2) - P(A_1 \cap A_2) \\&= P\bigl((A_1 \cap A_2) \cup (A_1 \cap A^c_2)\bigl) - P(A_1 \cap A_2) & \text{Disjoint additivity} \\&= P(A_1) - P(A_1 \cap A_2) \\ &= P(A_1) - P(A_1)P(A_2) & \text{Independence of A_1 and A_2} \\ &= P(A_1)\bigl(1 - P(A_2)\bigl) \\ &= P(A_1)P(A^c_2) \end{align}

The same argument of course shows that $$A^c_1$$ and $$A_2$$ are independent. We can also prove that $$A^c_1$$ and $$A^c_2$$ are independent:

\begin{align} P(A^c_1 \cap A^c_2) &= P\bigl( (A_1 \cup A_2)^c \bigl) & \text{De Morgan's laws} \\ &= 1 - P(A_1 \cup A_2) \\ &= 1 - P(A_1) - P(A_2) + P(A_1 \cap A_2) \\ &= 1 - P(A_1) - P(A_2) + P(A_1)P(A_2) & \text{Independence of A and B} \\ &= \bigl(1 - P(A_1)\bigl)\bigl(1 - P(A_2)\bigl)\\ &= P(A^c_1)P(A^c_2) \end{align}

However, I don't know how to generalize this to $$n$$ events. I tried induction, but no luck so far. Exhausting all cases is of course not feasible, so I think that there must be some clever way to reformulate the problem. Does anyone have some pointers in the right direction? Thank you.

Edit: proof attempt inspired by @peek-a-boo:

Lemma I. If $$A_1$$ and $$A_2$$ are independent events, then $$A_1$$ and $$A^c_2$$ are independent, and $$A^c_1$$ and $$A_2$$ are also independent.

Proof. We can prove that $$A_1$$ and $$A^c_2$$ are independent, as follows:

\begin{align*} P(A_1 \cap A^c_2) &= P(A_1 \cap A_2) + P(A_1 \cap A^c_2) - P(A_1 \cap A_2) \\&= P\bigl((A_1 \cap A_2) \cup (A_1 \cap A^c_2)\bigl) - P(A_1 \cap A_2) & \text{Disjoint additivity} \\&= P(A_1) - P(A_1 \cap A_2) \\ &= P(A_1) - P(A_1)P(A_2) & \text{Independence of A_1 and A_2} \\ &= P(A_1)\bigl(1 - P(A_2)\bigl) \\ &= P(A_1)P(A^c_2) \end{align*}

The same argument of course shows that $$A^c_1$$ and $$A_2$$ are independent. $$\qedsymbol$$

Lemma II. If $$A_1,...,A_n$$ are independent events, and $$E_1,...,E_n$$ are events such that $$E_k \in \{A_k,A^c_k\}$$ for all $$k \in \{1,...,n\}$$, then the events $$E_1,...,E_n$$ are independent.

Proof. Let $$n_c$$ be the number of complements, so $$n_c = \#(\{k \in \{1,...,n\}: E_k = A^c_k\})$$. We induct on $$n_c$$.

Suppose first that $$n_c = 1$$, and assume without loss of generality that $$E_1 = A^c_1$$ (if this was not the case, we could simply introduce a new collection of events which is reordered accordingly). Hence $$E_k = A_k$$ for $$k > 1$$. Now consider any index set $$J \subseteq \{1,...,n\}$$. Noting that that $$E_2,...,E_n$$ are independent (since they are a subcollection of the independent sets $$A_1,...,A_n$$) and $$J\backslash\{1\} \subseteq \{2,...,n\}$$, we have $$P(\cap_{j \in J\backslash\{1\}} E_j) = \prod_{j \in J\backslash\{1\}} P(E_j)$$. We now split into two cases:

• $$1 \notin J$$. Then $$J = J\backslash\{1\}$$, so $$P(\cap_{j \in J} E_j) = \prod_{j \in J} P(E_j)$$.

• $$1 \in J$$. Let us see that $$A_1$$ and $$\cap_{j \in J\backslash\{1\}} E_j$$ are independent. $$A_1,...,A_n$$ are independent, and the events $$A_1,...,A_n$$ and $$A_1,E_2,...,E_n$$ are the same. Thus \begin{align*} P(A_1 \cap (\cap_{j \in J\backslash\{1\}} E_j)) &= P(A_1) \prod_{j \in J\backslash\{1\}} P(E_j)\\ &= P(A_1) P(\cap_{j \in J\backslash\{1\}} E_j) \end{align*}

By Lemma I, $$E_1$$ and $$\cap_{j \in J\backslash\{1\}} E_j$$ are independent (recall that $$E_1 = A^c_1$$). Thus \begin{align*} P(\cap_{j \in J} E_j) &= P(E_1 \cap (\cap_{j \in J\backslash\{1\}} E_j)) \\ &= P(E_1) P(\cap_{j \in J\backslash\{1\}} E_j) \\ &= P(E_1) \prod_{j \in J\backslash\{1\}} P(E_j) \\ &= \prod_{j \in J} P(E_j) \end{align*}

Since this holds for any $$J \subseteq \{1,...,n\}$$, we conclude that the events $$E_1,...,E_n$$ are independent. Thus the result of Lemma II is true for $$n_c = 1$$

Now suppose inductively that there exists some $$1 \leq m < n$$ such that the result of Lemma II is true for $$n_c = m$$. We will show that it is also true for $$n_c = m + 1$$. Suppose that $$n_c = m + 1$$, and assume without loss of generality that $$E_k = A^c_k$$ for $$1 \leq k \leq m + 1$$ (again, if this was not the case, we could simply introduce a new collection of events which is reordered accordingly). Consider any index set $$J \subseteq \{1,...,n\}$$.

The events $$\{E_k\}_{k \in \{1,...,m\}} \cup \{A_k\}_{k \in \{m+1,...,m\}}$$ are independent by the inductive assumption, and we have $$\{A_{m+1}\} \cup \{E_k\}_{k \in \{1,...,n\}\backslash\{m+1\}} = \{E_k\}_{k \in \{1,...,m\}} \cup \{A_k\}_{k \in \{m+1,...,m\}}$$. The events $$\{E_j\}_{j \in J\backslash\{m + 1\}}$$ are a subcollection of $$\{A_{m+1}\} \cup \{E_k\}_{k \in \{1,...,n\}\backslash\{m+1\}}$$, and we thus have $$P(\cap_{j \in J\backslash\{m+1\}} E_j) = \prod_{j \in J\backslash\{m+1\}} P(E_j)$$.

We now split into two cases:

• $$m+1 \notin J$$. Then $$J = J\backslash\{m+1\}$$, so $$P(\cap_{j \in J} E_j) = \prod_{j \in J} P(E_j)$$.

• $$m+1 \in J$$. Let us see that $$A_{m+1}$$ and $$\cap_{j \in J\backslash\{m+1\}} E_k$$ are independent. Since the events $$\{A_{m+1}\} \cup \{E_k\}_{k \in \{1,...,n\}\backslash\{m+1\}}$$ are independent by the inductive hypothesis, and $$\{A_{m+1}\} \cup \{E_j\}_{j \in J\backslash\{m+1\}}$$ is a subcollection of $$\{A_{m+1}\} \cup \{E_k\}_{k \in \{1,...,n\}\backslash\{m+1\}}$$, we have \begin{align*} P(A_{m+1} \cap (\cap_{j \in J\backslash\{m+1\}} E_j)) &= P(A_{m+1}) \prod_{j \in J\backslash\{m+1\}} P(E_j) \\ &= P(A_{m+1}) P(\cap_{j \in J\backslash\{m+1\}} E_j) \end{align*} By Lemma I, $$E_{m+1}$$ and $$\cap_{k \in \{1,...,n\}\backslash\{m+1\}} E_k$$ are independent (recall that $$E_{m+1} = A^c_{m+1}$$). Thus \begin{align*} P(\cap_{j \in J} E_j) &= P(E_{m+1} \cap (\cap_{j \in J\backslash\{m+1\}} E_j)) \\ &= P(E_{m+1}) P(\cap_{j \in J\backslash\{m+1\}} E_j) \\ &= P(E_{m+1}) \prod_{j \in J\backslash\{m+1\}} P(E_j) \\ &= \prod_{j \in J} P(E_j) \end{align*}

Since this holds for any $$J \subseteq \{1,...,n\}$$, we conclude that the events $$E_1,...,E_n$$ are independent. Thus the result of Lemma II is true for $$n_c = m + 1$$. By induction, the result is true for any $$n_c$$ with $$1 \leq n_c \leq n$$. It is also true for $$n_c = 0$$, since then the events $$E_1,...,E_n$$ are the same as the events $$A_1,...,A_n$$, which are independent by asumption. Since this covers all possible cases, the proof is complete. $$\qedsymbol$$

• Induction is a good idea. Start by assuming $E_k= A_k$ for all $1\leq k \leq n-1$ and $E_n=A_n^c$. Proving independence here should be straightforward. So by induction on the number of complements of subsets in your list of $E_k$’s, you can conclude the general case. Also here is a much more general result using Dynkin’s $\pi$-$\lambda$ theorem. Sep 26, 2023 at 10:36
• @peek-a-boo Thank you your answer. With some effort, I managed to grind out a proof attempt based on your idea. I started the induction by assuming $E_1 = A^c_1$ rather than $E_n = A^c_n$, since I found that more intuitive. The argument is quite long and tedious, and could probably be simplified considerably. But I think the core ideas are sound. If you have the time, could you do me the favour and check the proof? I would really appreciate it, Sep 27, 2023 at 10:26
• Well I don’t really feel like reading through the induction details, but your base case seems right, so I’m inclined to say the rest is fine :) Sep 27, 2023 at 16:14
• @peek-a-boo Fair enough haha. I'm pretty sure it's correct, so I'll close this. Thanks again! Sep 27, 2023 at 16:31
• @peek-a-boo is the answer I give below more or less what you had in mind? Sep 27, 2023 at 18:53

I am not sure why your answer is so complicated, (Perhaps it is just long, and not complicated?) But I have tried to find the simplest approach :

$$\mathbf{Lemma\ 1:}\$$

Given a finite set of events $$X$$, and some event $$A\in X$$ then

$$X$$ is indt. $$\implies$$ $$X' := (X/\{A\})\cup\{A^c\}$$ is indt.

$$proof$$: Assume $$X$$ is independent, then $$\{A,B\}$$ is independent where $$B := \bigcap_{Y\in X/\{A\}} Y$$

From your original proof for the case of $$2$$ events, $$\{A^c,B\}$$ must be independent, so

\begin{align} P\left( \bigcap_{Y\in X'} Y \right) &= P\left( A^c \cap \bigcap_{Y\in X/\{A\}} Y \right) \\\\ &=P\left( A^c \cap B \right) \\\\ &= P(A)P(B) \\\\ &= \prod_{Y \in X'} P(Y) \end{align}

Thus $$X'$$ is independent. $$\hspace{3cm} \blacksquare$$

Then to prove, given a general set of independent events,

$$A = \{A_1,...,A_k\}$$

That the set

$$E = \{E_1, E_2, ... E_k \}$$

Where $$E_i \in \{ A_i, A_i^c\}$$, is also independent, you can simply start with the set $$A$$, and one by one "toggle" the necessary $$A_i \to A_i^c$$, at each step maintaining independence, and eventually reach $$E$$, which is then also independent. (You could formalise this part by induction if you wanted to, but it should be close enough to trivial for most readers)

• Yes, my proof is essentially the same as yours, just written out in tedious detail. I understand that many steps will seem obvious and unnecessary to most readers, but they don't to me (I am not a mathematician). Particularly the "toggle" part - it seems obvious, but I wasn't sure if it actually works until I wrote it out in detail. Sep 27, 2023 at 20:45
• @JonasE. Ah I see. Yes I agree then that it is very good practice to write something out in the most explicit detail, until you are so certain you could do that if asked, that you start feeling comfortable not doing it from the beginning Sep 27, 2023 at 20:49