# Xor of two binary random variables

Let $$X,Y\in\{0,1\}$$ be two dependent binary random variables such that $$\Pr[X=0]=\frac{1}{2}+\alpha$$ and $$\Pr[Y=0]=\frac{1}{2}+\beta$$ for $$\alpha,\beta\geq 0$$. My question is how to get a lower bound of $$\Pr[X\oplus Y=0]$$. Here $$X\oplus Y$$ is the xor of two binary variables $$X,Y$$.

In the case that they are independent, $$\Pr[X\oplus Y=0]=(1/2+\alpha)(1/2+\beta)+(1/2-\alpha)(1/2-\beta)=1/2+2\alpha\beta$$.

When they are dependent, I have $$\Pr[X\oplus Y=0]\geq \Pr[X=0,Y=0]\geq 1-(1/2-\alpha)-(1/2-\beta)=\alpha+\beta$$. However, the bound seems weak. I suspect one can get a lower bound greater than $$1/2$$ as in the independent case, but a counterexample would also be appreciated.

• If $Y = 1 - X$ then the xor is always 1, so $P[X\oplus Y=0] = 0$ you won't be able to get any lower bound with a constant. Sep 27 at 6:56
• @Quimey That setting doesn't satisfy the requirement about the marginal distributions. Sep 27 at 8:17
• ... except in the limit case $\alpha=\beta=0$. Sep 27 at 8:52

No, your lower bound is tight. To see this, you should try to construct $$X$$ and $$Y$$ that are "very" dependent, in a way that $$X \ne Y$$ is as probable as you can make it.

To construct such an example, let $$U$$ be uniformly distributed on $$(0,1)$$, and let $$X$$ be $$1$$ in the left end, and $$Y$$ in the right end.

Even more concretely: let $$X = [U < 1/2+\alpha]$$ and $$Y = [U > 1/2-\beta]$$, using the Iverson bracket. You should be able to see that here $$\text{Pr}(X \oplus Y = 0) = \alpha+\beta$$. If $$\alpha$$ and $$\beta$$ are small, this can be much smaller than $$1/2$$.

You can try to put, in your probability mass function, the maximum probability on the combination of $$(X,Y)$$ counted in your xor

If you put the maximal weight on (T,F) or on (F,T), all other probabilities can be determined and you find, in both cases :

$$\begin{array}{lll} X \text{\\} Y & F & T \\ F & \beta+\alpha & \frac{1}{2}-\beta \\ T & \frac{1}{2}-\alpha & 0 \\ \end{array}$$

You have min($$Pr[X \text{ xor } Y]=0)=\alpha+\beta$$

A proof could be built by expressing $$Pr[X \text{ xor } Y=0]$$ as a function of $$P(X=T, Y=F)$$ for instance and shows that the minimum is reached on the limit of the interval.

• But note that the original question is about lower bounding $\Pr[X\oplus Y=0]$. It seems that you are lower bounding $\Pr[X\oplus Y=1]$. Sep 27 at 7:50
• true. Thanks. I was very confused with those probabilities of False instead of True... Now I get the same result as you. I hope my answer is OK ;-) Sep 27 at 8:33