Does k-wise independence imply (k-1) independence?

Question

For example, if I have bits that are 4-wise independent, can I say they are 3-wise independent? How do I prove this?

Answer 1

Let the $4$ bits be random variables $A$, $B$. $C$, $D$. We want to prove, for example, that $A,B,C$ are independent. So we want to prove that $$\Pr(A=a\cap B=b\cap C=c)=\Pr(A=a)\Pr(B=b)\Pr(C=c).$$ The event $A=a\cap B=b\cap C=c$ can happen in two disjoint ways: (i) the equalities hold and $D=0$ or (ii) the equalities hold and $D=1$. Let $p$ be the probability that $D=0$. Then by $4$-wise independence we have $$\Pr(A=a\cap B=b\cap C=c\cap D=0)= \Pr(A=a)\Pr(B=b)\Pr(C=c)p.$$ Similarly, $$\Pr(A=a\cap B=b\cap C=c\cap D=1)= \Pr(A=a)\Pr(B=b)\Pr(C=c)(1-p).$$ Add. We get $$\Pr(A=a\cap B=b\cap C=c)=\Pr(A=a)\Pr(B=b)\Pr(C=c)(p+(1-p))=\Pr(A=a)\Pr(B=b)\Pr(C=c).$$