Esercizio - entropia del numero di lanci di una moneta

Questa pagina non ha ancora la versione ripasso: qui sotto c'è il testo completo.

Testo. Si lancia più volte una moneta equa ($P_{testa}=P_{croce}=\frac12$). La prima volta che esce croce il processo termina; se esce testa si continua a lanciare. Qual è l'entropia associata al numero di lanci?

Teoria usata: Informazione, entropia e informazione mutuaL'informazione di un evento di probabilità $P$ è $i=\log_2\frac1P$ bit; l'entropia $H(x)=\sum p\log_2\frac1p$ è l'informazione media e misura l'incertezza: $0\le H\le\log_2M$, massimo se i simboli sono equiprobabili. Per due variabili: $\max{H(x),H(y)}\le H(x,y)\le H(x)+H(y)$, $H(x|y)=H(x,y)-H(y)$ e l'informazione mutua $I(x;y)=H(x)-H(x|y)=H(x)+H(y)-H(x,y)\ge0$ (zero se e solo se indipendenti). Per una sorgente di $F_s$ simboli/s: rate di informazione $F_sH_s$, rate nominale $F_s\log_2M$, efficienza $\eta=\frac{H_s}{\log_2M}$.Informazione, entropia e informazione mutua →, Codifica di sorgenteLa codifica di sorgente senza perdita assegna ai simboli (o a parole di $N$ simboli) parole di codice di lunghezza variabile, corte per i simboli probabili, con una mappa invertibile. Un codice a prefisso è sempre decodificabile; Kraft-McMillan: se il codice è decodificabile $\sum M^{-l_i}\le1$ e viceversa esiste un codice a prefisso con quelle lunghezze. Shannon: $L\ge\frac{H}{\log_2M}$ e esiste un codice con $L<\frac{H}{\log_2M}+1$ (lunghezze $\lceil\log_M\frac1p\rceil$). Shannon-Fano divide dall'alto, Huffman unisce dal basso i due meno probabili ed è ottimo; raggruppare simboli e la codifica aritmetica si avvicinano al limite.Codifica di sorgente →, Distribuzione geometricaGeo(p) è il numero della prova in cui arriva il primo successo in prove indipendenti: P(X = n) = (1−p)^(n−1) p per n ≥ 1, P(X > n) = (1−p)^n (lunga attesa), media 1/p, varianza (1−p)/p², ed è senza memoria.Distribuzione geometrica →, Serie notevoli - geometrica, telescopica, armonicaLe serie di cui si conosce il carattere e da usare come termine di paragone: geometrica (converge a 1/(1-q) se |q|<1), telescopiche (somma b_1 - lim b_n, come Mengoli), armonica generalizzata (1/n^alpha converge se e solo se alpha>1).Serie notevoli - geometrica, telescopica, armonica →, Regole di derivazioneDerivate delle funzioni elementari e delle loro inverse (arcsin, arctan, settcosh...) e regole di calcolo: linearità, prodotto (Leibniz), quoziente, funzione composta (regola della catena), funzione inversa, f(x)^g(x).Regole di derivazione →.

Distribuzione del numero di lanci

Sia $N$ il numero di lanci. $N=n$ significa $n-1$ teste seguite da una croce, in $n$ lanci indipendenti, quindi $$p_N(n)=\left(\frac12\right)^{n-1}\cdot\frac12=\frac1{2^n},\qquad n=1,2,3,\dots$$ (è la distribuzione geometrica di parametro $\frac12$). Verifica: $\sum_{n\ge1}2^{-n}=\frac{1/2}{1-1/2}=1$ ✓. I valori possibili sono infiniti, ma l'entropia si calcola come per un alfabeto finito, con la somma estesa a tutti gli $n$.

Informazione ed entropia

L'informazione dell'evento "$N=n$" è $i(n)=\log_2\frac1{p_N(n)}=\log_22^n=n$ bit: più il risultato è raro, più informa (uscita $N=5$: $5$ bit; $P=\frac1{32}$). L'entropia è l'informazione media: $$H(N)=\sum_{n=1}^{\infty}p_N(n)\,i(n)=\sum_{n=1}^\infty\frac n{2^n}.$$

Calcolo della somma. Per $q=\frac12$ e $S=\sum_{n\ge1}nq^n$ si usa un trucco di scorrimento. Moltiplicando per $q$: $qS=\sum_{n\ge1}nq^{n+1}=\sum_{m\ge2}(m-1)q^m$. Sottraendo membro a membro, $$S-qS=\sum_{n\ge1}nq^n-\sum_{n\ge2}(n-1)q^n=q+\sum_{n\ge2}q^n=\sum_{n\ge1}q^n=\frac q{1-q},$$ quindi $S(1-q)=\frac q{1-q}$ e $$S=\frac q{(1-q)^2}.$$ (Alternativamente con la derivata della serie geometrica: $\sum_{n\ge0}q^n=\frac1{1-q}$ si deriva rispetto a $q$ e dà $\sum_{n\ge1}nq^{n-1}=\frac1{(1-q)^2}$; moltiplicando per $q$ si ritrova $S$.) Con $q=\frac12$: $$H(N)=\frac{1/2}{(1/2)^2}=2\ \text{bit}.$$

Controllo numerico: i primi termini $\frac12+\frac24+\frac38+\frac4{16}+\frac5{32}+\frac6{64}+\dots=0{,}5+0{,}5+0{,}375+0{,}25+0{,}156+0{,}094+\dots$ si avvicinano a $2$ (con $60$ termini la somma è $2{,}000$).

Codifica di Shannon

Le probabilità $2^{-n}$ sono potenze di $\frac12$: il teorema di Shannon dice che il limite $\tilde L=H$ si raggiunge. Le lunghezze di Shannon sono $l_n=\left\lceil\log_2\frac1{p_N(n)}\right\rceil=n$ (nessun arrotondamento: sono già intere) e valgono Kraft $\sum_n2^{-n}=1$ (albero binario completo). Il codice è $$N=1\to0,\quad N=2\to10,\quad N=3\to110,\quad N=4\to1110,\quad\dots$$ (codice unario: $n-1$ uni e uno zero). La lunghezza media è $\tilde L=\sum_nn\,2^{-n}=2=H(N)$, quindi l'efficienza è $\eta=\frac H{\tilde L}=1$: il codice è ottimo.

Interpretazione. Questo codice è proprio la sequenza dei lanci (testa $=1$, croce $=0$): ogni lancio è una variabile binaria equiprobabile, che porta $1$ bit di informazione, e se ne fanno in media $E[N]=2$ prima di fermarsi: l'informazione media dell'esperimento, $2$ bit, coincide con il numero medio di lanci.