Matematica per la Physical History Signature - parte 2

5. Divergenza KL: la "distanza" tra due spiegazioni

L'idea

La divergenza di Kullback-Leibler misura quanto una distribuzione di probabilità P è "diversa" da un'altra Q. Non è una vera distanza (non è simmetrica: D_{KL}(P \| Q) \neq D_{KL}(Q \| P)), ma funziona come una distanza "diretta".

Analogia

Hai due mappe dello stesso territorio. La mappa P dice "qui c'è un fiume, qui una montagna". La mappa Q dice "tutto pianura". Se vai nel territorio reale (che segue P), la mappa Q ti sorprende molto: ti aspetti pianura e trovi montagne. La divergenza KL misura quanto sei "sorpreso" in media se usi Q mentre il mondo è P.

Definizione formale

Per variabili continue, la somma diventa un integrale:

Proprietà chiave: D_{KL}(P \| Q) \geq 0, con uguaglianza se e solo se P = Q (quasi ovunque).

Esempio con numeri

Due storie per una traccia T che può valere 0 o 1:

La storia vera predice meglio la traccia di 0.368 nats in media. Con n = 100 tracce indipendenti, la separazione totale è circa 100 \cdot 0.368 = 36.8 nats: enorme.

Nel protocollo PHS

Appare in §3: D_{\text{causale}}(\mathcal{H}, \mathcal{H}') = D_{KL}(P(\mathcal{T}\mid\mathcal{H}) \| P(\mathcal{T}\mid\mathcal{H}')). È la quantità centrale che misura quanto le tracce penalizzano la storia alternativa.

6. Legge dei grandi numeri: perché più dati aiutano

L'idea

Se fai la media di molte misure indipendenti, il risultato si avvicina al valore vero. Non è magia: è statistica. Più tracce hai, più la storia vera si distingue da quella falsa.

Analogia

Lanci una moneta truccata che dà testa al 60%. Se la lanci 3 volte, potresti vedere 3 croci (sfortuna). Se la lanci 1000 volte, vedrai circa 600 teste. La media "converge" al valore vero.

Definizione formale

Siano X_1, X_2, \dots variabili aleatorie indipendenti con la stessa distribuzione (i.i.d.), con media \mu = \mathbb{E}[X_i]. La legge forte dei grandi numeri (SLLN) dice:

"q.c." (quasi certo) significa: la probabilità che la convergenza fallisca è zero.

Esempio con numeri

Sia X_i = -\log P(T_i \mid \mathcal{H}), cioè la "sorpresa" della traccia i-esima sotto la storia vera. La media \bar{X}_n converge all'entropia H(T_1 \mid \mathcal{H}).

Se H(T_1 \mid \mathcal{H}) = 1 nat, con n = 10 tracce la media sarà circa 1. Con n = 1000, sarà molto vicina a 1 (errore tipico \approx 1/\sqrt{n} = 0.03).

Nel protocollo PHS

Appare in §9: la SLLN è usata per dimostrare che -\frac{1}{n}\log P(\mathcal{T}\mid\mathcal{H}) converge all'entropia h. Questo è il passo chiave del teorema di separazione asintotica.

7. Estremo inferiore (inf): il miglior risultato possibile

L'idea

Se hai un insieme di numeri, il minimo è il più piccolo. Ma se l'insieme è infinito, il minimo potrebbe non esistere (nessun elemento è il più piccolo, ma puoi avvicinarti arbitrariamente). L'estremo inferiore (inf) è il più grande dei "candidati a minimo": il valore che puoi avvicinare quanto vuoi, anche se non lo raggiungi mai.

Analogia

Vuoi comprare una macchina. I prezzi che vedi sono: 10.000€, 9.500€, 9.800€, 9.400€, 9.450€, ... e così via, scendendo di poco ogni volta senza mai fermarsi. Non c'è un "prezzo minimo" (perché la sequenza non si ferma), ma c'è un "inf": 9.000€, il valore sotto cui non scenderai mai, anche se non troverai mai una macchina a quel prezzo.

Definizione formale

Se il minimo esiste, \inf A = \min A. Altrimenti, inf A è il "limite inferiore".

Esempio con numeri

Sia A = \{1, \frac{1}{2}, \frac{1}{3}, \frac{1}{4}, \dots\}. Il minimo non esiste (nessun elemento è 0), ma:

Nel protocollo PHS

Appare in §6: C_{\text{fisico}}(\mathcal{H};\mathcal{A}) = \inf_{\Pi \in \mathcal{A}(\mathcal{H})} \text{Cost}(\Pi). Il costo fisico è il miglior costo possibile tra tutti i protocolli che realizzano la storia. Non è detto che esista un protocollo con quel costo esatto, ma puoi avvicinarti arbitrariamente.

8. Notazione asintotica: o(n) e i limiti

L'idea

Quando n (numero di tracce) diventa grande, alcuni termini diventano trascurabili rispetto ad altri. La notazione o(n) descrive qualcosa che "cresce più lentamente di n": diviso per n, tende a zero.

Analogia

Stai corriendo una maratona (n = chilometri). Il tuo amico corre con te ma ogni tanto si ferma a legarsi le scarpe. Il tempo perso per le scarpe è o(n): su 42 km, 2 minuti totali sono irrilevanti rispetto alle 4 ore di corsa. Ma su 1 km, 2 minuti sono enormi.

