domenica 7 febbraio 2021

Capacità — 10. Monete truccate

“Rieccoci, pronti per parlare di trasmissioni, canali, capacità”.

“È passato molto tempo”.

“Sì, facciamo un riassuntino. Abbiamo visto come si può calcolare la capacità di un canale che trasmette informazioni, semplificando all'osso il significato di informazione. In pratica, ci siamo ricondotti all'idea che per ottenere informazioni io posso fare domande e ottenere, come risposte, un o un no. Con tanti e no posso ottenere risposte anche a domande complicate, basta farne abbastanza”.

“Alla fine, abbiamo visto che le domande che servono, in media, sono uguali al logaritmo in base 2… uhm, il logaritmo in base 2 di che cosa?”.

“Del numero di domande che devo fare per capire quale dei tanti messaggi è stato trasmesso, il tutto diviso per la lunghezza dei messaggi in questione”.

“Uhm, ok, devo ripassare”.

“Dopo facciamo un altro esempio, dovrebbe tornare tutto alla mente”.

“Speriamo”.

“Chiamiamo entropia di informazione, quindi, il numero medio minimo di domande che, alla lunga, mi servono per individuare quale messaggio viene trasmesso”.

Numero medio minimo di domande alla lunga. Non esisteva una definizione più complicata?”.

“Eh. Allora: medio si riferisce al fatto che vogliamo capire, in media, quante domande ci servono per individuare un messaggio. Devo ragionare sulle medie perché in alcuni casi può servire un certo numero di domande, in altri casi un numero di domande maggiore, o minore. Il numero di domande è costante quando il numero di messaggi è una potenza di 2, altrimenti in alcuni casi potrebbero servire meno o più domande rispetto ad altri casi”.

“Va bene, questo lo ricordo”.

“Parliamo di minimo perché voglio fare il minor numero di domande possibile, in media, senza perdere tempo”.

“E questo mi pare logico”.

“E diciamo alla lunga perché più si allungano i messaggi, migliore è il calcolo teorico. Insomma, se per un messaggio abbiamo tre casi da esaminare e possiamo ottenere risposte binarie, in alcuni casi serve una domanda e in altri casi ne servono due. Se però cominciamo ad accumulare messaggi, allora il calcolo che facciamo si avvicina sempre di più al logaritmo”.

“Vero, ricordo anche questo esempio”.

“Se, per esempio, abbiamo una moneta non truccata, in cui cioè le due facce hanno entrambe probabilità pari a 1/2 di presentarsi, allora indichiamo con H(1/2, 1/2) l'entropia di informazione della moneta”.

“Mi serve una domanda sola per scoprire cos'è uscito, no?”.

“Certo. Una domanda con una moneta, due domande con due monete, tre domande con tre monete, e così via. Alla lunga, ma anche alla corta, ti serve una domanda per moneta”.

“Quindi l'entropia vale 1. Uno cosa, poi?”.

“Un bit: l'avevamo chiamata così, l'unità di misura”.

“Giusto”.

“Ora prendiamo una moneta truccata. Una moneta leggermente sbilanciata, in cui Testa ha probabilità di uscita pari a 2/5, e Croce ha probabilità 3/5. Vogliamo calcolare l'entropia di questa moneta, cioè H(2/5, 3/5). Ti aspetti che sia maggiore o minore di 1?”.

“Uhm, non saprei”.

“Ti è più facile conoscere il risultato del lancio di questa moneta, o di quella equilibrata?”.

“Ah, se la metti così… quella equilibrata è imprevedibile, non posso assolutamente prevedere cosa uscirà”.

“Mentre l'altra?”.

“Bè, l'altra è leggermente sbilanciata, se dovessi scommettere, alla lunga direi che è più conveniente scommettere su Croce”.

“Quindi sai qualcosa di più: quella moneta è più prevedibile”.

“Allora l'entropia dovrebbe essere minore di 1: se l'imprevedibilità totale la risolvo con una domanda, questa dovrei risolverla con un po' meno fatica. Ma come la calcoliamo?”.

“Simuliamo la moneta con un'urna contenente cinque palline: due sono contrassegnate con la T e tre, invece, con la C”.

