We are given two bits A and B. Define P(!X) as the probability that bit X is 0, and P(X) as the probability that bit X is 1. Define C = A xor B.
We are told the following:
- $ P(A) = P(B) = p $
where A and B are independent bits. We can conclude from this that, since each bit must be either 0 or 1,
- $ P(!A) = P(!B) = 1 - p $
We want to see if knowing something about A will tell us something about C, i.e., if A and C are dependent (if it will) or independent (if it won't). Consider the definition for independence:
- A and C are independent iff $ P(A) \cap P(B) = P(A)P(B) $
So, to test for independence, we can evaluate the following:
- $ P(A) = p $
- $ P(C) = P(!A)P(B) + P(A)P(!B) = 2(1-p)(p) = 2p - 2p^2 $ (since C = A xor B, C=1 if A=0 and B=1 or if A=1 and B=0.)
- $ P(A \cap C) = P(A \cap !B) = p(1-p) = p-p^2 $ (Since A=1 and C=1 only in the case that B=0)
- $ P(A)P(C)= (p)(2p - 2p^2) = 2p^2 - 2p^3 $
When, then, does $ P(A) \cap P(B) = P(A)P(B) $? (ie, When are A and C independent?)
- $ p-p^2 = 2p^2 - 2p^3 \Rightarrow 2p^3 - 3p^2 + p = 0 \Rightarrow p(p-1)(2p-1) = 0 $
- $ \Rightarrow p = 0, \frac{1}{2}, 1 $
So, in general, A and C = A xor B are not independent, except in the 3 cases which were found above.
Answer: In general, no.
