Il libro di Will Kurt “Bayesian Statistics the Fun Way” è un’introduzione interessante alle finezze del teorema di Bayes e soprattutto al suo significato pratico. Per chi non si ricordasse la formula del teorema, è questa: $$ P(A|B) = \frac{P(B|A)\cdot P(A)}{P(B)}$$ dove $P(A)$ indica la probabilità di un evento $A$ (chessò, ho il raffreddore) e $P(A|B)$ la probabilità dell’evento $A$ sapendo che c’è stato l’evento $B$ (ho il raffreddore tutte le volte che il giorno prima è piovuto). Se proprio non vi resta in mente la formula, vi svelo un trucchetto: immaginando che tutte le probabilità in gioco siano maggiori di zero – anche perché altrimenti non c’è molto da calcolare… – si può scrivere la formula come $$ P(A|B) \cdot P(B) = P(B|A) \cdot P(A)$$, che è più simmetrica. In ogni caso, noi cerchiamo di aggiornare la probabilità del nostro evento $A$ (che avevamo a priori) una volta che abbiamo una nuova informazione $B$ (che per definizione conosciamo), e lo facciamo rovesciando la logica, cioè sapendo qual è la probabilità di $B$ nota $A$.

Come dicevo, Will Kurt fa un esempio con il Lego, esempio che trovate in questo suo vecchio post e che ora vi racconto. Partiamo con alcuni mattoncini ($1 \times 1$, anche se i pezzi in realtà sono più grandi, ma non so come chiamare l’unità minimale) come in figura:

Abbiamo una superficie $6 \times 10$ di mattoncini di tre colori, che rappresentano il nostro spazio di probabilità: c’è un rettangolo $4 \times 10$ blu, uno $2\times 10$ rosso e uno $3 \times 2$ giallo posato sopra gli altri due (purtroppo con le mie capacità grafiche è difficile mostrarlo bene, ma il fatto che siano leggermente spostati sulla destra dovrebbe essere un indizio). Calcolando le probabilità dello strato di base, abbiamo $P(\rm{blu}) = \frac{2}{3}$ e $P(\rm{rosso}) = \frac{1}{3}$. Chiaramente $P(\rm{blu}) + P(\rm{rosso}) = 1$, visto che lo strato di base ha solo mattoncini blu e rossi.

Ora entrano in scena i mattoncini gialli. È vero che $P(\rm{giallo}) = \frac{1}{10}$, perché ci sono sei mattoncini gialli su 60. Ma nel nostro spazio degli eventi noi non consideriamo l’evento “c’è un mattoncino giallo”, anche perché altrimenti la probabilità totale sarebbe maggiore di 1. Ripeto: gli eventi per noi sono solo quello che si trova sullo strato di base. Consideriamo ora la probabilità condizionata di avere un mattoncino giallo sopra uno blu oppure rosso, indicandola come $P(\rm{giallo\!|\! blu})$ o $P(\rm{giallo\!|\! rosso})$ rispettivamente. Come possiamo calcolare $P(\rm{giallo\!|\! rosso})$? Semplice: separiamo il blu dal rosso e consideriamo solo la parte rossa, come in figura. Abbiamo che l’area rossa è come prima $2\times 10 = 20$, quella gialla è $2\times 2 = 4$, e pertanto $P(\rm{giallo\!|\! rosso}) = \frac{4}{20} = \frac{1}{5}$.

E se invece volessimo calcolare $P(\rm{rosso\!|\! giallo})$? Banale, mi direte. Ci sono sei mattoncini gialli di cui quattro sono sopra il rosso: se dall’alto vediamo un mattoncino giallo sappiamo che la probabilità che sotto ce ne sia uno rosso è $\frac{2}{3}$. Non ci crederete, ma questo è proprio il teorema di Bayes! Intuitivamente, insomma, il teorema non è niente di che, e possiamo anche intuire che il reverendo Bayes lo considerasse talmente ovvio da non scriverne nemmeno. Vediamo ora come tirare fuori la formula mostrata all’inizio, formalizzando la nostra intuizione.

