Probability bias of the binary AND Say we are given only the following,
$\textsf{Pr}[x' \oplus x = 0]=\frac{1}{2}(1 + \varepsilon_1)$ and $\textsf{Pr}[y' \oplus y = 0]=\frac{1}{2}(1 + \varepsilon_2)$.
Where $x,x',y,y' \in \{0,1\}$.
Can we say anything about $\textsf{ Pr}[x'y' \oplus xy = 0]$ in terms of $\varepsilon_1$ and $\varepsilon_2$? Even a bound would be great.

Here's a table of the contributions of the $16$ possible conjunctive clauses of the $4$ variables (where $0$ represents $\textsf{Pr}[x'y' \oplus xy = 0]$ and $1$ and $2$ the other two probabilities):

All combinations except $1,2$ occur. Thus, we can choose the three probabilities independently except whatever contributes to $1$ and $2$ also contributes to $0$. This yields the bound
\begin{align}
\textsf{Pr}[x'y' \oplus xy = 0]&\ge\textsf{Pr}[x'\oplus x=0\land y'\oplus y=0]\\
&\ge\textsf{Pr}[x'\oplus x=0]+\textsf{Pr}[y'\oplus y=0]-1\\
&=\frac{\epsilon_1+\epsilon_2}2\;.
\end{align}
