Counterexample (valid for every n ≥ 4)
Fix n ≥ 4 and define a probability space with n+1 atoms ω0, ω1, …, ωn having probabilities
- P(ω0) = s := 1/(n−1)^2,
- P(ωi) = r := (n−2)/(n−1)^2 for i = 1, 2, …, n.
Note that s + n r = 1.
Define Bernoulli variables X1, …, Xn by
- Xi(ω0) = 1 for every i,
- Xi(ωi) = 1 and Xj(ωi) = 0 for j ≠ i.
Equivalently, the random vector X = (X1,…,Xn) takes the value 1^n with probability s and the value ei (the i-th standard basis vector) with probability r for i=1,…,n.
Properties
-
Non-constant: For each i,
P(Xi = 1) = s + r = 1/(n−1) ∈ (0,1).
-
Pairwise independence: For i ≠ j,
- P(Xi = 1, Xj = 1) = s = 1/(n−1)^2 = P(Xi = 1) P(Xj = 1).
- P(Xi = 1, Xj = 0) = r = (n−2)/(n−1)^2 = P(Xi = 1) P(Xj = 0).
- P(Xi = 0, Xj = 0) = (n−2)r = (n−2)^2/(n−1)^2 = P(Xi = 0) P(Xj = 0).
Thus every pair (Xi, Xj) is independent.
- No complete subset of size ≥ 3: Consider any subset of d coordinates. The only configurations that occur with positive probability are:
- the all-ones vector 1^d (coming from ω0),
- the all-zeros vector 0^d (coming from any ωk with k outside the chosen d indices),
- and the d one-hot vectors (coming from ωi with i among the chosen indices).
Hence at most d+2 configurations occur. For d ≥ 3 we have d+2 < 2^d, so no subset of size ≥ 3 is complete.
Conclusion
For n ≥ 4 we have t = ⌊log2 n⌋ ≥ 2 and hence t+1 ≥ 3, but the construction above has no complete subset of size 3 (let alone t+1). Therefore the proposed statement is false for all n ≥ 4.
Remarks
- For n = 3 the assertion in the question is trivial: t = 1 so t+1 = 2, and any pair of pairwise independent non-constant Bernoulli variables is automatically “complete” (all four outcomes have positive probability).
- The construction above is a standard extremal example of n pairwise independent Bernoulli variables supported on only n+1 outcomes. In particular, since a complete subset of size d requires support size at least 2^d, this immediately precludes completeness for any d with 2^d > n+1.
