Probability proof of a function with independent uniformly distributed variables

Question

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$

where

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

Answer 1

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").

Answer 2

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

Alternatively:

$\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\}$