HW2 (Due 10/4)

Continue with Question 2 in HW1

1. What is $I(D_1;D_2)$?

2. What is $I(D_1;S)$?

3. What is $I(D_1;D_2|S)$?

4. What is $I(D_1;D_2|S=3)$?

Let $X_1$ and $X_2$ be two discrete random variables whose outcomes do not overlap. And let $X=X_1$ with prob $p$ and $X=X_2$ with prob $(1-p)$. Show that $H(X) = p H(X_1) + (1-p) H(X_2) + H(p)$

A group of 1,000 students have the average height of 170 cm and the standard deviation of 15 cm. Approximatley how many bits are needed to store all the height data with the precision of 0.1 cm assuming the height is normally distributed?

(Typical sequences of coin-flips) Consider sequences of $N$ coin-flips with the probability of head equal to $p$. Denote $n_H({\bf x})$ as the number of heads in a sequence $\bf x$. Assume $p < 0.5$. Show that a sequence $\bf x$ is $\epsilon$-typical $\left({\bf x} \in A_{\epsilon}^N(X)\right)$ if and only if $p- \frac{\epsilon}{\log\frac{1-p}{p}} \le \frac{n_H({\bf x})}{N} \le p+ \frac{\epsilon}{\log\frac{1-p}{p}}$

1. Let $p=0.2$, $\epsilon=0.01$, and $N=100$, compute $Pr({\bf X}^N \in A_\epsilon^{N}(X))$

2. Repeat (a) with $N$ change to $10,000$.

3. Repeat (a) and (b) with $p$ change to $0.45$.