Recall that two distributions $X$ and $Y$ that range over some set $S$ are \emph{identical} if for every $s$ in $S$, $\Pr[ X = s] = \Pr[ Y = s ]$. Below $n$ is some integer $n\geq 3$. (You can get partial credit for solving the questions below for the special case that $n=3$ and $z$ (in Question~2) is the string $111$.)
- Let $X_1,...,X_n$ be random variables where $X_i \in \bit$ chosen such that each $X_i$ is chosen to equal $0$ with probability $1/2$ and equal $1$ with probability $1/2$, and all of the $X_i$'s are independent. Let $Y_1,...,Y_n$ be random variables where $Y_i \in \bit$ chosen as follows: first an $n$ bit $0/1$ string $y$ is chosen uniformly at random from the set $\bit^n$ of all possible $n$-bit $0/1$ strings, and then $Y_i$ is set to be the $i^{th}$ coordinate of $y$. Prove that the distributions $(X_1,...,X_n)$ and $(Y_1,...,Y_n)$ are identical.
- Let $z$ be a fixed string in $\bit^n$, and let $Z_1,...,Z_n$ be random variables chosen as follows: first a string $w \in \bits^n$ is chosen uniformly from $\bit^n$, and then $Z_i$ is set to $z_i \oplus w_i$, where $\oplus$ is the XOR operation (i.e., $0\oplus 1 = 1 \oplus 0 = 1$ and $0 \oplus 0 = 1 \oplus 1 = 0$). Prove that the distribution $(Z_1,...,Z_n)$ is identically distributed to $(X_1,...,X_n)$ and $(Y_1,...,Y_n)$ above.
- Let $W_1,...,W_n$ be random variables where $W_i \in \bit$ chosen as follows: first a string $w$ is chosen uniformly at random from the set of all $n$-bit $0/1$ strings satisfying $w_1 \oplus w_2 \oplus \cdots \oplus w_n = 0$, and then $W_i$ is set to be $w_i$. \textbf{(a)} Prove that $W_1$ and $W_2$ are independent. \textbf{(b)} Prove or disprove that the random variables $W_1,...,W_n$ mutually independent.