Xor of two binary random variables

Question

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.

Answer 1

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$.

Answer 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.