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|\frac{1}{N}{H}_{\delta }(X^N)-H(x)\right|\le \epsilon$$

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)+\epsilon )}\le p(x_1,x_2,\dots ,x_n)\le 2^{-n(H(X)-\epsilon )}$$

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|-\frac{1}{n}\log p(x_1,x_2,\dots ,x_n)-H(X)\right|>\epsilon \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] MacKay “Information Theory, Inference and Learning Algorithms” Cambridge University Press 2003

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