Skip to Content
Information Theory

1. Entropy

2020-12-22Original-language archivelegacy assets may be incomplete

Preliminary

  • A mathematical theory of communicationo - Shannon 1948
  • Convexity: f(∑ipixi)≤∑ipif(xi)f(\sum_ip_ix_i)\leq \sum_ip_if(x_i)
    • f(Epxi)≤Epf(xi)f(E_p x_i)\leq E_pf(x_i)
    • convex: f′′(x)≥0f''(x)\geq 0
  • f(x)=−xlog⁡xf(x)=-x\log x is concave

Entropy

Entropy: H(X)=−∑x∈Xp(x)log⁡p(x)=Eplog⁡1p(X)H(X)=-\sum_{x\in\mathcal{X}}p(x)\log p(x)=E_{p}\log\frac{1}{p(X)}

  • 0log⁡0→00\log 0\rightarrow 0
  • 0≤H(X)≤log⁡∣X∣0\leq H(X)\leq \log|\mathcal{X}|
  • uniform XX: H(X)=log⁡∣X∣H(X)=\log|\mathcal{X}|
  • Hb(X)=log⁡baHa(X)H_b(X)=\log_baH_a(X)

Joint Entropy: H(X,Y)=−Elog⁡p(X,Y)=−∑x∈X∑y∈Yp(x,y)log⁡p(x,y)H(X,Y)=-E\log p(X,Y)=-\sum_{x\in\mathcal{X}}\sum_{y\in\mathcal{Y}}p(x,y)\log p(x,y)

  • H(X,X)=H(X)H(X,X) = H(X)
  • H(X,Y)=H(Y,X)H(X,Y) = H(Y,X)

Conditional Entropy: H(Y∣X)=∑x∈Xp(x)H(Y∣X=x)=−∑x∈X∑y∈Yp(x,y)log⁡p(y∣x)=−Elog⁡p(y∣x)H(Y|X)=\sum_{x\in\mathcal{X}}p(x)H(Y|X=x)=-\sum_{x\in\mathcal{X}}\sum_{y\in\mathcal{Y}}p(x,y)\log p(y|x)=-E\log p(y|x)

  • H(Y∣X)≤H(X)H(Y|X)\leq H(X)
  • remaining uncertainty when XX is known
  • H(X∣Y)≠H(Y∣X)H(X|Y)\neq H(Y|X)
  • H(X∣Y)+H(Y)=H(Y∣X)+H(X)=H(X,Y)H(X|Y)+H(Y)=H(Y|X)+H(X)=H(X,Y)
  • Chain rule: H(X1,X2,⋯ ,Xn)=H(X1)+H(X2∣X1)+⋯+H(Xn∣Xn−1,⋯ ,X1)H(X_1,X_2,\cdots,X_n)=H(X_1)+H(X_2|X_1)+\cdots+H(X_n|X_{n-1},\cdots,X_1)
  • Zero conditional entropy: if H(Y∣X)=0,Y=f(X)H(Y|X)=0,Y=f(X)

Relative Entropy (Kullback-Leibler distance): D(p∥q)=∑x∈Xp(x)log⁡p(x)q(x)=Eplog⁡p(X)q(X)=Ep(−log⁡q(x))−H(p)D(p\|q)=\sum_{x\in X}p(x)\log\frac{p(x)}{q(x)}=E_p\log\frac{p(X)}{q(X)}=E_p(-\log q(x))-H(p)

  • D(p∥q)≥0D(p\|q)\geq 0 equality iff p(x)=q(x)p(x)=q(x) (prove by concavity)
  • variational distance V(p,q)=∑x∈X∣p(x)−q(x)∣V(p,q)=\sum_{x\in\mathcal{X}}|p(x)-q(x)|
  • Pinsker's inequlity: D(p∥q)≥12ln⁡2V2(p,q)D(p\|q)\geq\frac{1}{2\ln 2}V^2(p,q)
  • D(p∥u)=log⁡∣X∣−H(X)D(p\|u)=\log|\mathcal{X}|-H(X)

