Prove or disprove: independence of random variables

Question

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.

Answer 1

Your counterexample is on the right track , but I think you meant (and ommited to say) that $a_i$ are iid fair coin flips themselves (if so, you should have notated them in uppercase, say $Z_i \in \{ 0,1\}$ - notice also the bad notation).

Another construction for $n=3$. Let $X_1, X_2$ be iid $B(1/2)$ (fair coin flips) and let $X_3 = X_1 + X_2$ where the sum is modulo $2$ (equivalently, $X_3=XOR(X_1,X2)$, exclusive-or operator). Then, again $X_i$ are all fair coins, pairwise independent, but not jointly independent.

The above suggests a generalization for $n>3$. Let $X_1, X_2 \cdots X_{n-1}$ be iid $B(1/2)$ and $X_n = X_1 + X_2 \cdots +X_{n-1}$ (mod $2$). I think it's not difficult to prove that $X_n$ is also $B(1/2)$ and that any $n-1$ subset (actually any proper subset!) is iid.

Answer 2

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.