ENEE 627 HW 2. Date due Tuesday March 3 in class
1. Textbook problems 2.10, 2.18, 2.26, 2.29, 2.30, 3.3, 3.4
2. Let $\rho(X,Y)$ be the function defined in problem 2.9(a) of the textbook. Prove that for any $\epsilon>0$ there exists $\delta>0$ such that $P(X\not= Y) <= \delta$ impies that $\rho(X,Y)<= \epsilon$. (please give an explicit expression for $\delta$ as a function of $\epsilon$). Use the Fano inequality.
3. Let $p,q$ be pmf's defined on a finite set $\mathcal X$. Define $d(p,q)=\sum_{x\in \mathcal X} |p(x)-q(x)|$ to be the $\ell_1$-distance between the distributions.  Prove that
$$D(p||q)\geq\frac1{2 \ln2}d^2(p,q).$$
Moreover, show that for any $\epsilon$ there are $p,q$ such that $\Big|\frac{D(p||q)}{d^2(p,q)}-\frac1{2 \ln2}\Big|<\epsilon.$
(Hint: Reduce the question to the case ${\mathcal X}=\{0,1\}.$ For this, consider the set $M=\{x: p(x)\ge q(x)\}$. Then consider Bernoulli pmf's $\tilde p=(p(M), 1-p(M)), \tilde q=(q(M),1-q(M))$ and notice that $D(p\|q)\geq D(\tilde p\|\tilde q)$ while $d(p,q)=d(\tilde p, \tilde q).$
For the Bernoulli case the problem is to find the largest $c$ such that
$$p\log\frac p q+(1-p)\log\frac{1-p}{1-q}-4c(p-q)^2\ge 0$$
for all $0\le q\le p\le 1$. This is solved by computing derivatives.).