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
$$ -\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).
$$ \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.
$$ 2^{-n(H(X) + \varepsilon)} \leq p(x_{1}, x_{2}, \dots, x_{n}) \leq 2^{-n(H(X) - \varepsilon)} $$$$ 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