# Proof that $2^n-(n+1)$ equations are necessary to establish the independence of n events.

Suppose $A_1,A_2,\cdots,A_n$ are $n$ events, we say that they are all independent if for all $\{i_1,\cdots, i_m\}\subset \{1,2,\cdots,n\}$(where $m\ge 2$), we have $$\mathrm{Pr}[A_{i_1}\cap A_{i_2}\cdots\cap A_{i_m}]=\mathrm{Pr}[A_{i_1}]\times\mathrm{Pr}[A_{i_2}]\cdots\times\mathrm{Pr}[A_{i_m}].$$

One can easily observe that there are $2^n-(n+1)$ relations, my question is that if these relations are all necessary to establish the independence of $A_i$s?(i.e. can one of the relation be derived from any of other relations?)

I think this is necessary, but I don't know how to prove.

Hint: take $X_1,\ldots,X_{n-1}$ as independent random variables with a Bernoulli distribution with $p=\frac{1}{2}$ and define $X_n$ as: $$X_n = X_1+\ldots +X_{n-1}\pmod{2}.$$
• Hi Jack, from your construction I can prove that if any $n-1$ events are all independent we can't say the $n$ events are independent. But what if we have known that all combination of the events are independent except one combination say $A_1, A_2$, can we prove from those relation that $A_1, A_2$ are independent also? – Jow Chieh Sep 2 '15 at 21:45
We just need to show that for every subset $\{i_1,i_2,\cdots,i_m\}\subset\{1,2,\cdots,n\}$ we can construct a probability space $\Omega$ such that all the independent conditions satisfies except $$\mathrm{Pr}[A_{i_1}\cap A_{i_2}\cdots\cap A_{i_m}]=\mathrm{Pr}[A_{i_1}]\times\mathrm{Pr}[A_{i_2}]\cdots\times\mathrm{Pr}[A_{i_m}].\qquad (1)$$
Denote $I=[0,1], A\subset I$, note that the lebesgue measure on $I$ is a natural probability measure. We let the probability space to be $I_1\times I_2\cdots\times I_n$ where $I_i$s are $n$ copies of $I$. Define the events $A_i$s to be subsets $I_1\times I_2\cdots A_i'\times\cdots I_n$, where $A_i'$ is the image subspace of $A$ in $I_i$.
One can easily verify that $A_i$s are all independent. We now modify some space $A_j$ to make condition $(1)$ invalid but do not change other relations. Without lost of generality we may assume $\{i_1,\cdots,i_m\}=\{1,2,\cdots,m\}$. Our purpose is to decrease the volume of $A_1\cap A_2\cdots\cap A_m$, we pick out a small space $S\subset A_1'\times A_2'\times A_m'\times I_{m+1}^c\cdots\times I_n^c$ and $S'\subset A_1'\times A_2'\cdots\times A_{m-1}'\times I_m^c\times \cdots\times I_n^c$ such that $V(S)=V(S')$, let $\hat{A}_m=(A_m-S)\cup S'$.
One can verifies that $A_1,\cdots,\hat{A}_m,\cdots,A_n$ ar as desire.