Parity Bit Breaks Four-Wise Independence

Let $\Omega = \{0,1,\ldots,15\}$ with uniform probability, representing all $4$-bit binary strings $b_1 b_2 b_3 b_4$. Define four events: $A_i = \{\omega \in \Omega : b_i(\omega) = 1\}$ for $i = 1,2,3$, and $A_4 = \{\omega \in \Omega : b_1 \oplus b_2 \oplus b_3 = 1\}$ where $\oplus$ denotes XOR. (a) Show that each $A_i$ has probability $1/2$. (b) Prove that $\{A_1, A_2, A_3, A_4\}$ is $3$-wise independent: for every subset of size $3$, the intersection has probability $(1/2)^3$. (c) Compute $P(A_1 \cap A_2 \cap A_3 \cap A_4)$ and show that $4$-wise independence fails. (d) Explain why the parity event $A_4$ is fundamentally constrained by $A_1, A_2, A_3$.