161-A3.2

The submission bin for this exercise can be found here.

The items below are arranged from easiest to hardest. When writing proofs, take care not to rely on figures and work with the available definitions and properties to produce a logical sequence of statements. To get full credit, justify all steps concisely. Note that although it is possible to write correct, lengthy proofs, the exercises below are guaranteed to have concise solutions so that they all fit in one A4-sized sheet of paper.

I strongly encourage everyone to make partial submissions per item, preferably starting from Item 1, so that you can confirm if you are on the right track, or if there are significant faults/fallacies in your work.

Exercises (10 points)

1. (3 points) Let $X,Y$ be independent and uniformly distributed random variables over the common alphabet $\{0,1\}$, and define a third random variable $Z$ as $Z=X\oplus Y$, where $\oplus$ is the XOR operation. Show that the three random variables are pairwise independent, but not mutually independent.
2. (3 points) Show that if $X$ is not a deterministic random variable, then $H(X)$ is strictly positive. Hint: What can we say about the probabilities if a random variable is non-deterministic?
3. (2 points) Show that if $X\perp Z$, then $I(X;Y|Z)=I(X;Y,Z)$. Hint: Use Bayes' theorem.
4. (2 points) For $n>3$, show that if $X_{1}\rightarrow X_{2}\rightarrow \cdots \rightarrow X_{n}$ forms a Markov chain, then $(X_{1},X_{2})\rightarrow (X_{2},X_{3})\rightarrow \cdots \rightarrow (X_{n-1},X_{n})$ also forms a Markov chain.