Partiamo calcolando il numero di mattoncini gialli a partire dalla probabilità di trovarli:

$$ \rm{NumGialli} = P(\rm{giallo}) \cdot \rm{TotNum} = \frac{1}{10} \cdot 60 = 6 $$

Cosa vuol dire “Quattro mattoncini gialli sono sul rosso”? Per prima cosa dobbiamo calcolare quanti sono i mattoncini rossi, con una formula simile a quella sopra:

$$ \rm{NumRossi} = P(\rm{rosso}) \cdot \rm{TotNum} = \frac{1}{3} \cdot 60 = 20 $$

Sappiamo poi che il rapporto dei mattoncini gialli sopra quelli rossi è $P(\rm{giallo| rosso})$; moltiplicandolo per il numero dei mattoncini rossi troviamo quanti sono i mattoncini gialli sui rossi:

$$ \rm{NumGialliSuiRossi} = P(\rm{giallo | rosso}) \cdot \rm{NumRossi} = \frac{1}{5} \cdot 20 = 4 $$

Infine dobbiamo calcolare il rapporto tra i mattoncini rossi coperti da quelli gialli e il totale di quelli gialli:

$$ P(\rm{rosso | giallo}) = \frac{\rm{NumGialliSuiRossi}}{\rm{NumGialli}} = \frac{4}{6} = \frac{2}{3} $$

Da qui possiamo usare le tre formule precedenti per scrivere i due termini della frazione usando le probabilità e il numero totale di mattoncini; quest’ultimo fa il piacere di eliminarsi e otteniamo il teorema di Bayes. Diciamocelo, però: la formalizzazione non è così facile da vedere, ed è forse per questo che il teorema rimane spesso piuttosto oscuro, anche se come abbiamo visto non c’è nulla di davvero complicato.

Ultimo aggiornamento: 2025-12-11 14:49

Come sapete, la costante ꬲ ≅ 2,71828… se la gioca alla pari con π nel campionato per il numero che appare più spesso nelle formule matematiche. A differenza del pi greco, però, ꬲ è più facile da gestire, non tanto perché è il limite per $n$ tendente all’infinito dell’espressione $(1 + 1/n)^n$ (la definizione usuale) quanto perché è la somma della serie $ \frac{1}{0!} + \frac{1}{1!} + \frac{1}{2!} + \frac{1}{3!} + \frac{1}{4!} + \cdots $ che ha due vantaggi: è facile da scrivere e converge molto rapidamente. Ci sono anche altre rappresentazioni interessanti di ꬲ, come la forma in frazione continua [1, 2, 1, 1, 4, 1, 1, 6, 1, …] che ha permesso a Eulero di dimostrare che è un numero irrazionale. Non è però immediato ricavare questo sviluppo; in compenso esiste una dimostrazione relativamente semplice, dovuta a Joseph Fourier (sì, quel Fourier) dell’irrazionalità di ꬲ. Eccola qua.

Cominciamo a considerare queste due successioni infinite (o meglio, la collezione di successioni infinite per ogni valore di $n$):

$$ a_n = \frac{1}{n+1} + \frac{1}{(n+1)(n+2)} + \frac{1}{(n+1)(n+2)(n+3)} + \cdots $$
$$ b_n = \frac{1}{n+1} + \frac{1}{(n+1)^2} + \frac{1}{(n+1)^3} + \cdots $$

