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.).