Prove or disprove: Suppose $X_{1}, \ldots, X_{n}$ are distinct Bernoulli random variables with $p=1 / 2$ (fair coin flips). If every subset of $n-1$ random variables is independent, then the full set of random variables $\left\{X_{1}, \ldots, X_{n}\right\}$ is independent. Does the truth or falseness of this statement depend on the value of $n$ ?
I think answer if False. I showed it for $n=3$ case. I took $a_1, a_2, a_3$ iid coin flips, then $X_1 = 1$ if $a_1 \neq a_2$, $X_2 = 1$ if $a_2 \neq a_3$, $X_3 = 1$ if $a_1 \neq a_3$, then we get that $P(X_1=1,X_2=1,X_3=1) = 0$ whereas $P(X_i=1,X_j=1) = 1/4$.
I don't know how to generalize that for $n$ case.
Best Answer
Suppose $X_1,\ldots,X_{n-1}$ are independent and for each $i\in\{1,\ldots,n\}$ you have $\Pr(X_i=1)=1/2 = \Pr(X_i=0).$
Let $X_n$ be the mod $2$ sum of $X_1,\ldots,X_{n-1},$ i.e. $X_n=1$ if and odd number of $X_1,\ldots,X_{n-1}$ are equal to $1$ and $0$ if even.
Then see you you can show that every set of $n-1$ of $X_1,\ldots,X_n$ is independent.