 Solution

ID: past-exam-of-the-communication-theory-course-of-the-university-of-oxford/2011/1/c/solution

Write

w_{i} = (A q)_{i}

. For each row put

S_{i} = {j : a_{ij} > 0}

; the positive row entries

α_{i} = (a_{ij})_{j \in S_{i}}

form a probability distribution because the row sum is one. When

w_{i} > 0

r_{i} (j) = \frac{a _{ij} q _{j}}{w _{i}} (j \in S_{i}) .

Part (a), applied on this row support, gives

d (r_{i}, α_{i}) \geq 0

. Its weighted sum expands as

i : w_{i} > 0 \sum w_{i} d (r_{i}, α_{i}) = i, j \sum a_{ij} q_{j} lo g_{2} \frac{q _{j}}{w _{i}} = j \sum q_{j} lo g_{2} q_{j} i \sum a_{ij} - i \sum w_{i} lo g_{2} w_{i} = H (w) - H (q) .

Rows with

w_{i} = 0

contribute zero, since all

a_{ij} q_{j}

in such a row vanish. Using the convention that zero-weight logarithmic terms are zero, the result is

H (W) - H (V) = i : w_{i} > 0 \sum w_{i} d (r_{i}, α_{i}) \geq 0.

Both stochasticity conditions have a role: row sums normalize the comparison distributions, while column sums preserve the total contribution from

q

 New to topics? Read the docs here!