Let's say I have a finite set of binary random variables. Does there exist, for any such set, another finite set of binary random variables that carries approximately the same information, but whose members are all statistically independent of each other? By "carry approximately the same information", I mean that any sample of the dependent set could be approximately determined given the corresponding sample of the independent set.

In other words: It's my understanding that when we have statistical dependencies, it means we have redundant information. For any given set of binary variables, does there exist another set which carries the same information but with all the redundancies eliminated?

If so, is it possible to find such sets? Are there any known techniques for doing so?

  • $\begingroup$ Don't miss the sequel! $\endgroup$ Aug 21, 2016 at 4:17
  • $\begingroup$ I think @Xi'an's answer from the sequel should be here, too. It shows such that the desired set of binary random variables can be constructed. I don't think it this question (especially on a statistics site) should be formalized as "can the desired set of random variables be constructed in any probability space where the original random variables ca be constructed, without extending the probability space". $\endgroup$ Aug 21, 2016 at 7:25

1 Answer 1


De Finetti's representation theorem, which is important in mathematical statistics, shows that something like this is true for exchangeable random variables. It says that for any sequence of exchangeable random variables, there exists another random variable conditional on which the former are IID.

But now I'll attack your problem more directly. Let's formalize it like this:

Conjecture: Let $(Ω, Σ, μ)$ be a probability space. If $X_1, X_2, …, X_n$ are Bernoulli random variables on $Ω$, then there exist independent Bernoulli random variables $Y_1, Y_2, …, Y_m$ on $Ω$ and a function $f : \{0, 1\}^m → \{0, 1\}^n$ such that for all $ω ∈ Ω$, $f(Y_1(ω), …, Y_m(ω)) = (X_1(ω), …, X_n(ω))$.

This statement is false. For a counterexample, consider the case when:

  • $n = 2$
  • $Ω = \{1, 2, 3\}$
  • $μ(1) = \tfrac{1}{2}$, $μ(2) = μ(3) = \tfrac{1}{4}$
  • $X_1(1) = 0$, $X_1(2) = X_1(3) = 1$
  • $X_2(1) = 0$, $X_2(2) = 0$, $X_1(3) = 1$

Notice that $X_1$ and $X_2$ are dependent, since

$$P(X_1 = 0, X_2 = 0) = \tfrac{1}{4} ≠ \tfrac{3}{8} = \tfrac{1}{2} \cdot \tfrac{3}{4} = P(X_1 = 0)P(X_2 = 0).$$

Obviously, $m$ will need to be greater than 1. However, on this probability space, there is no pair of independent Bernoulli random variables. There are only 8 distinct Bernoulli random variables (because $2^{|Ω|} = 2^3 = 8$), and all $\binom{8}{2} = 28$ pairs of these are dependent. The following Python program proves this by checking every pair.

import numpy as np
from itertools import combinations

probs = np.array([2, 1, 1])  # Multiplied by 4 so we can do integer arithmetic.

ys = [np.array([a, b, c])
    for a in (False, True) for b in (False, True) for c in (False, True)]

for y1, y2 in combinations(ys, 2):
    def f(a, b):
        v1 = y1 if a else ~y1
        v2 = y2 if b else ~y2
        return np.sum(probs[v1 & v2]) == np.sum(probs[v1]) * np.sum(probs[v2])
    if f(0, 0) and f(0, 1) and f(1, 0) and f(1, 1):
        print "Independent"
        print "Dependent"
  • $\begingroup$ thanks for your response, but I think for my purposes the constraint that the random variables be exchangeable is too much $\endgroup$
    – user124644
    Jul 27, 2016 at 8:15
  • $\begingroup$ @delta See my additions above. $\endgroup$ Jul 27, 2016 at 15:34
  • 1
    $\begingroup$ The counterexample here is in my opinion rather misleading as there was no reason to assume the intention was that the probability space is fixed. See remarks about "probabilistic way of thinking" and "extend the sample space as necessary" terrytao.wordpress.com/2010/01/01/… . In a statistics site this "way of thinking" is imo even more desirable than in math. $\endgroup$ Aug 21, 2016 at 7:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.