maximal number of independent subsets (bitstrings with uniform distribution)?

Question

Let $B=\{0,1\}^n$ be the set of length $n$ bit-strings with the uniform distribution, and let $\mathcal{F}=\{f:B\to \{0,1\}\}$ be the set of all binary functions on $B$.

What is the maximal size of an independent collection of functions from $\mathcal{F}$? I.e., what is the largest $N$ such that there exist $f_i\in\mathcal{F}$ with $$ \mathbb{P}(f_i=\epsilon_i, i\in I)=\prod_{i\in I}\mathbb{P}(f_i=\epsilon_i) $$ for all choices $\epsilon_i\in\{0,1\}$ and subsets $I\subseteq\{1,\ldots, N\}$?

I guess this is equivalent to asking for the maximal number of independent subsets of $B$, i.e. what is the largest number $N$ such that there exist $A_i\subseteq B$ with $$ \mathbb{P}\left(\bigcap_{i\in I}A_i\right)=\prod_{i\in I}\mathbb{P}(A_i), $$ for all $I\subseteq\{1,\ldots, N\}$, where $\mathbb{P}(A)=|A|/2^n$?

I don't see any way to count these off the top of my head, although there are maybe some obvious sets of independent functions (e.g. the coordinate functionals). Perhaps this is the best one can do, the intuition being "$n$ independent bits $\Leftrightarrow$ $n$ independent subsets"? (Disregarding the "trivial" events $\emptyset$, $B$, corresponding to constant functions.)

---

The paper Independent Events in a Discrete Uniform Probability Space considers the problem more generally, with the uniform distribution on finite sets.

Theorem 5 there backs up the "intuitive" answer $N=n$ to my question (ignoring constant functions/(co)null sets).

Answer 1

Here's a proof that if the sample space $B$ has size $p^n$ where $p$ is prime, then we can have at most $n$ non-trivial independent events. (The simpler answer suggested by d.k.o. gives the same result for $p=2$.)

Suppose $A_1,...,A_N$ are independent and none of them is empty or equal to $B$.

Note that $\nu_p(|A_i|)\le n-1$ for each $i$ (where $\nu_p$ is the $p$-adic order); otherwise we'd have either $|A_i|=0$ or $|A_i|\ge p^n=|B|$.

Independence says that $\frac{|\bigcap_{i=1}^N A_i|}{|B|}=\prod_{i=1}^N{\frac{|A_i|}{|B|}}$. Multiplying through by $|B|^N$, we see that $\prod_{i=1}^N{|A_i|}$ is divisible by $|B|^{N-1}=p^{n(N-1)}$.

Therefore, $n(N-1)\le\nu_p(\prod_{i=1}^N |A_i|)=\sum_{i=1}^N\nu_p(|A_i|)\le N(n-1)$, so $\frac{N-1}N\le\frac{n-1}n$, so $N\le n$.

Answer 2

Since $|\Omega|=|\{0,1\}^n|=2^n$, there can be at most $n$ non-trivial independent events in $2^{\Omega}$. Thus, excluding the constant functions $f\equiv 1$ and $f\equiv 0$, there can be at most $n$ mutually independent random variables taking values in $\{0,1\}$.

Answer 3

Here is a constructive converse of the accepted answer for completeness ($P=\{0,1,\ldots,p-1\}^n$, $p$ prime). As suggested in the question, the $n$ cylinder sets $P_i=\{x=(x_1,\ldots,x_n)\in P : x_i=0\}$ are mutually independent. For $I\subseteq\{1,\ldots, n\}$ we have $$ \frac{1}{p^n}\left|\bigcap_{i\in I}P_i\right|=\frac{1}{p^n}|\{x\in P : x_i=0 \ \forall i\in I\}|=\frac{1}{p^n}p^{n-|I|}=\frac{1}{p^{|I|}}=\prod_{i\in I}\frac{p^{n-1}}{p^n}=\prod_{i\in I}\frac{|P_i|}{|p^n|}. $$ (Of course, $p$ doesn't have to be prime for this to give independent sets, but it is a maximal family when $p$ is prime.)