# Extracting an (almost) independent large subset from a pairwise independent set of Bernoulli variables

Let $n>1$, and let $X_1,X_2, \ldots ,X_n$ be non-constant random variables with values in $\lbrace 0,1 \rbrace$. Let us say that a subset of variables $X_{i_1},X_{i_2}, \ldots,X_{i_d}$ is complete if the vector $\overrightarrow{X}=(X_{i_1},\ldots,X_{i_d})$ satisfies $P(\overrightarrow{X}=\overrightarrow{c})>0$ for any $\overrightarrow{c}\in \lbrace 0,1 \rbrace^d$.

Prove or find a counterexample : if $X_1,X_2, \ldots ,X_n$ are pairwise independent Bernoulli variables, then we may extract a complete subset of cardinality at least $t+1$, where $t$ is the largest integer satisfying $2^{t} \leq n$.

This is true for $n=3$ (and hence also true for $n$ between $3$ and $7$), as is shown in the main answer to that MathOverflow question. (That other MathOverflow question is also related, and provides several links)

If true, this result is sharp, as can be seen by the classical example of taking all arbitrary sums modulo 2 of an initial set of fully independent $t+1$ Bernoulli variables. This produces a set of pairwise independent $2^{t+1}-1$ variables, and where the maximal cardinality of a complete subset is $t+1$.

Update 10/10/2012 : By induction, it would suffice to show the following : if $X_1, \ldots ,X_t$ is a fully independent set of $t$ Bernoulli variables and $X$ is another Bernoulli variable, such that the pair $(X_i,X)$ is independent for each $i$, then there are coefficients $\varepsilon_0,\varepsilon_1, \ldots ,\varepsilon_t$ in $\lbrace 0,1 \rbrace$ such that, if we put

$$H=\Bigg\lbrace (x_1,\ldots,x_t,x) \in \lbrace 0,1 \rbrace ^{t+1} \Bigg| x=\varepsilon_0+\sum_{k=1}^{t}\varepsilon_kx_k \ {\sf mod} \ 2\Bigg\rbrace, \ \overrightarrow{X}=(X_{1},\ldots,X_{t},X)$$ then $P(\overrightarrow{X}=h)>0$ for any $h\in H$.

-