È immediato vedere che la successione $b_n$ è una progressione geometrica, e quindi il suo valore è $\frac{1}{n}$; d’altra parte, ogni termine di $a_n$ tranne il primo è minore a quello corrispondente di $b_n$ mentre il primo è uguale, e quindi $ 0 < a_n < \frac{1}{n} $. Adesso viene il bello. Prendiamo la definizione di ꬲ come somma infinita e moltiplichiamola per $n!$. I primi $n$ termini del risultato sono tutti interi, mentre la somma di quelli che rimangono, dopo avere tolto $n!$ a denominatore, corrisponde proprio a $a_n$ e quindi è compresa tra 0 e 1. Possiamo riscrivere questo risultato dicendo $$ a_n = n!ꬲ - \textrm{int}(n!ꬲ)$$ La dimostrazione è praticamente terminata. Supponiamo infatti per assurdo che ꬲ sia razionale, e quindi possiamo scrivere $ꬲ = \frac{k}{m}$, con $k$ e $m$ interi. Ma allora $m!ꬲ$ è intero, e dunque $ (m!ꬲ) = \textrm{int}(m!ꬲ)$, il che è impossibile perché sappiamo che tutti gli $a_n$ sono maggiori di zero. QED. Cosa possiamo ricavare da questa dimostrazione? Che Fourier era uno che ne sapeva: a me non sarebbe mai venuto in mente un percorso del genere. Col senno di poi però si può forse intuire cosa sia venuto in mente a Fourier. Il fatto che i termini della successione infinita tendono a zero molto, molto rapidamente ci fa capire che non hai spazio per riuscire a mettere insieme tutti i coefficienti dei denominatori per arrivare a un numeratore multiplo di essi; è un po’ la stessa idea che ebbe Liouville quando costruì esplicitamente il primo numero che si poteva dimostrare essere trascendente. Il bello di questa dimostrazione è comunque che possiamo tranquillamente spiegarla a uno studente liceale, una volta dato per assodato qual è lo sviluppo in serie infinita di ꬲ; non è che siano cose che capitino tutti i giorni!

Ultimo aggiornamento: 2025-12-03 13:32

Nel 1918 József Kürschák dimostrò che la somma di reciproci di due o più numeri consecutivi non può mai essere un intero. Come corollario, l’unico valore intero toccato calcolando la serie armonica $H_n = 1 + 1/2 + 1/3 + 1/4 + …$ è 1. Ci si può però oziosamente chiedere quanto vicino si può arrivare a un intero. John Cook in una successione di post ha mostrato che se ci limitiamo ai numeri da 1 a 100000 abbiamo che $$ \sum_{k=27134}^{73756} \frac{1}{k} \approx 1$$ con un errore dell’ordine di $10^{-11}$, e questa è la migliore approssimazione possibile a 1.

Limitandoci alle porzioni di serie armonica, si arriva rapidamente a un problema: i numeri in virgola mobile non sono abbastanza precisi per fare tutte le addizioni. Fortunatamente abbiamo a nostra disposizione un’approssimazione molto buona: $H_n \approx \log n + \gamma + \frac{1}{2n} – \frac{1}{12n^2}$, dove $\gamma$ è la costante di Eulero-Mascheroni pari a circa 0,57721. (Curiosità: non è noto se sia o no un numero irrazionale, ma tutti credono di sì, anche perché in caso contrario il suo denominatore dovrebbe avere almeno $10^{242080}$ cifre…). Notate come l’approssimazione usata da Cook sia molto più accurata di quella usuale $H_n \approx \log n + \gamma$, per andare più sul sicuro. Cook si è divertito a scrivere un programmino Python per trovare il termine della serie armonica più vicino a un numero (non necessariamente intero) dato, scoprendo per esempio che $H_12366 \approx 9,99996214846655$.

Ma anche questo programma, pur essendo ben fatto, ha dei problemi di arrotondamento se il numero cercato è molto grande. Per esempio dice che se vogliamo arrivare ad approssimare 100 dobbiamo sommare 15092688622113830917200248731913020965388288 termini, e l’errore relativo è dell’ordine di $3 \times 10^{-15}$. Ma usando Mathematica e l’approssimazione $n \approx \rm{exp}(m − \gamma)$, dove $m$ è il numero che vogliamo approssimare e $n$ il numero di termini richiesti, Cook mostra che la vera quantità di termini che dobbiamo sommare è 15092688622113788323693563264538101449859497; insomma i due numeri divergono dalla quattordicesima cifra, il che ha senso visto che siamo ai limiti della precisione dei numeri a 64 bit. Per curiosità, per arrivare a 1000 occorrono un bel po’ di termini, cioè

