Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$.

share|improve this question
add comment

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.