Capacità — 11. Entropia

“Abbiamo visto un esempio che aveva lo scopo di calcolare quanta informazione può contenere una moneta truccata”.

“Ricordo: il trucco è stato quello di trasformare il problema della moneta truccata nel problema di un'urna contenente un certo numero di palline, alcune con la scritta Testa e altre con la scritta Croce, in modo da rispettare le probabilità di uscita delle due facce della moneta”.

“Esatto. E ci siamo detti che avremmo potuto generalizzare il discorso”.

“Capirai”.

“Mettiamo in ordine le cose, via. Abbiamo n messaggi diversi, che indichiamo con s₁, s₂, …, s_n, ognuno dei quali ha probabilità p₁, p₂, … p_n”.

“E va bene”.

“Approssimiamo le varie probabilità con delle frazioni: p₁ = k₁/N, p₂ = k₂/N, e così via”.

“Ok. Usiamo le frazioni per ricondurci all'esempio dell'urna con le palline, vero?”.

“Esatto. Costruiamo un'urna che contenga N palline, in modo tale che l'estrazione di una di esse rispetti le probabilità dei singoli messaggi”.

“Perfetto”.

“Ora abbiamo due modi per calcolare il numero di domande che ci servono per individuare una singola pallina. Il primo è quello di dire che ci serve un numero di domande pari al log₂N”.

“E questo era facile. L'altro modo suppongo che sia la generalizzazione di quello che abbiamo visto l'ultima volta”.

“Già. L'altro modo consiste prima di tutto nel calcolare il numero medio di domande per sapere se abbiamo estratto una pallina contenente il messaggio s₁, oppure s₂, eccetera; questo numero lo indichiamo con H(k₁/N, …, k_n/N). A questo valore dobbiamo aggiungere il numero medio di domande per capire quale tra le palline etichettate con s₁ è uscita, quale tra quelle etichettate con s₂, e così via. Questi numeri sono uguali a (k₁/N) log₂k₁, (k₂/N) log₂k₂, eccetera”.

“Fammi provare a scrivere l'uguaglianza”.

“Prego”.

“Allora, ecco:”.

log₂N = H(k₁/N, …,k_n/N) + (k₁/N) log₂k₁ + … + (k_n/N) log₂k_n.

“Ottimo. Ora, spezzando il logaritmo in base 2 di N che hai sinistra, come abbiamo fatto l'altra volta, e ridistribuendolo nei logaritmi di destra, puoi arrivare a questa bella formula:”.

H(k₁/N) = (k₁/N) log₂(N/k₁) + … + (k_n/N) log_2(N/k_n).

“Bella, insomma”.

“E se, al posto di quelle frazioni, rimettiamo le probabilità, ecco questa bellissima formula:”.

H(p₁, …,p_n) = p₁log₂(1/p₁) + … + p_nlog₂(1/p_n).

“Che roba”.

“Per esempio, supponiamo che le statistiche di un certo esame ci dicano che metà degli studenti ha come giudizio Non sai niente torna più avanti, un quarto degli studenti ha come giudizio Te la sei cavata perché non posso bocciare tutti, un ottavo degli studenti ha Forse hai capito qualcosa, e l'ultimo ottavo ha Bene, hai capito, allora l'entropia di informazione di questo sistema-esame che può emettere quattro diversi messaggi è uguale a:”.

H(1/2, 1/4, 1/8, 1/8) = 1/2 log₂2 + 1/4 log₂4 + 1/8 log₂8 + 1/8 log₂8 = 7/4 = 1.75 bit.

“Quindi alla lunga mi servono 1.75 domande per sapere che voto ho preso”.

“Esatto, ma per sapere se l'esame è stato superato te ne basta una sola”.

“Meglio abbreviare le sofferenze”.

“Già”.