4
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$
    – Quimey
    Sep 27 at 6:56
  • $\begingroup$ @Quimey That setting doesn't satisfy the requirement about the marginal distributions. $\endgroup$
    – Clement C.
    Sep 27 at 8:17
  • 1
    $\begingroup$ ... except in the limit case $\alpha=\beta=0$. $\endgroup$ Sep 27 at 8:52
6
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ 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]$. $\endgroup$ Sep 27 at 7:50
  • 1
    $\begingroup$ 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 ;-) $\endgroup$ Sep 27 at 8:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.