\problemdata
{proof}
{independence}
{random variable}
{Eric Ho, S02}
\begin{problem}
Let $B_1,\dots, B_n$ be independent Bernoulli variables, with $\pr{B_i =
1} = 1/2$ for $1 \le i \le n$.  Let $D \eqdef B_1 \oplus \cdots \oplus
B_n$ where $\oplus$ is sum mod 2.  Prove that any set of $n$ among the
$n+1$ variables $B_1,\dots, B_n, D$ are mutually independent, but all
$n+1$ are not mutually independent.

\solution{

Note that $\pr{D=1}= 1/2$ because it is the sum of the probabilities of
$2^{n}/2$ cases of $B_{1}^{(x_1)} \oplus \cdots \oplus B_{n}^{(x_n)}$ with
an even number of $x_i$'s equal to one, where $B^{1}\eqdef B$, and
$B^{-1}\eqdef \bar{B}$.  But because the $B_i$'s are mutually independent,
each case of $B_1 \oplus \cdots \oplus B_n$ has probability $2^{-n}$, so
the sum of these probabilities is $1/2$.

Also, $B_1,\dots, B_n, D$ are not mutually independent, since whether or
not each of $B_1,\dots, B_n$ is equal to one determines whether or not $D$
is equal to one.

By symmetry among the $B_i$'s, to show $n$-way independence, we need only
show that $D,B_2,\dots, B_n$ are mutually independent.  If $B_2^{(x_2)}
\oplus \dots \oplus B_n^{(x_n)}$ for $x_i = \pm 1$ is equal to one, then we
know that $D$ equals $B_1^{(\pm 1)}$.  In either case, the conditional
probability of $D$ will be the same of that of $B_1$.  But the conditional
probability of $B_1$ remains 1/2 because it is mutually independent of
$B_2,\dots,B_n$.  Hence the conditional probability of $D$ also remains
$1/2$, proving that $D$ is independent of $B_2,\dots, B_n$.}

\end{problem}


