Splitting One Uniform Into Two Independent Uniforms

Worked Solution

How to Think About It: Your first instinct is probably "no way -- one source of randomness can't produce two independent copies." That intuition is wrong, and understanding why is the whole point of this problem. The key insight: $U$ is not "one coin flip" of randomness. Its binary expansion $U = 0.b_1 b_2 b_3 \ldots$ gives you an *infinite* sequence of i.i.d. fair coin flips. An infinite i.i.d. sequence can be partitioned into two infinite i.i.d. subsequences. That is the construction.

The common wrong "proof" of impossibility goes: $(f(U), g(U))$ is a deterministic function of $U$, so it traces a curve in the unit square, curves have 2D Lebesgue measure zero, so the joint can't be uniform on $[0,1]^2$. The flaw: this argument assumes the map is continuous (or at least sufficiently regular). The bit-interleaving map is wildly discontinuous -- it is a measurable bijection (a.e.) from $[0,1]$ to $[0,1]^2$ that pushes $\lambda_1$ to $\lambda_2$. No contradiction.

Answer: Yes, it is possible.

Construction (Bit-Interleaving):

For almost every $u \in [0,1]$, write $u$ in its unique binary expansion (excluding the countable, measure-zero set of dyadic rationals):

$$u = 0.b_1 b_2 b_3 b_4 b_5 b_6 \ldots \quad (\text{base 2})$$

Define:

$$f(u) = 0.b_1 b_3 b_5 b_7 \ldots \quad \text{(odd-indexed bits)}$$

$$g(u) = 0.b_2 b_4 b_6 b_8 \ldots \quad \text{(even-indexed bits)}$$

Equivalently, $f(u) = \sum_{k=1}^{\infty} b_{2k-1} \cdot 2^{-k}$ and $g(u) = \sum_{k=1}^{\infty} b_{2k} \cdot 2^{-k}$.

Proof of correctness:

*Step 1 -- Marginals are uniform.* Since $U \sim \text{Unif}(0,1)$, the binary digits $b_1, b_2, b_3, \ldots$ are i.i.d. $\text{Bernoulli}(1/2)$. The subsequence $(b_1, b_3, b_5, \ldots)$ is also i.i.d. $\text{Bernoulli}(1/2)$, so $f(U) = \sum_{k=1}^{\infty} b_{2k-1} \cdot 2^{-k}$ has the distribution of a uniform on $[0,1]$ (a random variable whose binary digits are i.i.d. fair coins is uniform). By the same argument, $g(U) \sim \text{Unif}(0,1)$.

*Step 2 -- Independence.* The odd-indexed bits $(b_1, b_3, b_5, \ldots)$ and the even-indexed bits $(b_2, b_4, b_6, \ldots)$ are disjoint sub-collections of an i.i.d. sequence, hence independent. Since $f(U)$ is $\sigma(b_1, b_3, b_5, \ldots)$-measurable and $g(U)$ is $\sigma(b_2, b_4, b_6, \ldots)$-measurable, the two random variables are independent. $\square$

*Step 3 -- The map is a measure-preserving bijection (a.e.).* The map $h : [0,1] \to [0,1]^2$ defined by $h(u) = (f(u), g(u))$ is an injection on the set of non-dyadic rationals (which has full measure). Its inverse "interleaves" the binary digits of two numbers back into one. For any measurable rectangle $[0, a] \times [0, c] \subseteq [0,1]^2$:

$$P(f(U) \leq a,\, g(U) \leq c) = P(f(U) \leq a) \cdot P(g(U) \leq c) = a \cdot c = \lambda_2([0,a] \times [0,c])$$

So $h$ pushes $\lambda_1$ forward to $\lambda_2$. This is why the "curves have measure zero" argument fails: $h$ is not a curve in the topological sense. It is a highly discontinuous, space-filling, measure-preserving map.

Why the dimension argument fails:

The statement "a map from $\mathbb{R}$ to $\mathbb{R}^2$ has image of 2D measure zero" is true for *Lipschitz* maps (by the area formula) and even for continuous maps with bounded variation. But it is false for arbitrary measurable maps. The bit-interleaving map is nowhere continuous -- nearby values of $u$ can map to completely different points in the square (flipping one early bit of $u$ rearranges many bits of $f(u)$ and $g(u)$). Measure-theoretic structure and topological structure are different things, and this problem is all about that distinction.

Bonus: A dependent construction.

The problem asks for a dependent pair if the answer were "no." Since the answer is yes, we provide these for comparison. The simplest dependent construction: $f(U) = U$ and $g(U) = 1 - U$. Both are marginally $\text{Unif}(0,1)$, but they are maximally negatively dependent:

$$\text{Cov}(f(U), g(U)) = \text{Cov}(U, 1-U) = -\text{Var}(U) = -\frac{1}{12}$$

Another interesting construction: $f(U) = U$ and $g(U) = (U + 1/2) \mod 1$. Both marginals are $\text{Unif}(0,1)$ and $\text{Cov}(f(U), g(U)) = 0$, but they are not independent -- knowing $U$ determines $g(U)$ exactly. This shows that zero covariance does not imply independence.

Answer: Yes, it is possible. Write $U$ in binary as $0.b_1 b_2 b_3 \ldots$, set $f(U) = 0.b_1 b_3 b_5 \ldots$ (odd bits) and $g(U) = 0.b_2 b_4 b_6 \ldots$ (even bits). Both are $\text{Unif}(0,1)$ and independent. The construction works because the binary digits of a uniform are i.i.d. $\text{Bernoulli}(1/2)$, and partitioning an i.i.d. sequence into disjoint subsequences preserves independence.