Definizioni

• f(n) = o(n) significa: \lim_{n\to\infty} \frac{f(n)}{n} = 0.
• f(n) = O(n) significa: f(n) cresce al massimo linearmente (non più veloce di c \cdot n per qualche costante c).
• f(n) \sim g(n) significa: \lim_{n\to\infty} \frac{f(n)}{g(n)} = 1 (sono "asintoticamente uguali").

Esempio con numeri

Nel teorema di separazione (§9):

Dove R_n = o(n). Se n = 1000, D_{KL} = 0.5, \lambda \Delta C = 10:

• n D_{KL} = 500
• R_n potrebbe essere 50 (che è 0.05 \cdot n, quindi o(n) è vero ma il termine è ancora visibile)
• Per n = 10^6, R_n sarà probabilmente qualche migliaio, trascurabile rispetto a 500.000.

Nel protocollo PHS

Appare in §9: il resto R_n = o(n) garantisce che, asintoticamente, il termine λ Δ C (costo fisico) diventa trascurabile rispetto al termine statistico n D_KL. Ma nel regime finito (n piccolo), λ Δ C domina: è qui che il costo fisico conta.

9. Grafi e centralità: chi è il perno della rete

L'idea

Un grafo è un insieme di nodi collegati da archi. Nel PHS, i nodi sono le tracce e gli archi sono le correlazioni. La centralità di un nodo misura quanto è "importante" per la rete.

Analogia

Una rete di amici. Se togli un amico marginale (conosce solo una persona), la rete non cambia. Se togli l'organizzatore delle feste (conosce tutti), la rete crolla. L'organizzatore ha alta "betweenness centrality": molti cammini tra altre persone passano per lui.

Definizioni

Grafo: G = (V, E), dove V è l'insieme dei nodi (tracce) e E è l'insieme degli archi (correlazioni).

Betweenness centrality di un nodo v:

dove σ_st è il numero di cammini minimi tra s e t, e σ_st(v) è quanti di questi passano per v.

Centralità > 0.3 (regola pratica del PHS): il nodo è "centrale".

Esempio con numeri

Grafo con 4 nodi: ENF, meteo, rumore EM, sciami cosmici. Archi:

• ENF — rumore EM
• meteo — sciami cosmici
• rumore EM — sciami cosmici

I cammini minimi:

• ENF → sciami: passa per rumore EM (\sigma = 1, \sigma(v) = 1 per rumore EM).
• meteo → rumore: passa per sciami (\sigma = 1, \sigma(v) = 1 per sciami).
• ENF → meteo: passa per rumore EM → sciami (\sigma = 1, rumore EM e sciami hanno \sigma(v) = 1).

Betweenness:

• rumore EM: 2/3 ≈ 0.67 (centrale!)
• sciami cosmici: 2/3 ≈ 0.67 (centrale!)
• ENF: 0
• meteo: 0

Le tracce controllate (rumore EM, sciami) sono centrali: se l'avversario le replica male, tutta la rete crolla.

Nel protocollo PHS

Appare in §8 (massa causale, grafo G_ℋ) e §15 (regola pratica: tracce controllate devono essere centrali). Se una traccia controllata è marginale, l'avversario può ignorarla e replicare il resto.

10. Termodinamica per non fisici: Landauer e l'entropia prodotta

L'idea

La termodinamica dice che certe operazioni devono produrre calore. Non è un limite tecnologico: è una legge fisica. Landauer ha dimostrato che cancellare un bit di informazione produce almeno una quantità minima di calore.

Analogia

Hai una scrivania con due cassetti: "importante" e "spam". Ogni giorno metti i documenti nel cassetto giusto. Se un giorno decidi di unificare i cassetti in uno solo "tutto", devi cancellare la distinzione "importante/spam". Per farlo, devi fare lavoro (spostare i documenti, bruciare quelli spam, etc.). Landauer dice che questo lavoro ha un minimo fisico.

Definizione formale

Teorema di Landauer (1961): Per cancellare un bit di informazione logica in un bagno termico a temperatura T:

Dove:

• k_B \approx 1.38 \times 10^{-23} J/K (costante di Boltzmann).
• T è la temperatura assoluta in Kelvin.
• Q è il calore dissipato nell'ambiente.

Equivalentemente, in termini di entropia:

dove |Δ I| è il numero di bit cancellati.

Esempio con numeri

A temperatura ambiente (T = 300 K):

Per cancellare 1 bit. È pochissimo, ma misurabile con strumenti sensibili.

Entropia prodotta S_{\text{prod}}: è l'entropia che il sistema genera nell'ambiente durante un processo. Se il processo è reversibile, S_{\text{prod}} = 0. Se è irreversibile, S_{\text{prod}} > 0.

Nel protocollo PHS

Appare in §7 (lemma del bound di Landauer pesato). Il lemma dice che il costo fisico di una storia è almeno la somma dei costi di Landauer per ogni step irreversibile. Se una storia alternativa richiede molte cancellazioni logiche, deve dissipare molto calore: questa è una traccia termica.

11. Riepilogo: mappa concetto → sezione del protocollo