### Pset 3, Abubakar Abid (It may take a second for the LaTeX-javascript library to load...)

4.1) The entropy functional is $$H(p) = -\sum^X_{i=1}{p_i \log{p_i}}$$ And define $$0 \log{0} = 0$$

i) We observe that not only is $$H(p)$$ continuous but it is differentiable. $$\frac{dH}{dp_j} = -\sum^X_{i\neq j} 0 - p_j \frac{1}{p_j} - \log{p_j} = -1 - \log{p_j}$$ ii) Every term in the sum that defines $$H$$ must independently be non-positive, because $$0 \le p_i \le 1$$, so the sum is always non-positve, and $$H$$ therefore is non-negative. If $$p_1 = 1$$, then $$p_i = 0$$ for all other $$i$$ and and we see that $$H$$ evaluates to zero. Likewise, if $$H$$ evaluates to zero, we know, all $$p_i$$ must be equal to 0 or 1, but since the sum of all $$p_1$$ is 1, there can be only one non-zero term.

iii) We prove by contradiction. Suppose the maximal entropy distribution exists and includes non-uniform probabilities $$p_1$$ and $$p_2$$ with $$p_1 < p_2$$ WLOG. We will show that we can get a higher entropy by slightly increasing $$p_1$$ and slightly decreasing $$p_2$$. The entropy of the two original terms is $$-p_1 \log{p_1} - p_2 \log{p_2}$$ The entropy of the modified terms is (using the taylor expansion for $$\log{(p+\epsilon)} \approx \log(p) + \frac{\epsilon}{p}$$: $$-p_1 \log{p_1} - p_2 \log{p_2} - \epsilon - \epsilon \log{p_1} - \frac{\epsilon^2}{p_1} + \epsilon + \epsilon \log{p_1} - \frac{\epsilon^2}{p_1}$$ Ignoring the second order terms, the change in entropy is $$\epsilon \log{p_2} - \epsilon \log{p_1} = \epsilon \log{p_2 / p_1} > 0$$ The last expression is greater than zero because we assumed $$p_2 > p_1$$. Thus, the entropy takes its maximum when the probabilities are equally distributed, and that value turns out to be $$\log{X}$$.

iv) If the drawings are independent, then the chance of seeing $$(x,y)$$ is $$p_x q_y$$, or the product of the probabilities of seeing each of them separately, and the entropy of joint distribution can be written as $$H(p,q) = -\sum_i^X \sum_j^Y {p_i q_j \log(p_i q_j)}$$ $$= -\sum_i^X {p_i \sum_j^Y{ q_j \log(p_i q_j)}}$$ $$= -\sum_i^X {p_i \sum_j^Y{ q_j \log{p_i} + q_j \log{q_j}}}$$ $$= -\sum_i^X {p_i (\log{p_i} + H(q))}$$ $$= {H(p) + H(q)}$$ Where we have used the fact that probabilities sum to 1.

4.2) We know that $$H(x,y) = H(x|y) + H(y) = H(y|x) + H(x)$$, so the second and third equalities follow by substitution. The last equality follows when we write $$H(x) = -\sum_i^X {p_i \log{p_i}} = -\sum_j^Y \sum_i^X {p_{j|i} p_i \log{p_i}} = -\sum_j^Y \sum_i^X {p(i,j) \log{p_i}}$$ Similarly, $$H(y) = -\sum_j^Y \sum_i^X {p(i,j) \log{p_j}}$$ Substituting, we get the last relation.

4.3 a) Either all three can be incorrect, or 2 out of the 3 can be incorrect: $$p_1 = \epsilon^3 + 3 \epsilon^2 (1-\epsilon)$$

4.3 b) From (a), $$p_2 = p_1^3 + 3 p_1^2 (1-p_1)$$

4.3 c) We can recursively define $$p_{N+1} = p_{N}^3 + 3 * p_N^2 (1 - p_N)$$ with the base cases above. The probability of an error is $$p_N$$ while the number of bits required is $$3^N$$. It seems that the dominant term for small error rates is $$\epsilon^{2^N}$$.

4.4) From (4.20), we can easily calculate the differential entropy of a Gaussian process as: $$\ln{\sqrt{2 \pi \sigma^2_N}} + \frac{\sigma_N^2 + \mu_N^2 - 2 \mu_N^2 + \mu^2_N }{2 \sigma_N^2} = \frac{1}{2} + \ln{\sqrt{2 \pi \sigma^2_N}}$$ Where $$\mu_N$$ and $$\sigma_N$$ are the mean and variance of the distribution respectively.

4.5 a) The carrier capacity is: 3300 Hz * log(1+100) = 21.9 kilobits/second.

4.5 b) For the capacity to be 1 Gbit/s, the SNR would have to be about 10000 dB.

4.6) The expected value of $$x_i$$ is $$x_0$$ so the average of $$n$$ measurments is clearly unbiased. The variance of the average is $$\sigma^2/n$$, due to the well-known properties of the Gaussian. Does this meet the lower bound?

From Wolfram Alpha, we can do the integral, where the mean is 7 and variance 11 for computational purposes. It turns out that the Fisher score for one measurement is $$1/\sigma^2$$

So the score for $$n$$ measurements is $$n/\sigma^2$$, and we meet the bound exactly.