110611511026604935641074705584421138393028001852577373936470952377218354575172401275457597579044729873152469512963401398362087144972181770571895264066114088968182356842977823764462179821981744448731785408629116321919957856034605877855212667092287520105386027668843119590555646814038787297694678647529533718769401069269427475868793531944696435696745559289326610132208504257721469829210704462876574915362273129090049477919400226313586033

(un numero di 435 cifre). Che possiamo dedurre da tutto questo? Due cose. La prima è che la serie armonica cresce molto lentamente; la seconda è che bisogna sempre sapere qual è il modo migliore per fare un conto, tenendo conto delle limitazioni dei computer…

Ultimo aggiornamento: 2025-11-26 09:24

La successione infinita mostrata qui sopra è stata probabilmente la prima ad essere sommata. Naturalmente l’artefice di questo risultato è stato Archimede, l’unico matematico dell’antichità che non aveva paura di trattare con quantità infinite. Questo risultato gli serviva per quadrare la parabola; chiaramente la dimostrazione formale che fece per la quadratura sfruttò il metodo di esaustione di Eudosso, ma per quanto riguarda la somma il siracusano mostrò la figura qui raffigurata. Il quadrato grande di lato 1 è diviso in quattro parti uguali: una è colorata (e quindi ha area 1/4), due sono bianche, la quarta è divisa a sua volta allo stesso modo, con un quadrato colorato di area 1/16, due quadrati bianchi della stessa area e un quarto quadrato da dividere a sua volta. In definitiva, alla parte colorata corrispondono due parti identiche non colorate, e tutte assieme riempiono il quadrato: pertanto l’area complessiva delle parti colorate è 1/3.

Ok, in realtà non è proprio così: come spiega la voce di Wikipedia, Archimede dimostrò che la somma 3/4 + 3/16 + 3/64 + 3/256 + ⋯ si avvicina quanto si vuole a 1. (Sempre esaustione, claro). Nella sua dimostrazione il quadrato colorato e i due non colorati formano uno gnomone, cioè una figura a L; l’insieme di tutti gli gnomoni riempiono il quadrato.

Ma la cosa forse più bella è che non è necessario usare i quadrati per mostrare che la somma in questione vale 1/3. Come potete vedere nella figura qui a fianco, è possibile prendere un triangolo equilatero e scomporlo in modo tale da avere la stessa suddivisione. Quale delle due scomposizioni è la migliore? Per quanto mi riguarda, la risposta è “entrambe”; ciascuna costruzione è infatti interessante, e visualmente chiara. Il bello di queste dimostrazioni senza parole è proprio questo: capire un risultato senza dover fare conti (in questo caso bisogna saper contare fino a tre, ma direi che ce la possiamo fare…)

La scorsa settimana ho scritto che anche se la struttura logica dell’algoritmo RSA ha cinque parametri, la chiave di cifratura e è quasi sempre settata a 65537, per ragioni di efficienza computazionale e perché non dovrebbe dare problemi di sicurezza (almeno nei casi normali). Ma c’è anche un’altra modifica che è stata fatta negli anni, sempre per ridurre il costo computazionale (che nel caso della crittografia a chiave pubblica è molto più alto che nei sistemi di crittografia simmetrici).

Ricordo che nell’algoritmo RSA viene calcolato φ(n) = (p−1)(q−1), dove p e q sono i numeri primi di partenza, il cui prodotto è n, e φ(n) è la funzione φ di Eulero, cioè quanti sono i numeri minori di n e che non hanno fattori primi in comune con n. Nel nostro caso è facile calcolare il “toziente” (altro nome con cui è nota la funzione φ di Eulero), proprio perché p e q sono primi.