“Ok”.

“Ora calcoliamo, prima di tutto, l'entropia di quest'urna, supponendo che essa contenga 5 palline distinguibili”.

“Ah, quindi non ci interessa soltanto sapere se esce T o C?”.

“Per ora no, vogliamo più dettaglio”.

“Allora, è come se ci fossero 5 scelte e io dovessi scoprire quale di queste è stata fatta. Da tutto quello che abbiamo detto, oserei dire che l'entropia è il logaritmo in base 2 di 5”.

“Esatto, abbiamo fatto tutta la fatica che abbiamo fatto per poter, ora, rispondere velocemente a questa domanda. Alla lunga ti servono, in media, log25 domande”.

“Bene. Quindi?”.

“Quindi ora possiamo rifare lo stesso calcolo in un altro modo. Per sapere quale pallina è uscita, prima di tutto devi sapere se è uscito T o C, e poi quale T o quale C”.

“Oserei dire che è ovvio, ma non capisco come mi possa aiutare”.

“Il numero medio di domande che devi fare per sapere se è uscito T o C è proprio H(2/5, 3/5)”.

“Grazie, ma non lo conosco!”.

“Non importa, è quello, teniamolo indicato”.

“Ah, vabbé”.

“Poi, per sapere quale T…”.

“Mi serve ancora una domanda, perché le T sono due!”.

“Esatto. Attenzione: 2 volte su 5 ti basta una domanda, perché la T esce 2 volte su 5. Permettimi però di indicare il numero di domande (che è pari a 1, in questo caso) come log22”.

“Ok, complichiamoci la vita. Se invece è uscita C… so che di C ce ne sono 3, uhm”.

“Quante domande devi fare per distinguere un oggetto tra 3?”.

“Ah, ma è il solito problema: il logaritmo in base 2 di 3”.

“Esatto. Quindi 3 volte su 5 ti serve un numero di domande pari a log23”.

“Come metto insieme tutto questo?”.

“Da un lato hai visto che per scoprire quale pallina è uscita dall'urna ti servono log25 domande, dall'altro hai visto che puoi arrivare allo stesso risultato prima chiedendoti prima solo se è uscito T o C, e poi quale T o quale C, e cioè H(2/5, 3/5) + 2/5 log22 + 3/5 log23”.

“Mi stai dicendo che abbiamo trovato che log25 = H(2/5, 3/5) + 2/5 log22 + 3/5 log23?

“Esatto”.

“Ma allora posso ricavare H(2/5, 3/5)!”.

“Certo, abbiamo fatto tutta questa fatica per questo motivo. Avanti, arriva alla fine”.

“Ecco qua: H(2/5, 3/5) = log25 − 2/5 log22 − 3/5 log23”.

“Permettimi di giocare un po' con le proprietà dei logaritmi, per scrivere questa formula in un modo più carino e generalizzabile”.

“Va bene”.

“Spezzo in due parti il log25: dico che è uguale a 2/5 log25 + 3/5 log25”.

“Giusto. Vedo che hai usato gli stessi coefficienti dell'altra parte”.

“Esatto. Al momento l'uguaglianza è diventata così: H(2/5,3/5) = 2/5 log25 + 3/5 log25 − 2/5 log22 − 3/5 log23”.

“Va bene. Suppongo che metterai insieme i pezzi con gli stessi coefficienti, giusto?”.

“Sì, scrivo in questo modo: H(2/5, 3/5) = 2/5 (log25 − log22) + 3/5 (log25 − log23)”.

“E ora?”.

“Trasformo le differenze tra logaritmi in logaritmi di rapporti: H(2/5, 3/5) = 2/5 log2(5/2) + 3/5 log2(5/3)”.

“Ah, carino”.

“Bè, puoi fare il calcolo adesso. Viene minore di 1 come ti aspettavi?”.

“Vediamo… viene 0.971. Un po' meno, sì: bella roba”.

“E naturalmente tutto questo si può generalizzare”.

“Non potremmo certo privare un Vero Matematico del piacere di una generalizzazione”.

“Eh, già”.