Mutual Information: I(X;Y)=∑x∑yp(x,y)log⁡p(x,y)p(x)p(y)=D(p(x,y)∥p(x)p(y))=Ep(x,y)log⁡p(X,Y)p(X)p(Y)I(X;Y)=\sum_x\sum_yp(x,y)\log\frac{p(x,y)}{p(x)p(y)}=D(p(x,y)\|p(x)p(y))=E_{p(x,y)}\log\frac{p(X,Y)}{p(X)p(Y)}

  • Independent I(X;Y)=0I(X;Y)=0
  • I(X;X)=H(X)I(X;X)=H(X)
  • I(X;Y)=H(X)−H(X∣Y)=H(X)+H(Y)−H(X,Y)I(X;Y)=H(X)-H(X|Y)=H(X)+H(Y)-H(X,Y)

Conditional Mutual Information: I(X;Y∣Z)=H(X∣Z)−H(X∣Y,Z)=Ep(x,y,z)log⁡p(X,Y∣Z)p(X∣Z)p(Y∣Z)I(X;Y|Z)=H(X|Z)-H(X|Y,Z)=E_{p(x,y,z)}\log\frac{p(X,Y|Z)}{p(X|Z)p(Y|Z)}

  • Chain rule: I(X1,X2,⋯ ,Xn;Y)=∑i=1nI(Xi;Y∣Xi−1,⋯ ,X1)I(X_1,X_2,\cdots,X_n;Y)=\sum_{i=1}^nI(X_i;Y|X_{i-1},\cdots,X_1)

Conditional Relative Entropy: D(p(y∣x)∥q(y∣x))=Ep(x,y)log⁡q(Y∣X)q(Y∣X)D(p(y|x)\|q(y|x))=E_{p(x,y)}\log \frac{q(Y|X)}{q(Y|X)}

Inequality

  • H(X1,X2,⋯ ,Xn)≤∑i=1nH(Xi)H(X_1,X_2,\cdots,X_n)\leq\sum_{i=1}^nH(X_i) equality iff XiX_i are independent
  • I(X;Y∣Z)I(X;Y|Z) and I(X;Y)I(X;Y)
    • X→Y→Z:I(X;Z∣Y)=0X\rightarrow Y\rightarrow Z:I(X;Z|Y)=0
    • Z=X+Y mod 2:I(X;Y∣Z)>I(X;Y)Z=X+Y\bmod 2:I(X;Y|Z)>I(X;Y)
  • Data Processing Inequality: X→Y→Z,I(X;Y)≥I(X;Z)X\rightarrow Y\rightarrow Z,I(X;Y)\geq I(X;Z)
    • X→Y→Z,I(X;Y)=I(X;Z)+I(X;Y∣Z)X\rightarrow Y\rightarrow Z,I(X;Y)=I(X;Z)+I(X;Y|Z)
  • I(X;Y;Z)=I(X;Y)−I(X;Y∣Z)I(X;Y;Z)=I(X;Y)-I(X;Y|Z)
  • Perfect Secrecy: H(X)≤H(Z)H(X)\leq H(Z) 信息长度小于秘钥长度
  • Fano's Inequality: relationship between PeP_e and H(X∣Y)H(X|Y)
    • X→Y→X^,Pe=P(X^≠X)X\rightarrow Y\rightarrow \hat X,P_e=P(\hat X\neq X)
    • H(Pe)+Pelog⁡∣X∣≥H(X∣X^)≥H(X∣Y)H(P_e)+P_e\log|\mathcal{X}|\geq H(X|\hat X)\geq H(X|Y)
    • weaken: Pe≥H(X∣Y)−1log⁡∣X∣P_e\geq\frac{H(X|Y)-1}{\log |\mathcal{X}|}
  • Log sum inequality: for nonnegative numbers, ∑i=1nailog⁡aibi≥(sumi=1nai)log⁡∑i=1nai∑i=1nbi\sum_{i=1}^na_i\log\frac{a_i}{b_i}\geq(sum_{i=1}^na_i)\log\frac{\sum_{i=1}^na_i}{\sum_{i=1}^nb_i}, equal iff aibi=c\frac{a_i}{b_i}=c
  • H(p)H(p) is concave of pp
  • D(p∥q)D(p\|q) is convex in pair (p,q)(p,q)