Esercizio - Entropia del bacio (teoria dell'informazione)

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

Testo (esercizio "Kissing theory"). Un ragazzo, studente di ingegneria dell'informazione, a una festa incontra una ragazza e parlano di teoria dell'informazione. A fine serata lei dice: "Lo sai che il $75\,\%$ dei ragazzi, ma solo il $25\,\%$ delle ragazze, bacia con gli occhi aperti? Eppure, prima di te, ho baciato solo chi li teneva aperti. Quindi ho guadagnato $0{,}811$ bit di informazione sul tuo conto! E tu?". La ragazza era incerta sulla variabile $E_{boy}=\{\text{aperti},\text{chiusi}\}$ (stato degli occhi del ragazzo): $H(E_{boy})$ valeva $0{,}811$ bit all'incontro e dopo la festa vale $0$.

1. Cosa può dire il ragazzo sull'analoga variabile $E_{girl}$, ragionando dal suo punto di vista?
2. Il ragazzo può calcolare un'altra variazione di entropia dopo la frase della ragazza. All'incontro stima la probabilità $p_k$ che lei abbia baciato $k$ ragazzi prima: $p_0=\frac1{16}$, $p_1=\frac3{16}$, $p_2=\frac14$, $p_k=\big(\frac12\big)^{k-1}$ per ogni $k\ge3$. Quanto vale l'entropia di $k$ alla fine della festa?

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 →, Formula delle probabilità totali e formula di BayesSe (A_i) è una partizione di Ω, P(B) = Σ P(B ∣ A_i) P(A_i) (probabilità totali); la formula di Bayes inverte il condizionamento: P(A_k ∣ B) = P(B ∣ A_k) P(A_k) / P(B).Formula delle probabilità totali e formula di Bayes →, 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 →.

1. L'entropia della ragazza e quella del ragazzo

Il $0{,}811$ della ragazza. $E_{boy}$ è binaria con $P[\text{aperti}]=0{,}75$: la sua entropia è l'entropia binaria $$H(E_{boy})=h(0{,}75)=-0{,}75\log_20{,}75-0{,}25\log_20{,}25=0{,}75\cdot0{,}415+0{,}25\cdot2=0{,}811\ \text{bit},$$ come dice il testo. Dopo aver visto gli occhi del ragazzo l'incertezza è $0$: l'entropia è scesa di $0{,}811$ bit.

Il ragazzo. $E_{girl}$ è binaria con $P[\text{aperti}]=0{,}25$ (e chiusi $0{,}75$): $$H(E_{girl})=h(0{,}25)=-0{,}25\log_20{,}25-0{,}75\log_20{,}75=0{,}811\ \text{bit}.$$ È lo stesso valore, perché l'entropia binaria è simmetrica: $h(p)=h(1-p)$. Dopo il bacio il ragazzo conosce lo stato degli occhi di lei ($H=0$). Quindi può rispondere "anch'io": ha guadagnato $0{,}811$ bit sul conto di lei, come entropia media.

Osservazione. L'entropia è l'informazione media. L'informazione portata dall'evento effettivamente osservato dipende dall'esito, $i=-\log_2P$: "ragazzo con gli occhi aperti" ($P=0{,}75$) porta solo $0{,}415$ bit; se invece la ragazza avesse avuto gli occhi aperti ($P=0{,}25$) il ragazzo avrebbe appreso $2$ bit, se chiusi $0{,}415$ bit. Il valore $0{,}811$ è la media $0{,}25\cdot2+0{,}75\cdot0{,}415$: quindi la frase "ho guadagnato $0{,}811$ bit" è vera per la riduzione di entropia dell'esperimento (media), non per l'informazione dell'esito specifico.

2. Entropia del numero di ragazzi baciati

Prima della frase. La distribuzione è corretta: $\frac1{16}+\frac3{16}+\frac14+\sum_{k\ge3}\big(\tfrac12\big)^{k-1}=\frac1{16}+\frac3{16}+\frac14+\frac12=1$ (la serie geometrica $\sum_{k\ge3}2^{1-k}=\frac14\cdot\frac1{1-1/2}=\frac12$). Entropia: $$H(k)=-\sum_kp_k\log_2p_k=\tfrac1{16}\cdot4+\tfrac3{16}\log_2\tfrac{16}3+\tfrac14\cdot2+\sum_{k\ge3}\big(\tfrac12\big)^{k-1}(k-1)\ ,$$ dove l'ultimo termine vale $\sum_{j\ge2}j2^{-j}=2-\frac12=\frac32$ (da $\sum_{j\ge1}j2^{-j}=2$, 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 →). Quindi $H(k)=0{,}25+0{,}4528+0{,}5+1{,}5=2{,}703$ bit.

Dopo la frase. Il ragazzo apprende un'informazione su $k$: tutti i $k$ ragazzi baciati prima avevano gli occhi aperti. Ogni ragazzo li tiene aperti con probabilità $0{,}75$, indipendentemente, quindi $P[\text{tutti aperti}\mid k]=0{,}75^k$. Per la formula di Bayes la nuova distribuzione è $$q_k=P[k\mid\text{tutti aperti}]=\frac{p_k\,0{,}75^k}{Z},\qquad Z=\sum_kp_k\,0{,}75^k.$$ Si calcola $Z$ sommando la parte finita e la serie geometrica di ragione $\frac38$ ($\frac12\cdot\frac34$): $$Z=\frac1{16}+\frac3{16}\cdot\frac34+\frac14\cdot\frac9{16}+\sum_{k\ge3}\Big(\frac12\Big)^{k-1}\Big(\frac34\Big)^k=\frac1{16}+\frac9{64}+\frac9{64}+\frac{27}{160}=\frac{41}{80}=0{,}5125,$$ perché $\sum_{k\ge3}2^{1-k}(3/4)^k=\frac34\sum_{k\ge3}(3/8)^{k-1}=\frac34\cdot\frac{(3/8)^2}{1-3/8}=\frac{27}{160}$. Allora $$q_0=\frac5{41}=0{,}122,\quad q_1=q_2=\frac{45}{164}=0{,}274,\quad q_k=\frac{60}{41}\Big(\frac38\Big)^{k-1}\ (k\ge3):\ q_3=0{,}206,\ q_4=0{,}077,\dots$$ (somma $=1$). L'entropia diventa $$H(k\mid\text{tutti aperti})=-\sum_kq_k\log_2q_k=2{,}425\ \text{bit}$$ (calcolata sommando i termini al calcolatore). La variazione di entropia è $2{,}425-2{,}703=-0{,}278$ bit: la frase della ragazza toglie solo $0{,}28$ bit di incertezza sul suo passato (la distribuzione di $k$ si sposta verso i valori bassi: la media passa da $E[k]=2{,}69$ a $2{,}01$, perché avere molti baci tutti "a occhi aperti" è meno probabile).