3.3.6 problem 44

(a)

$P\left(X\oplus Y\right)\sim$ Bern$\left(\frac{p}{2}\right)$

(b)

If $p\ne \frac{1}{2}$, $X\oplus Y$ and $Y$ are not independent. Imagine that $X=0$ is extremely unlikely. Then, knowing that $Y=0$ makes it very likely that $X\oplus Y=1$. If $p=\frac{1}{2}$, then $X\oplus Y$ and $Y$ are independent.

$X\oplus Y$ and $X$ are independent, since knowledge of $X$ still keeps the probability of $Y=1$ at $\frac{1}{2}$

(c)

Let the largest element in $J$ be $m$.

$$\begin{array}{cccccccc}P(Y_J=1)& =P(X_m=1)P(Y_{J\setminus \left\{m\right\}}=0)+P(X_m=0)P(Y_{J\setminus \left\{m\right\}}=1)& & & & & & \\ & =\frac{1}{2}\left(P\right(Y_{J\setminus \left\{m\right\}}=0)+P(Y_{J\setminus \left\{m\right\}}=1\left)\right)& & & & & & \\ & =\frac{1}{2}& & & & & & \end{array}$$

Thus, $Y_J\sim \mathrm{Bern}\left(\frac{1}{2}\right)$

To prove pairwise independence: Let $J$, $J^{\text{'}}$ be two arbitrary subsets of $\{1...n\}$. We want to show that $P(Y_J=a\wedge Y_{J^{\text{'}}}=b)=P(Y_J=a)P(Y_J=b)=1/4$ for $a,b\in \{0,1\}$, with the second equality coming from our knowledge that $Y_J\sim \mathrm{Bern}(1∕2)$ for all $J$.

First, let us note that for all $J,J^{\text{'}}$ that are disjoint, $Y_J,Y_{J^{\text{'}}}$ are independent - this follows from the independence of the $X_i$.

Now, suppose $J,J^{\text{'}}$ are not disjoint. Let $A=J\cap J^{\text{'}}$, let $B=J\setminus A$, and let $C=J^{\text{'}}\setminus B$. By definition, $A,B,C$ are disjoint.

Now, we have

$$P(Y_J=a\wedge Y_{J^{\text{'}}}=b)=P(Y_J=a,Y_{J^{\text{'}}}=b|Y_A=1\left)P\right(Y_A=1)+P(Y_J=a,Y_{J^{\text{'}}}=b|Y_A=0)P(Y_A=0)$$

using the LOTP. Continuing, we have

$$=P(Y_B=1-a,Y_C=1-b|Y_A=1\left)P\right(Y_A=1)+P(Y_B=a,Y_C=b|Y_A=0)P(Y_A=1)$$

by noting that if $x\oplus 1=y$, we must have $y=1-x$ and if $x\oplus 1=y$, we have $y=x$. Continuing, we get

$$=P(Y_B=1-a)P(Y_C=1-b)P(Y_A=1)+P(Y_B=a)P(Y_C=b)P(Y_A=0)$$

We can remove the conditioning since $A,B,C$ are disjoint, and therefore $Y_B,Y_C,Y_A$ are all independent r.v.s. Finally, we realize that since all $Y$ are $\mathrm{Bern}(1∕2)$, this results in

$$={(1∕2)}^3+{(1∕2)}^3=1/4=P(Y_J=a)P(Y_{J^{\text{'}}}=b)$$

as desired - $Y_J,Y_{J^{\text{'}}}$ are independent for any pair $J,J^{\text{'}}$.

To prove that the $Y_J$ are not all independent, consider the subsets $S=\left\{1\right\},S^{\text{'}}=\left\{2\right\},S^{\mathrm{\text{'}\text{'}}}\{1,2\}$. It is clear that if $Y_S=1$ and $Y_{S^{\text{'}}}=1$, then $Y_{S^{\mathrm{\text{'}\text{'}}}}=Y_S\oplus Y_{S^{\text{'}}}=0$. However, this implies that

$$P(\bigcap _{J\subseteq \{1..n\}}{Y}_J=1)=0$$

i.e. it is impossible for all $Y$ to simultaneously equal 1. However, we know that

$$\prod _{J\subseteq \{1..n\}}P(Y_J=1)={(1∕2)}^{2n-1}\ne 0$$

Thus, the $Y_J$ are not independent.