How Conditioning Creates Dependence

We want to disprove:

$X \perp Y ;;\nRightarrow;; X \perp Y \mid Z$

So we construct:

$X \perp Y \quad \text{but} \quad X \not!\perp Y \mid Z$

🪙 Step 1: Define Independent Variables

Let and be fair coins:

$P(X = 0) = P(X = 1) = \frac{1}{2}$ $P(Y = 0) = P(Y = 1) = \frac{1}{2}$

Independence:

$P(X = x, Y = y) = P(X = x)\cdot P(Y = y)$

Example:

$P(X = 0, Y = 0) = \frac{1}{2} \times \frac{1}{2} = \frac{1}{4}$

⚙️ Step 2: Define

$Z = X \oplus Y$

Meaning:

$Z = 0 \text{ if } X = Y, \quad Z = 1 \text{ if } X \ne Y$

📊 Step 3: Possible Outcomes

latex = (0,0,0), (0,1,1), (1,0,1), (1,1,0)[/latex]

Each has probability:

$P(X=x, Y=y) = \frac{1}{4}$

🔍 Step 4: Condition on

$Z = 0 \Rightarrow (X,Y) = (0,0), (1,1)$ $P(Z = 0) = \frac{1}{4} + \frac{1}{4} = \frac{1}{2}$

📌 Step 5: Conditional Joint Probability

$P(X = 0, Y = 0 \mid Z = 0) = \frac{P(X=0, Y=0)}{P(Z=0)}$ $= \frac{\frac{1}{4}}{\frac{1}{2}} = \frac{1}{2}$

📌 Step 6: Conditional Marginals

$P(X = 0 \mid Z = 0) = \frac{1}{2}$ $P(Y = 0 \mid Z = 0) = \frac{1}{2}$

⚠️ Step 7: Check Conditional Independence

$P(X=0, Y=0 \mid Z=0) \stackrel{?}{=} P(X=0 \mid Z=0)\cdot P(Y=0 \mid Z=0)$

Right-hand side:

$\frac{1}{2} \times \frac{1}{2} = \frac{1}{4}$

Left-hand side:

$\frac{1}{2}$

❌ Final Result

$\frac{1}{2} \ne \frac{1}{4}$ $P(X,Y \mid Z) \ne P(X \mid Z)\cdot P(Y \mid Z)$

🚨 Conclusion

$X \not!\perp Y \mid Z$

Even though:

$X \perp Y$

🧠 Key Insight

$Z = 0 \Rightarrow X = Y$ $\text{Knowing } X \Rightarrow \text{Knowing } Y$

👉 Conditioning created dependence.