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$
Best Answer
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)