I'm currently reading through the introduction section of a research paper which states the following:

Let $Y_0$, $Y_1$, $Y_2$ and $Y_3$ be independent uniformly distributed variables over the field $\mathbb{F_2=\{0,1\}}$. Then,

$P\left[ f(Y_0, Y_1, Y_2, Y_3)=0 \right] = 1/2$


$f(Y_0, Y_1, Y_2, Y_3) := \{\left( Y_0 \lor Y_1 \right)\oplus \left( Y_0 \land Y_3 \right) \}\oplus\{Y_2\land\left[\left(Y_0 \oplus Y_1\right) \lor Y_3\right]\}$

The paper offers only a proof "by inspection". After thinking about it for myself, it doesn't appear obvious to me to why this is true. Here is my thought process:

$P\left[Y_0\lor Y_1 = 0\right]=1/4$

$P\left[Y_0\land Y_3 = 0\right] = 3/4$

$P\left[\{\left( Y_0 \lor Y_1 \right)\oplus \left( Y_0 \land Y_3 \right) \}=0\right]=\frac{1}{4}\cdot\frac{3}{4}+\frac{3}{4}\cdot\frac{1}{4}=\frac{3}{8}$

$P\left[\left(Y_0 \oplus Y_1\right)=0\right]=1/2$

$P\left[\left[\left(Y_0 \oplus Y_1\right) \lor Y_3\right]=0\right]=1/4$

$P\left[\{Y_2\land\left[\left(Y_0 \oplus Y_1\right) \lor Y_3\right]\}=0\right]=1-\frac{1}{2}\cdot\frac{3}{4}=5/8$

$P\left[ f(Y_0, Y_1, Y_2, Y_3)=0 \right]=\frac{3}{8}\cdot\frac{5}{8}+\frac{5}{8}\cdot\frac{3}{8}=30/64=15/32\neq1/2$

Where is the fault in my understanding? What am I missing?


Your third calculation $$P\left[\{\left( Y_0 \lor Y_1 \right)\oplus \left( Y_0 \land Y_3 \right) \}=0\right]=\frac{1}{4}\cdot\frac{3}{4}+\frac{3}{4}\cdot\frac{1}{4}=\frac{3}{8}$$ is incorrect. It is true that $$P(A\oplus B=0)=P(A=0)P(B=0) + P(A=1)P(B=1)$$ when $A$ and $B$ are independent, but here $Y_0\lor Y_1$ is not independent of $Y_0\land Y_3$, since $Y_0$ is involved in both of these. (You have the same problem with your final line.)

I get $$P\left[\{\left( Y_0 \lor Y_1 \right)\oplus \left( Y_0 \land Y_3 \right) \}=0\right]=\frac12$$ by tediously counting the possibilities. This may be the most direct way to work out the final probability (which I find is $1/2$, as claimed): evaluate the truth of the assertion on all 16 possibilities (aka "inspection").


The third line is incorrect. $\def\getsto{\mathop{\leftrightarrow}}\def\P{\mathsf P}$

Well, because $\{A\oplus B=0\}$ is equivalent to $\{A\getsto B=1\}$, therefore this is $(\{A=1\}\cap\{B=1\})\cup(\{A=0\}\cap \{B=0\})$

However, when $A=(Y_0\wedge Y_1)$ and $B=(Y_0\vee Y_3)$, the conjunction is not of independent events.   The truth value of $A,B$ will both be dependent on truth value of $Y_0$ .

So instead the third line will be:

$ \P\{(Y_0\wedge Y_1)\oplus (Y_0\vee Y_3)=0\} ~{= \P\{(Y_0\wedge Y_1)\getsto(Y_0\vee Y_3)=1\}\\ =\P\{(Y_0\wedge Y_1)\vee(\neg Y_0\wedge\neg Y_3)=1\}\\= \tfrac 12 }$


$\P\{(Y_0\wedge Y_1)\oplus (Y_0\vee Y_3)=0\} ~{= 1-\P\{(Y_0\wedge Y_1)\oplus (Y_0\vee Y_3)=1\}\\ = 1-\P\{(Y_0\wedge\neg Y_1)\vee(\neg Y_0\wedge Y_3)=1\}\\= \tfrac 12 }$

Notes: $\getsto$ is the "biconditional" connective; aka "material equivalence". $~(Y_0\wedge Y_1)\getsto (Y_0\vee Y_3)$ is true iff $(Y_0\wedge Y_1)$ and $(Y_0\vee Y_3)$ have the same truth value.$~$ In that event, there are two cases: $Y_0$ is either true or false.$~$

  • In the case where $Y_0$ is true, then $(Y_0\vee Y_3)$ is too (whatever $Y_3$ is), which means $Y_0\wedge Y_1$ is also true, and thus $Y_1$ must be true.

  • In the case where $Y_0$ is false, then $Y_0\wedge Y_1$ is false (whatever $Y_1$ may be), and so $Y_1\vee Y_3$ must be false too, and so $Y_3$ is false.

    • Thus the event $\{(Y_0\wedge Y_1)\getsto (Y_0\vee Y_3)=1\}$ is exactly the event $\{(Y_0\wedge Y_1)\vee(\neg Y_0\wedge\neg Y_3)=1\}$

Apply similar reasoning to $\{f(Y_0,Y_1,Y_2,Y_3)=0\}$

  • $\begingroup$ Just to confirm, are you using $\leftrightarrow$ to refer to the conjunction? Also, going from $$ P\{(Y_0\wedge Y_1)\leftrightarrow(Y_0\vee Y_3)=1\}$$ to $$ P\{(Y_0\wedge Y_1)\vee (\neg Y_0\wedge\neg Y_3)=1\} $$ has me a little confused. Have you simplified the expression? Is your expression related to $$ P \{ \left(Y_0\land Y_1\right)\land\left(Y_0\lor Y_3 \right) \} \lor \{ \neg \left( Y_0\land Y_1 \right) \land \neg \left( Y_0\lor Y_3 \right)\} $$ which would be obtained after using the definition of XOR. $\endgroup$ – Akyidrian Sep 22 '17 at 0:58
  • $\begingroup$ Added notes to clarrify $\endgroup$ – Graham Kemp Sep 22 '17 at 3:04
  • $\begingroup$ Thanks! The clarification certainly helps but it raises one final question. It seem that a divide and conquer approach ultimately does not work in calculating the final result necessary to prove the theorem; i.e. that $$P\left[f(Y_0,Y_1,Y_2,Y_3)=0\right]=1/2$$. This is because both $$\left( Y_0 \lor Y_1 \right)\oplus \left( Y_0 \land Y_3 \right)$$ and $$Y_2\land\left[\left(Y_0 \oplus Y_1\right) \lor Y_3\right]$$ are dependent on each other in a similar way to the worked example you went through; although for this case, all 4 variables are dependent variables and not just $Y_0$! $\endgroup$ – Akyidrian Sep 22 '17 at 4:17
  • $\begingroup$ Am I correct in saying this? I suppose creating a truth table and tabulating the truth values to find the probability would be a more easier approach, especially for really long logical equations where analysis like this would be tedious. $\endgroup$ – Akyidrian Sep 22 '17 at 4:18

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.