Non è però necessario usare φ(n) per scegliere un d tale che ed = 1 (mod φ(n)). È infatti sufficiente usare la funzione di Carmichael λ(n), definita come il più piccolo intero positivo m tale che a^m ≡ 1 (mod n) per ogni a coprimo con n. Si può dimostrare che λ(n) è un divisore di φ(n), e quindi è un numero più piccolo e pertanto le operazioni di computazione sono più brevi. Ma di quanto lo sono? Di un fattore MCD(p−1, q−1). Chiaramente entrambi i numeri sono pari e quindi c’è un fattore 2, ma si potrebbe sperare che ci sia qualcosa in più. John Cook ha fatto qualche prova, e ha trovato che su 100 coppie di numeri generati casualmente, la mediana del MCM è 2 (quindi in almeno metà dei casi il fattore è effettivamente 2); c’è stato un caso in cui si è arrivati a 2370, mentre il valore medio (poco utile in questo caso, perché a noi serve una sola coppia) è stato 35,44. In pratica, insomma, abbiamo quasi sempre 2 o 4 come fattore comune, In altri termini, se dobbiamo usare spesso una chiave può valer la pena di cercare una coppia di primi per cui λ(n) è effettivamente molto minore di φ(n), altrimenti possiamo far finta di niente.

Ultimo aggiornamento: 2025-11-05 15:33

Come probabilmente sapete, l’algoritmo RSA è uno dei più famosi algoritmi di crittografia a chiave pubblica: questo significa che chiunque può mandarci un messaggio cifrato, usando appunto la chiave pubblica, ma solo noi possiamo decodificarlo. L’algoritmo è tendenzialmente questo:

(a) Scegliamo due numeri primi molto grandi p e q.
(b) Calcoliamo n = pq e φ(n) = (p−1)(q−1).
(c) Scegliamo una chiave di crittazione e che sia un numero relativamente primo rispetto a φ(n). (La lettera “e” sta per “encryption”, se ve lo foste chiesti.)
(d) Calcoliamo la chiave di decrittazione d tale che ed = 1 (mod φ(n)).
(e) Pubblichiamo e e n, mantenendo segreti d, p e q.

La logica della crittografia RSA è che se conosciamo p e q possiamo calcolare “facilmente” n, φ(n) e d, ma non è possibile trovare d senza fattorizzare n, e almeno per il momento la fattorizzazione non è facile da fare, checché si dica delle meraviglie dei computer quantistici.

La cosa buffa è che di solito (pare nel 99,5% dei casi in un sondaggio compiuto da due ricercatori) i punti (b) e (c) si invertono: si sceglie prima e e poi si prendono i due primi, verificando che φ(n) sia primo rispetto a e. E soprattutto non si sceglie e a caso, ma si usa 65537. Come mai? John D. Cook lo spiega esaurientemente: è abbastanza grande perché φ(n) sia relativamente primo (se non lo è, bisogna trovare altri p e q) ed essendo uno più una potenza di 2 si risparmia sui calcoli. C’è addirittura chi ha usato e = 3, ma li si esagera. In realtà, continua Cook, usare un e troppo piccolo può far correre il rischio che qualcuno che ha accesso al computer dove sono stati fatti i conti riesce a trovare alcuni dei bit del numero, e in questo caso ci sono algoritmi più rapidi per decrittare a forza bruta. E scegliere un altro primo? Il punto è che e non è semplicemente una potenza di due più uno, ma un numero primo di Fermat: ne conosciamo solo 5 (3, 7, 17, 257, 65537), e anche se ce ne fosse un altro sarebbe così grande da risultare impraticabile…

Insomma, all’atto pratico abbiamo una semplificazione dell’algoritmo, visto che non scegliamo più e; ma la prossima volta vedremo che ce n’è un’altra.

Scrivendo il post di stamattina mi è venuto in mente un trucchetto che può permettervi di fare bella figura con poca fatica. Riuscite a calcolare a mente quant’è il 60% di 25?

Il calcolo è molto più semplice di quanto sembri a prima vista. Per definizione, una percentuale si calcola moltiplicando i due numeri presenti e dividento per 100, cioè 60×25/100 nel nostro caso. Questo equivale a 25×60/100, che è il 25% di 60. Ma il 25% è un quarto, quindi basta dimezzare due volte 60 e trovare il risultato che è 15. Semplice, no?