A posterior over 4 states is p = (1/2, 1/4, 1/8, 1/8). An approximation is q = (1/8, 1/8, 1/4, 1/2). Compute Σ q log₂(q/p), the KL divergence of q from p, in bits. Answer as a fraction in lowest terms.

Learn / Library / Statistics

KL in bits

StatisticsMedium

A posterior over $4$ states is $p = (\frac{1}{2}, \frac{1}{4}, \frac{1}{8}, \frac{1}{8})$ . An approximation is $q = (\frac{1}{8}, \frac{1}{8}, \frac{1}{4}, \frac{1}{2})$ . Compute $\sum q log_{2} (\frac{q}{p})$ , the KL divergence of $q$ from $p$ , in bits. Answer as a fraction in lowest terms.

Checking an answer needs JavaScript. The hint and the solution open without it.

Hint

Each ratio $\frac{q}{p}$ is a power of $2$ , so every log is a whole number.

Solution

The ratios $\frac{q}{p}$ are $\frac{1}{4}$ , $\frac{1}{2}$ , $2$ , $4$ , with logs $- 2$ , $- 1$ , $1$ , $2$ .
Weighting by $q$ gives $- \frac{1}{4} - \frac{1}{8} + \frac{1}{4} + 1 = \frac{7}{8}$ .
The divergence is $\frac{7}{8}$ bits, so the answer is $\frac{7}{8}$ .

Answer: $\frac{7}{8}$

Next question Back to the library