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