6.441 Information Theory, Lecture 2 Notes

LECTURE 2 Convexity and related notions Last time: • Goals and mechanics of the class • notation • entropy: definitions and properties • mutual information: definitions and prop­ erties Lecture outline • Convexity and concavity • Jensen’s inequality • Positivity of mutual information • Data processing theorem • Fano’s inequality Reading: Scts. 2.6-2.8, 2.11. Convexity Definition: a function f (x) is convex over (a, b) iff ∀x1, x2 ∈ (a, b) and 0 ≤ λ ≤ 1 f (λx1 + (1 − λ)x2) ≤ λf (x1) + (1 − λ)f (x2) and is strictly convex iff equality holds iff λ = 0 or λ = 1. f is concave iff −f is convex. Convenient test: if f has a second deriva­ tive that is non-negative (positive) every­ where , then f is convex (strictly convex) Jensen’s inequality if f is a convex function and X is a r.v., then EX [f (X)] ≥ f (EX [X]) if f is strictly convex, then EX [f (X)] = f (EX [X]) ⇒ X = E[X]. Concavity of entropy Let f (x) = −x log(x) then 1 f �(x) = −x log(e) − log(x) x = − log(x) − log(e) and 1 f ”(x) = − log(e) < 0 x for x > 0. H(X) = � x∈|X | f (PX (x)) thus the entropy of X is concave in the value of PX (x) for every x. Thus, consider two random variables, X1 and X2 with common X . Then the ran­ dom variable X defined over the same X such that PX (x) = λPX1 (x) + (1 − λ)PX2 (x) satisfies: H(X) ≥ λH(X1) + (1 − λ)H(X2). Maximum entropy Consider any random variable X11 on X . For simplicity, consider X = {1, . . . , |X |} (we just want to use the elements of X as in­ dices). Now consider X21 a random vari­ able such PX 1 (x) = PX 1 (shif t(x)) where 2 1 shif t denotes the cyclic shift on (1, . . . , X ). Clearly H(X11) = H(X21). Moreover, con­ sider X12 defined over the same X such that PX 2 (x) = λPX 1 (x) + (1 − λ)PX 1 (x) then 1 H(X12) 1 ≥ H(X11). 2 We can show recursively with the obvious extension of notation that H(X1n) ≥ H(X1m) 1 ∀n > m ≥ 1. Now limn→∞PX n (x) = |X | 1 ∀x ∈ X . Hence, the uniform distribution maximizes entropy and H(X) ≤ log(|X |). Conditioning reduces entropy H(Y |X) = EZ [H(Y |X = Z)] = − � PX (x) x∈X � PY |X (y|x)log2[PY |X (y|x)] y∈Y � PY (y) = x∈X PX (x)PY |X (y|x) hence by con­ cavity H(Y |X) ≤ H(Y ). Hence I(X; Y ) = H(Y ) − H(Y |X) ≥ 0. Independence bound: H(X1, . . . , Xn) = ≤ n � i=1 n � H(Xi|X1, . . . , Xi−1) H(Xi) i=1 Question: H(Y |X = x) ≤ H(Y )? Mutual information and transition probability Let us call PY |X (y |x) the transition proba­ bility from X to Y . Consider a r.v. Z that takes values 0 and 1 with probability θ and 1 − θ and s.t. PY |X,Z (y|x, 0) = PY� |X (y|x) PY |X,Z (y|x, 1) = PY�� |X (y|x) and Z is independent from X I(X; (Y, Z)) = I(X; Z) + I(X; Y |Z) and I(X; (Y, Z)) = I(X; Y ) + I(X; Z |Y ) hence I(X; Y |Z) ≥ I(X; Y ) so θI(X; Y |Z = 0)+(1−θ)I(X; Y |Z = 1) ≥ I(X; Y ) For a fixed input assignment, I(X; Y ) is convex in the transition probabilities Mutual information and input probability Consider a r.v. Z such that PX |Z (x|0) = P �(x), PX |Z (x|1) = P ��(x), Z takes values 0 and 1 with probability θ and 1 − θ and Z and Y are conditionally independent, given X I(Y ; Z |X) = 0 and I(Y ; (Z, X)) = I(Y ; Z) + I(Y ; X |Z) = I(Y ; X) + I(Y ; Z |X) so I(X; Y |Z) ≤ I(X; Y ). Mutual information is a concave function of the input probabilities. Exercise: jamming game in which we try to maximize mutual information and jam­ mer attempts to reduce it. What will the policies be? Markov chain Markov chain: random variables X, Y, Z form a Markov chain in that order X → Y → Z if the joint PMF can be written as PX,Y,Z (x, y, z) = PX (x)PY |X (y |x)PZ |Y (z |y). Markov chain Consequences: • X → Y → Z iff X and Z are conditionally independent given Y PX,Z |Y (x, z|y) = = PX,Y,Z (x, y, z) PY (y) PX,Y (x, y) PZ |Y (z |y) PY (y) = PX |Y (x|y)PZ |Y (z |y) so Markov implies conditional indepen­ dence and vice versa • X → Y → Z ⇔ Z → Y → X (see above LHS and last RHS) Data Processing Theorem If X → Y → Z then I(X; Y ) ≥ I(X; Z) I(X; Y, Z) = I(X; Z) + I(X; Y |Z) I(X; Y, Z) = I(X; Y ) + I(X; Z |Y ) X and Z are conditionally independent given Y , so I(X; Z |Y ) = 0 hence I(X; Z) + I(X; Y |Z) = I(X; Y ) so I(X; Y ) ≥ I(X; Z) with equality iff I(X; Y |Z) = 0 note: X → Z → Y ⇔ I(X; Y |Z) = 0 Y depends on X only through Z Consequence: you cannot ”undo” degra­ dation Consequence: Second Law of Thermodynamics The conditional entropy H(Xn|X0) is non­ decreasing as n increases for a stationary Markov process X0, . . . , Xn Look at the Markov chain X0 → Xn−1 → Xn DPT says I(X0; Xn−1) ≥ I(X0; Xn) H(Xn−1)−H(Xn−1|X0) ≥ H(Xn)−H(Xn|X0) so H(Xn−1|X0) ≤ H(Xn|X0) Note: we still have that H(Xn|X0) ≤ H(Xn). Fano’s lemma Suppose we have r.v.s X and Y , Fano’s lemma bounds the error we expect when estimating X from Y �= We generate an estimator of X that is X g(Y ). �= Probability of error Pe = P r(X � X) Indicator function for error E which is 1 � and 0 otherwise. Thus, P = when X = X e P (E = 0) Fano’s lemma: H(E) + Pe log(|X | − 1) ≥ H(X|Y ) Proof of Fano’s lemma H(E, X |Y ) = H(X |Y ) + H(E|X, Y ) = H(X |Y ) H(E, X |Y ) = H(E|Y ) + H(X |E, Y ) H(E|Y ) ≤ H(E) H(X |E, Y ) = PeH(X|E = O, Y ) + (1 − Pe)H(X|E = 1, Y ) = PeH(X |E = O, Y ) ≤ PeH(X|E = O) ≤ Pe log(|X | − 1)