information theory

• $A_s=\{s_1,s_2,\dots ,s_{\alpha }\}$ is the set of source symbols

• (message) $s=(s_1,s_2,\dots ,s_k)\in A_s^k$

• (channel input) $x=g(s)$

  • $A_x=\{x_1,x_2,\dots ,x_m\}$ is the set of channel input symbols
  • $x=(x_1,x_2,\dots ,x_n)\in A_x^n$ is a sequence of codewords

• $p(X)=\{p(x_1),p(x_2),\dots ,p(x_m)\}$

• (channel output) $y=(y_1,y_2,\dots ,y_n)\in A_y^n$

  • $A_y=\{y_1,y_2,\dots ,y_m\}$ is the set of channel output symbols

• $X$ is a discrete random variable

• $p(x)$ is the probability of an outcome $x$

• $\mathcal{X}=\{x:X=x\}$ is the alphabet of $X$.

  • $|\mathcal{X}|=n$

• The self-information (or information content) of an outcome $x\in \mathcal{X}$ is defined as $I(x)=-\log p(x)$

  • (It measures how surprising or informative the specific outcome $x$ is. If $p(x)$ is small, then observing $x$ is rare and thus carries more information, so $I(x)$ is large. Conversely, if $p(x)$ is large, then observing $x$ is common and carries less information, so $I(x)$ is small.)
  • $I(x)\ge 0$
  • $I(x,y)=I(x)+I(y)$

• The (Shannon) entropy of $X$ is defined as $H(X)=-\sum _{x\in \mathcal{X}}p(x)\log p(x).$

  • $H(X)=\mathbb{E}[I(X)]$
  • $H(X)\ge 0$
  • $H(X)\le \log n$, with equality if and only if $X$ is uniformly distributed over $\mathcal{X}$
  • $H(X,Y)=H(X)+H(Y)$

• (examples)

  • (deterministic variable) Let $p(x_0)=1$ for some $x_0\in \mathcal{X}$, then $H(X)=0$
  • (uniform distribution) Let $p(x)=\frac{1}{n}$ for all $x\in \mathcal{X}$, then $H(X)=\log n$
    • (fair die) If $n=6$, then $H(X)=\log 6\approx 2.585$
  • (binary variable) Let $p(0)=p$ and $p(1)=1-p$, then $H(X)=-p\log p-(1-p)\log (1-p)$
    • (fair coin) If $p=\frac{1}{2}$, then $H(X)=1$

• (Shannon’s source coding theorem)

• $\frac{H(X)}{{\log }_{2}a}\le \mathbb{E}[S]<\frac{H(X)}{{\log }_{2}a}+1$

• (maximum possible entropy) $H_{\text{max}}(X)={\log }_{2}n$

• (absolute redundancy) $R=H_{\max }(X)-H(X)$

• ((relative) redundancy) $r=1-\frac{H(X)}{H_{\max }(X)}$