backup del Post

Che cos’è il caso?

Se vi presentassi la successione di cifre binarie 10101 01010 10101 01010 10101 01010 e vi dicessi che è casuale, immagino che mi guardereste con la faccia di chi dice “non vorrai mica prendermi in giro, vero?”. Se invece vi dessi la successione 10111 00111 01111 01000 00011 01011 forse vi stupireste un po’ dei gruppetti di 0 e di 1 consecutivi ma probabilmente vi fidereste della mia parola… e naturalmente fareste male. Anche la seconda successione, infatti, è costruita in maniera tutto fuorché casuale. Ho preso la parte dopo la virgola dello sviluppo decimale di pi greco (14159 26535 89793…) e ho scritto 1 quando la cifra corrispondente è dispari e 0 quando è pari. In definitiva ci vuole un po’ più di fatica per trovare la regola, ma anche la seconda successione è perfettamente deterministica e non casuale. Ma allora, che cos’è una successione casuale?

La risposta è molto semplice: boh. No, non è proprio così: però è vero che non è molto semplice trovare una definizione di successione casuale. Cominciamo con la definizione frequentista legata alla probabilità: una successione è casuale se in ciascun suo elemento ogni elemento ha la stessa probabilità di apparire. Questa definizione è la formalizzazione di quello che si fa quando lanciamo una moneta o un dado e ci segniamo man mano tutti i risultati, e detta così sembra assolutamente logica: peccato che non funzioni affatto in pratica, perché entrambe le successioni qui sopra hanno esattamente la stessa probabilità di essere generate. Questo è un paradosso piuttosto noto, che deriva dal fatto che mentre a prima vista la successione “zero uno” ha una sua logica ben precisa quella “pi greco” è indistinguibile da tante altre successioni e quindi non spicca.

Per ovviare a questo problema i matematici hanno tirato fuori dal cappello il concetto di numero normale: non solo la singola cifra della successione deve apparire con probabilità casuale, ma lo stesso deve capitare se leggiamo la successione a coppie di cifre, a terne, e così via. Si può facilmente dimostrare che “quasi tutte” le successioni di numeri sono normali, e quindi immaginare che le successioni che non ci sembrano casuali verranno subito sgamate. In effetti la prima successione non passa il test: la coppia di cifre 00, oppure quella 11, non appariranno mai e pertanto il numero non è casuale. Purtroppo però, almeno a quanto ne sappiamo, la successione di cifre decimali di pi greco passa tutti i test di normalità, e pertanto anche questo secondo criterio fallisce… beh, diciamo fallisce in teoria. Se abbiamo bisogno di numeri (pseudo)casuali per una risoluzione numerica di un problema, non possiamo usare la prima successione perché rischiamo troppo di incocciare in un bias, ma la seconda è con ogni probabilità valida e funzionante. Notato però che non ho espresso certezze in nessuno dei casi?

D’altra parte, tutta la teoria ossimorica degli algoritmi di generazione di numeri casuali nasce per trovare una funzione che snoccioli una numeri senza che noi possiamo indovinare quale sarà il prossimo. Questa tra l’altro è proprio la base della definizione di entropia data da Claude Shannon quando definì la teoria dell’informazione. Come stabilire quanta informazione è presente nella lingua inglese, o in quella italiana? Sicuramente ce n’è, altrimenti sapremmo già cosa qualcuno dice prima ancora che inizi a parlare. Altrettanto certamente non è il massimo esprimibile in linea teorica avendo a disposizione ventisei lettere: per esempio dopo la q possiamo supporre con ogni probabilità che troveremo una u. Calcolare però con esattezza l’entropia di una lingua è praticamente impossibile, e lo era ancora di più alla fine degli anni 1940 quando i computer erano per la quasi totalità esseri umani che facevano i conti con carta e penna. Shannon non si perse d’animo, e per stimare quanti bit di informazione per lettera contenesse la lingua inglese ideò un semplice esperimento. Prese un testo e dei volontari, lesse loro una lettera per volta e chiese di indovinare la successiva, con risultati che non sono poi tanto lontani da quelli calcolati oggi con i Big Data. Ecco dunque una nuova definizione di casualità, come impredicibilità. Una successione è casuale se pur conoscendo un certo numero di termini precedenti non abbiamo nessuna idea di quello che seguirà; la parte più interessante è che il campo di azione di questa definizione può essere ampliato per calcolare quanto una successione non è casuale, e confrontare due successioni per capire quale è più casuale di un’altra. L’entropia in senso informatico è una nozione potentissima.

Abbiamo però ancora qualche problema. Se noi guardiamo la prima delle successioni iniziali ci accorgiamo subito che la sua entropia è bassa, ma se guardiamo la seconda la risposta cambia a seconda se abbiamo o no una conoscenza esterna: non solo la successione dei numeri ma anche la regola che l’ha creata. Si è così arrivati negli anni ’60 a una definizione ancora diversa di casualità, sviluppata in modo indipendente da Chaitin e Kolmogorov. (La guerra fredda portò anche a questa duplicazione di sforzi, visto che era difficile sapere cosa facevano “gli altri” anche in campi prettamente teorici come la matematica). Di nuovo, l’origine di questa nuova definizione è informatica. Una successione si può definire casuale se il più breve programma che la genera deve contenere al suo interno tutta la successione. Non importa quale sia il linguaggio di programmazione usato: in questo caso non ci importa tanto il valore esatto quanto una stima, e pertanto un qualsiasi linguaggio equivalente a una macchina di Turing universale va bene. Finalmente abbiamo una risposta diversa alla nostra domanda iniziale: entrambe le successioni possono essere definite in maniera breve, e quindi non sono casuali. Questi sono risultati molto profondi nell’informatica teorica, tra l’altro, e soprattutto Chaitin ci ha costruito su una notevole teoria. L’unico guaio pratico è che è impraticabile scoprire se una successione è davvero casuale: bisognerebbe provare tutti i programmi “corti” e accertarci che nessuno tiri fuori i nostri dati di partenza. Ma perlomeno in linea di principio una strada c’è.

Alla fine però non vale la pena di preoccuparsi troppo: se una successione sembra casuale allora possiamo usarla con tranquillità… a meno che non siamo nel campo della crittografia. Se dobbiamo comporre qualche messaggio cifrato dobbiamo essere il più certi possibile che il testo in chiaro venga modificato in modo da soddisfare tutti i test di casualità. Ogni struttura che rimane, per quanto piccola, è un punto di attacco per l’analisi crittografica: le falle di Enigma furono l’impossibilità che una lettera venisse trasformata in sé stessa e la necessità di inviare ogni mattina i nuovi settaggi. Poi non venite a dire che il caso non è importante.