IN : 0≤n<100} e X ha distribuzione uniforme, H(X) = log2100 = 6.6439 (arrotond.).3. ENTROPIA e INFORMAZIONE.
I fattori casuali sono elementi di incertezza; l'informazione è qualcosa che fa diminuire l'incertezza. Già questa osservazione fa percepire i collegamenti tra probabilità e questioni legate alla trattazione delle informazioni.
Anche il contenuto informativo di un messaggio in genere si misura in bit, ma in questo caso con un significato diverso rispetto a quello come unità di misura (dello spazio) di memoria. Partiamo con un esempio.
A) So che è stata lanciata 23 volte una moneta equa. Voglio scoprire l'esito di questo esperimento, cioè, sostanzialmente, la sequenza di 23 caratteri scelti tra T e C che lo rappresenta; supponiamo che essa sia "TTCCTCTCCCTTTTCTCTTCCCC"
B) Idem, sapendo che la moneta ha la stessa faccia da entrambi i lati; supponiamo che l'esito sia "CCCCCCCCCCCCCCCCCCCCCCC"
Rispetto al codice ASCII le due stringhe sono lunghe 23·8=184 bit
Però se codificassi testa e croce rispettivamente con 0 e 1 potrei rappresentare i due esiti con due stringhe binarie "00110101110000101001111" e "11111111111111111111111", entrambe di 23 bit.
Questo è il modo che comporta meno bit per descrivere uscita per uscita l'esito dell'esperimento.
Ma per scoprire l'esito nel caso B serve una quantità di informazione minore che nel caso A:
A: devo chiedere 23 volte "è uscita testa (0) o croce (1)?" : 23 bit di informazione
B: devo fare una sola domanda: 1 bit di informazione
Intuitivamente possiamo descrivere il bit così:
bit = quantità di informazione in grado di indicare una scelta tra due possibilità equiprobabili
Vogliamo descrivere un numero intero compreso tra 1 e 99 usando i simboli 0 e 1. Consideriamo due possibili codifiche:
|
CODICE BINARIO PURO 7 bit (99 = 1100011) |
CODICE BCD (codifica binaria delle cifre decimali) 8 bit (99 = 10011001) |
La lunghezza in bit di un messaggio dipende dalla codifica adottata per descriverlo.
La prima codifica è meno dispendiosa. Una codifica è tanto meno dispendiosa quanto più la sua lunghezza in bit è vicina alla misura in bit del suo contenuto informativo.
• Qual è il contenuto informativo del messaggio con cui si sceglie un numero tra 100 equiprobabili?
Esempio più semplice:
• Di quanti bit di informazione si ha bisogno per trasmettere un numero tra 0 e 31? ovvero:
• Quante domande a risposte (equiprobabili) "sì/no" o "vero/falso" bisogna fare per individuare un numero scelto "a caso" (con distribuzione uniforme) tra 0 e 31?
[l'ipotesi di uniformità è quella che usualmente si fa in assenza di informazioni sul fenomeno: vedi scheda 4, §6]
<16
VERO / \ FALSO
______________/ \______________
<8 <24
_____/ \_____ _____/ \_____
<4 <12 <20 <28
_/ \_ _/ \_ _/ \_ _/ \_
<2 <6 <10 <14 <18 <22 <26 <30
/ \ / \ / \ / \ / \ / \ / \ / \
<1 <3 <5 <7 <9 <11 <13 <15 <17 <19 <21 <23 <25 <27 <29 <31
/\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
Si fanno 5 domande: occorrono 5 bit di informazione
Qualunque sia il sistema fisico S con cui rappresento questi numeri (cifre decimali, scrittura romana, cifre binarie, dispositivo elettronico, pallottoliere, …), cioè qualunque sia la sorgente S del messaggio, se so che essi sono equiprobabili (ovvero che i 32 stati del sistema che li rappresentano sono tali), dico che S ha un'entropia di 5 bit: è la quantità di informazione necessaria a dissolvere l'incertezza del destinatario del messaggio.
Per quanto finora visto siamo in grado di dire solo che l'entropia associata ad un sistema fisico a 2m stati equiprobabili è pari a m.
Tornando ai numeri tra 0 e 99, per individuare un numero non posso fare solo domande a risposta equiprobabile. Ad es. se il numero fosse 0, alla 3ª domanda posso chiedere se il numero sta tra 0 e 11 (12 possibilità) o tra 12 e 24 (13 possibilità) o se è tra 0 e 12 (13 possibilità) o tra 13 e 24 (12 possibilità); conveniamo di fare la prima scelta (sottointervallo sinistro meno numeroso di quello destro), in modo da ottenere un grafo come il seguente. Per individuare il numero in alcuni casi servono 6 domande, in altri 7. Ciò è in accordo con la definizione precedente: gli stati possibili sono 100 e 26 = 64 < 100 < 128 = 27.
<50
VERO / \ FALSO
_____________/ \______________
<25 <75
_____/ \_____ _____/ \_____
<12 <37 <62 <87
___/ \___ __/ \__ __/ \__ __/ \__
<6 <18 ... ... ... ... ... ...
__/ \__ _/ \_
<3 <9 ... ...
_/ \_ _/ \_
<1 <4 ... ..
/\ /\
0 <2 3 <5
/\ /\
1 2 4 5
1 bit è quindi l'entropia di un sistema a due stati equiprobabili.
Volendo si può cambiare unità di misura e assumere il ter (entropia di un sistema a 3 stati equiprobabili: 1 ter = log23 bit) o il decit (entropia di un sistema a 10 stati equiprobabili: 1 decit = log210 bit) o il nat (1 nat = log2e bit) o …; allora l'entropia sarebbe pari a log3n ter o log10n decit o logen nat o …. D'ora in poi useremo solo i bit come unità di misura (e in genere li sottintenderemo) e scriveremo log al posto di log2.
Possiamo interpretare il sistema fisico con una variabile casuale discreta X (dotata di una certa legge di distribuzione) e indicare con H(X) la sua entropia. Quindi, indicato con Dom(X) il domino di X (cioè i valori che X può assumere), abbiamo:
| se Dom(X)={x1, …, xn} e X ha legge di distribuzione uniforme (Pr(X=xi)=1/n per i=1,…, n), allora H(X) = log2n |
Dunque, tornando ai numeri tra 0 e 99, se Dom(X)={n IN : 0≤n<100} e X ha distribuzione uniforme, H(X) = log2100 = 6.6439 (arrotond.).
| 1 |
• Problema
Si eseguono 2 lanci indipendenti di una moneta equa. Si vuole trasmettere il messaggio "è uscita la stessa faccia"; qual è l'informazione associata a tale messaggio? Qual è quella per comunicare l'esito completo del lancio dei due dadi?
Per la prima domanda posso ragionare così: gli esiti "stessa faccia" e "faccia diversa" sono equipro-babili; quindi l'entropia è 1.
Per la seconda: gli esiti possibili sono TT, TC, CT, CC e sono equiprobabili; quindi: H = log24 = 2. Oppure potevo trovare l'informazione del primo lancio (H1 = 1 bit) e quella del 2° (H2 = 1 bit) e fare la somma, trovando H = H1+H2 = 1+1 bit = 2 bit. Più in generale, componendo due sistemi indipendenti X e Y entrambi a stati equiprobabili si trova, in modo analogo, che il sistema composto (X,Y) è a stati equiprobabili e ha entropia pari alla somma delle entropie di X e Y (additività dell'entropia).
• Altro problema
Eseguo 2 lanci indipendenti di una moneta truccata tale che (indicata con U l'uscita) Pr(U="testa")=0.7 e Pr(U="croce")=0.3. Voglio trasmettere il messaggio "è uscita la stessa faccia". Qual è l'informazione associata a tale messaggio?
Questa volta gli esiti non sono più equiprobabili. Idea: cercare di esprimere l'entropia H in funzione della probabilità dei vari stati.
Nel caso di un sistema X a n stati equiprobabili x1, x2, … indicata con p la probabilità Pr(X=xi) = 1/n, abbiamo n = 1/p e quindi H(X) = log n = log 1/p = – log p.
Nel caso di un sistema X a n stati non equiprobabili x1, x2, … (con probabilità p1, p2, …) l'entropia può essere definita come la media pesata (con pesi p1, p2, …) dei valori –log pi:
[cioè come H(X) = M(–log P) dove P è la variabile aleatoria che esprime la probabilità di uno stato qualsiasi (aleatorio) del sistema X]
H(X) = Σ pi (– log pi) = – Σ pi log pi (Shannon, 1948)
|
I valori –log pi sono chiamati informazione parziale contenuta del messaggio "X ha assunto lo stato xi".
Tornando alla moneta truccata, l'entropia di un lancio è maggiore rispetto al caso equo? Se si eseguono due lanci, qual è l'informazione associata al messaggio "è uscita la stessa faccia"? Utilizza POLIGON, che ha predefinita la funzione logaritmo binario (o opportunamente una CT) o il grafico riportato a fianco della funzione  -x·log2(x). |
|
||||
|
|
F: -xLB(x) u = F(.7^2)+f(.3^2)+2F(.3*.7) w = (F(.7)+F(.3))*2 |
||||
Più in generale:
Date X e Y indipendenti con Dom(X)={x1,…,xn} e Dom(Y)={y1,…,ym}, si ha H(X,Y)=H(X)+H(Y).
| 3 |
Quanto dimostrato conferma la bontà della scelta della definizione. La bontà è confermata anche dal fatto che si possono dimostrare le seguenti proprietà, che ci aspettiamo valgano in base all'idea intuitiva di entropia (per la dimostrazione si può vedere, ad es., il manuale di Ventsel):
• H(X,Y)≤ H(X)+H(Y)
• L'entropia di un sistema con un numero finito di stati raggiunge un massimo quando tutti gli stati sono equiprobabili. Nel caso di un sistema a 2 stati la dimostrazione è facile: indicata p1 con x si ha p2=1–x; quindi H=–xlogx–(1–x)log(1–x); derivando si trova che il massimo lo si ha per x=1–x, cioè x=1/2.
| <<< Paragrafo precedente | Paragrafo successivo >>> |
