Sembra essere molto simile a Central Limit Theorem and Law of Large Numbers però per Entropy. This is also called Shannon’s source coding theorem see here

Enunciato AEP

Data una serie di variabili aleatorie $X_{1}, X_{2}, \dots$ i.i.d. $\sim p(x)$ se vale che

$$ -\frac{1}{n} \log p(X_{1}, X_{2}, \dots, X_{n}) \to H(X) $$

in probability (la definizione data in Central Limit Theorem and Law of Large Numbers#Convergence in probability).

Un modo alternativo per enunciarla è così, segue il metodo in (MacKay 2003).

Per un certo $N$ tenderà all’infinito.

$$ \left\lvert \frac{1}{N} H_{\delta}(X^{N}) - H(x) \right\rvert \leq \varepsilon $$

Ossia a grandi linee: dato una variabile aleatoria $X$ e $N$ estrazioni della stessa, possiamo comprimere questa sequenza in $NH(X)$.

Dimostrazione

Principalmente sorvolata, ma utilizza cose simili a Central Limit Theorem and Law of Large Numbers, e una idea simile a Monte Carlo Methods per le probabilità. In realtà nella prima formulazione è un concetto molto semplice il motivo per cui funziona.

$$ -\frac{1}{n} \log p(X_{1}, \dots, X_{n}) = -\frac{1}{n} \sum_{i=1}^{n}\log p(X_{i}) \to -\mathbf{E}[\log p(X)] = H(X) $$

La cosa principale da comprendere è come ci può essere questo fenomeno con convergenza in probabilità, che è una nozione più che altro tecnica per questo discorso.

Typical sets

Elements in the typical set have roughly the same probability.

Questo insieme è un oggetto matematico che ha delle proprietà interessanti, viene corretto analizzarlo dopo che si ha AEP, perché in breve la sua esistenza è giustificata da quello. È l’insieme delle sequenze $(x_{1}, x_{2}, \dots , x_{n})$ prese da una distribuzione $p(x)$ sempre uguale tale per cui valga

$$ 2^{-n(H(X) + \varepsilon)} \leq p(x_{1}, x_{2}, \dots, x_{n}) \leq 2^{-n(H(X) - \varepsilon)} $$

Il motivo per cui abbiamo le cose strane all’esponente è proprio la definizione di convergenza in probabilità data. (basta che le espandi) Ossia il fatto che

$$ P\left( \left\lvert -\frac{1}{n} \log p(x_{1}, x_{2}, \dots, x_{n}) - H(X) \right\rvert > \varepsilon \right) = 0, n \to +\infty $$

Se si espande quanto è presente dentro si ottiene quel bound di sopra.

Proprietà

Vedi 3.1.2 di (Cover & Thomas 2012).

Il risultato importante è che possiamo rappresentare sequenze di $X^{n}$ in media usando $nH(X)$ bits, senza perdita di informazione.

References

[1] Cover & Thomas “Elements of Information Theory” John Wiley & Sons 2012

[2] MacKay “Information Theory, Inference and Learning Algorithms” Cambridge University Press 2003