Eliminating statistical dependency from a set of random variables 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?
 A: 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"
    else:
        print "Dependent"

