Information Theory

Say we want to transmit $n$ bits from point A to point B. Let $p$ be the probability of an error per bits, which are IID. How do we make sure the correct message is sent?

Repetition §

[!math|{“type”:“definition”,“number”:“auto”,“setAsNoteMathLink”:false,“title”:“KL Divergence”,“label”:“kl-divergence”,“_index”:0}] Definition 1 (KL Divergence). Let $E$ be a set of events $\{1\dots n\}$ and $p,q$ be probability distributions on $E$. Then, the divergence between the two distributions is the KL-Divergence:

$$D_{KL}(p\mid \mid q)=\sum _{i\in E}{p}_i\log \left(\frac{p_i}{q_i}\right).$$

[!math|{“type”:“theorem”,“number”:“auto”,“setAsNoteMathLink”:false,“title”:“Chernoff Bound”,“label”:“chernoff-bound”,“_index”:1}] Theorem 2 (Chernoff Bound). For random Bernoulli variables $X_i,i\in \{1\dots n\}$,

$$P\left(\sum _i{x}_i>nq\right)<\exp (-n{D}_{KL}(p\mid \mid q))$$

for $q\ge p$.

By repeating