640 231 100 91 1003 ...[aria del Don Giovanni di Mozart]
Non ci aspettiamo un comportamento "regolare" da un fenomeno casuale, ecco perché la sequenza 1 1 1 1 1 1 1 1 1 non ci sembra frutto di un fenomeno aleatorio.
Il caso come imprevedibilità
Per il senso comune la casualità è di solito identificata con l'imprevedibilità, la mancanza di leggi o semplicemente schemi di comportamento: per esempio una successione di numeri è casuale se non è chiara quale sia le regola che la genera, o se è chiaro che non vi sia regola alcuna (come vedremo questa percezione si può formalizzare matematicamente).
La lunghezza delle sequenze casuali incide sul loro presunto carattere di casualità: il lancio di una moneta è impredicibile, ma tutti siamo convinti, sulla base dell'esperienza, che lanciandola un gran numero di volte, le "teste" saranno più o meno quante le "croci".
Simulazione del lancio di una moneta
Anticipando sui temi che discuteremo in seguito, esibiamo una simulazione del lancio di monete per confermare il concetto di imprevedibilità nel breve periodo ma di "prevedibilità della tendenza" nel lungo periodo.
Numero di lanci = 0 Numero di "testa" = 0 Numero di "croce" = 0
(Questa simulazione usa un "generatore di numeri a caso" incluso nel browser).
Il "paradosso" della casualità
Lanciando un dado (non truccato) per 10 volte di seguito, le tre possibili sequenze di risultati seguenti sono tutte equiprobabili:
La prima ci pare "sospetta", ma in realtà, ha la stessa probabilità di comparire delle altre due, che è 1/610, fra tutte le 610 combinazioni possibili.
Lanciare il dado 10 volte di seguito o lanciare 10 dadi contemporaneamente dà luogo allo stesso fenomeno casuale!!!
"Prima o poi quel numero deve uscire"
Se le lotterie non sono truccate, ogni volta che si estrae un numero si ha la stessa probabilità per ciascun esito dell'estrazione: non esistono numeri "ritardatari"!!! In teoria, un numero potrebbe non essere mai più estratto.
Ogni volta che si estrae un numero al lotto la probabilità che esca 1, 2, 3, ... o 90 è la stessa in ciascun caso indipendentemente dalle estrazioni precedenti: ciascuna estrazione "ignora" l'esito delle precedenti (a parità di condizioni iniziali: tutte le palline nell'urna!).
Spesso ciò si esprime dicendo: i numeri non hanno memoria.
Esempi familiari di sequenze casuali
lancio di dadi, lotterie e altri giochi d'azzardo
popolazione: tassi di crescita, mortalità, etc.
temperatura, umidità, pioggia, etc.
quotazioni in borsa
tempi di attesa di una coda
tempistiche di eventi sismici
movimento di particelle in un liquido o gas (moto browniano)
(e molto altro)
Distribuzione di una sequenza casuale
0
1
2
3
4
5
6
7
8
9
La guerra (persa)
contro il caso
Il pensiero scientifico classico non ammette il caso
Fin dai suoi albori, il pensiero scientifico e razionale ha cercato di annullare la casualità, imponendo un ordine alle cose del mondo: un esempio tipico è la comprensione delle traiettorie dei corpi celesti in modo da prevederne le posizioni.
Babilonesi, Egizi e Greci, con apice nell'epoca ellenistica, riuscivano a predire le posizioni degli astri con diverse finalità (raccolti, oroscopi, speculazioni, etc.).
Traiettorie annodate ma non casuali
Il sistema tolemaico, per quanto ponesse erroneamente la Terra al centro del Cosmo, riusciva comunque a offrire previsioni accettabili grazie alla teoria degli epicicli, che spiegava anche fenomeni apparentemente irregolari come il movimento retrogrado di Marte.
L'immagine del mondo classica
La simmetria è una delle caratteristiche della bellezza nel mondo antico: la linearità, o circolarità delle forme, e l'eliminazione di qualsiasi imperfezione o difetto, indice di una visione del mondo che rifiutava il caso.
Il discobolo di Mirone (V sec. a.C.)
Il caso come combinazione e azzardo
Gerolamo CardanoBlaise PascalJacob Bernoulli
(1501-1576)(1623-1662)(1655-1705)
La legge fisica non lascia nulla al caso
F = m dv FG = G m×M
dt r2
Le equazioni della Fisica da Newton in poi sono "equazioni differenziali", cioè le loro incognite non rappresentano numeri, come nel caso delle equazioni algebriche, ma funzioni cioè traiettorie di oggetti (particelle, corpi, pianeti).
Isaac Newton (1643-1727)
Le funzioni spiegano il mondo
Nel caso più semplice possiamo pensare a una funzione come a un processo che dato un numero x in input restituisce un numero y in output in modo che uno stesso input non possa dar luogo a due output diversi.
Una funzione è quindi un oggetto deterministico: l'input determina univocamente l'output.
Esempi e controesempi di funzioni
Sono esempi di funzioni:
y = 4x(x-1)
y = cos x
y = area del cerchio di raggio x
NON sono esempi di funzioni:
y = numero il cui quadrato è x
y = numero il cui coseno è x
y = numero di lati di un poligono di area x
Modi di rappresentare una funzione
-x2/2
f(x) = 2
Tabulazione Grafici
Le funzioni rappresentano traiettorie
La traiettoria di un corpo nella fisica di Newton ha come input il tempo e come output la posizione: al variare della posizione e della velocità iniziale, la traiettoria cambia "linearmente" con le variazioni dei dati iniziali!
0 80
L'immagine del mondo nella prima modernità
Giovanni Paolo Pannini (1691-1765)
La fontana di Trevi.
La quintessenza del determinismo
"Una intelligenza che, a un dato istante, conosca tutte le forze che animano
la natura, la posizione
rispettiva degli enti che la compongono, se fosse così vasta da sottoporre questi dati all’analisi
[matematica], abbraccerebbe nella medesima formula i movimenti dei più grandi corpi dell’universo, e
quelli dei più effimeri atomi.
Nulla sarebbe incerto per essa, e sia l’avvenire sia il passato sarebbero
presente ai suoi occhi"
Pierre Simon de Laplace (1749-1827)
Il caso come errore e ignoranza
Thomas BayesP.S. de LaplaceCarl Friedrich Gauss
(1701-1761)(1749-1827)(1777-1855)
Prime battute d'arresto...
Charles Darwin Ludwig Boltzmann Louis Bachelier
(1809-1882) (1844-1906) (1870-1946)
L'immagine del mondo nel tardo '800
Vincent Van Gogh (1853-1890) Cielo stellato
... e il capolinea del determinismo
Werner Heisenberg (1901-1976) fondò la Fisica Quantistica sul "principio di indeterminazione": non è possibile conoscere contemporaneamente e in modo preciso le condizioni iniziali delle equazioni del moto (posizione e velocità)!
La fisica quantistica descrive le particelle in termini di "ampiezze di probabilità" e non di posizione e velocità contemporaneamente misurabili con precisione voluta.
Teoria della probabilità
Andrej Andreevič MarkovPaul LévyAndrej Kolmogorov
(1856-1922)(1886-1971)(1903-1987)
Il caso è ormai "accreditato" presso gli scienziati
"Quindi sembra che Einstein fosse doppiamente in errore quando diceva che Dio non gioca a dadi. Non soltanto Dio gioca sicuramente a dadi, ma spesso ci confonde lanciandoli dove non possiamo vedere [allude ai buchi neri]"
Stephen Hawkings (1942-)
L'immagine del mondo oggi
Jackson Pollock (1912-1956) - Number 20
Calcoli a caso...
L'esperimento di Buffon
Nel 1733 Georges-Louis Lecler conte di Buffon (1707-1788) propose un problema di "matematica dilettevole": qual è la probabilità che un ago, lanciato su un pavimento tracciato con linee parallele, cada di traverso una linea (dati lunghezza dell'ago e distanza fra le linee). Se la lunghezza dell'ago e la distanza delle linee coincidono, la probabilità è 2/π e questo offre una stima probabilistica del pi greco. Una versione equivalente ma più semplice segue nella prossima slide.
Calcolo "casuale" del pi greco
N : NC = Area quadrato : Area cerchio
⇒ Area cerchio = Area quadrato × NC / N
⇒ πr2 = (2r)2 × NC / N
⇒ π = 4 × NC / N
Integrali definiti (= aree)
-44
f(x) =
=
Metodo di Monte Carlo e i computer
Enrico Fermi John von NeumannStanisław Ulam
(1901-1954) (1903-1957) (1909-1984)
Cos'è un computer?
Un dispositivo (solitamente elettronico) che consente di:
Rappresentare numeri e altri dati con precisione finita e fissata e memorizzare sequenze di tali dati
Rappresentare codifiche di algoritmi (=particolari tipi di funzioni) che prendono in input i dati rappresentati e ne forniscono in output altri
Eseguire gli algoritmi codificati sui dati disponibili.
Architettura di von Neumann
Sia i dati che i programmi sono memorizzati nell'unità di memoria sotto forma di numeri: la CPU decide se trattarli come dati o eseguirli in quanto programmi.
I computer non possono fare tutto...
"Chiunque consideri metodi aritmetici per generare cifre a caso vive, naturalmente, nel peccato. Infatti, come è stato notato molte volte, non ci sono cose come i numeri a caso, ci sono solo metodi per produrre numeri a caso e una procedura rigorosamente aritmetica non è ovviamente un tale metodo."
Von Neumann e l'EDVAC (1951-1961)
Casualità e incomprimibilità
Una definizione problematica
Esistono numerosi test statistici per appurare il carattere aleatorio di una successione, che tipicamente operano a livello di distribuzione e non della successione ordinata dei singoli valori: questi test sono utili per studiare la distribuzione della successione in quanto variabile aleatoria, ma non si possono usare per definire cosa sia la casualità di una successione.
In effetti, definire in modo univoco cosa voglia dire che una successione infinita xn di numeri sia casuale, è compito arduo: fra le numerose definizioni di casualità qui riporteremo la principale, dovuta al genio di Kolmogorov, "l'Euclide della probabilità".
La definizione "da scommettitore" di successione casuale
Richard von Mises (1883-1953) ha tentato di definire cosa sia la casualità di una successione in termini di giochi d'azzardo: in sostanza, egli afferma, una successione numerica è casuale se non è possibile alterarne la statistica eliminandone una sotto-successione.
Cioè scommettere "con un sistema" non migliora, nel lungo periodo, le possibilità di vincere in un gioco completamente casuale.
Esempi sulla definizione di von Mises
Esempio: se una successione di 0 e 1 è realmente casuale e uniformemente distribuita, non si incrementa la probabilità di estrarre degli 0 o degli 1 scegliendo, per esempio, soltanto gli elementi di indice pari.
Controesempio: se consideriamo la successione 0 1 0 1 0 1 0 ... cioè definita come x2n = 0 e x2n+1 = 1, e se le togliamo la sotto-successione x2n troviamo la successione 1 1 1 1 1 ... che ovviamente fa sempre estrarre un 1. Quindi la successione di partenza non è casuale.
Si pone il problema di definire che tipi di "estrazione" sono leciti nella definizione e in ogni caso la definizione non è soddisfacente dal punto di vista della teoria della probabilità.
L'idea di Kolmogorov e Chaitin
A.N. Kolmogorov
Grigory Chaitin (1947-)
Hanno dato una definizione del concetto di successione casuale che implica proprio l'uso dei computer, o meglio dei programmi per computer: questa concezione ha aperto un intero filone di ricerca, la teoria algoritmica della complessità.
Programmi per computer
Abbiamo detto che un computer è una macchina che esegue algoritmi (= calcola funzioni) e che codifica queste funzioni nella propria memoria: queste codifiche si chiamano programmi.
Un programma è quindi una sequenza di simboli che viene codificata con una sequenza di numeri nella memoria del computer per essere eseguito: dunque è anche esso una sequenza numerica, del pari delle sequenze che, per esempio, consente di generare.
Sequenze finite casuali
La casualità di Kolmogorov e Chaitin è definita prima per successioni finite di simboli, per esempio successioni numeriche finite (in questo caso l'alfabeto sono i possibili numeri della successione).
L'idea è che una successione finita è di complessità alta, cioè se non è possibile convogliare la sua informazione con meno simboli di quelli richiesti a scrivere la successione.
In sostanza, una sequenzax0, x1, ..., xN è di complessità alta se non è possibile generarla con un programma per computer che abbia lunghezza minore di N.
La maggior parte delle successioni finite sono di complessità alta...
Successioni casuali
Nel caso di successioni infinite, Kolmogorov identifica il loro carattere di casualità con il loro carattere di incomprimibilità: una successione xn è incomprimibile se inizia con una successione finita di complessità alta.
In realtà questa definizione non è ben posta ed è stata resa rigorosa da Chaitin introducendo una particolare classe di algoritmi, che definire qui ci porterebbe troppo lontano: l'idea è tuttavia quella di considerare successioni i cui primi termini non siano esprimibili in modo più sintetico della successione stessa.
Simulare la casualità
Usare (di nuovo) le funzioni
Una sequenza pseudo-casuale è una successione numerica ottenuta da una stessa funzione cui ogni volta viene fornito come input l'output del passo precedente: si tratta quindi di "mappe iterate" o "equazioni alle differenze".
I valori xn devono "essere" (meglio "somigliare") a valori uniformemente distribuiti in un certo intervallo (per esempio fra 0 e 1 se sono numeri decimali o fra 0 e un certo N fissato se sono interi).
I valori xn devono "essere" (meglio "comportarsi come se fossero") mutuamente indipendenti.
La (2) non è possibile realmente soddisfarla: va intesa nel senso che il periodo della successione pseudo-casuale deve essere il più grande possibile.
Esempio: metodo di von Neumann (middle-square)
Si parte da un numero con un numero fisso di cifre, per esempio 4: la funzione da iterare prende il quadrato del numero (che ha quindi 8 cifre) e torna le 4 cifre centrali. E così via.
x0 = x1 =
Il metodo non è molto efficace...
Esempio: congruenze lineari
Si parte da un intero, e si applica una funzione lineare "modulo" un numero fissato: cioè si calcola, dato xn il successivo valore come
xn+1 = resto della divisione di axn+b per m
Il difficile è la scelta dei parametri a, b, m
x0 = a = b = m = x1 =
Proprietà delle congruenze lineari
In un generatore a congruenze lineari xn+1 ≡ axn+b (mod m) si ha che
Se MCD(b,m)=1, ogni fattore primo p di m divide anche a-1 e se 4 divide m allora divide anche a-1 il periodo del generatore è m.
Se m è primo, b=0, x0&neq;0, m divide am-1-1 ma non divide ak-1-1 per k=1,2,..., m-2 allora il periodo del generatore è il massimo possibile.
Si possono caratterizzare in generale i generatori di periodo massimo (usando la teoria di Gauss delle congruenze lineari).
Difetti delle congruenze lineari
x0 = a = b = m =
Altre tecniche
Le tecniche di teoria dei numeri consentono di ottenere generatori molto più affidabili, come per esempio quelli basati sulle tecniche di Marsaglia.
Una categoria importante è quella dei generatori "crittograficamente sicuri", basati su algoritmi espressamente progettati per rendere sicure le applicazioni alla cifratura dei dati (tipicamente basate sulla difficoltà di fattorizzare numeri molto grandi in numeri primi).
Funzione logistica
Iterare una funzione, come si fa nei generatori di numeri pseudo-casuali, può dare luogo a un comportamento caotico, che non è apparentemente possibile comprimere.
Consideriamo la funzione logistica
xn+1 = 4xn(1 - xn)
Si tratta di una semplice funzione quadratica, che origina come modello di evoluzione di una popolazione isolata.
Pierre François Verhulst (1804-1849)
Iterare la funzione logistica
x0 = N =
Caos deterministico...
Anche una semplice funzione come quella logistica, se iterata, produce del caos, cioè traiettorie che non sono periodiche e che oscillano in modo apparentemente casuale.
Per questo motivo tecniche analoghe possono essere effettivamente utilizzate per generare sequenze di numeri casuali: tuttavia caoticità non vuol dire casualità e in particolare le traiettorie della mappa logistica tendono ad addensarsi intorno a un "attrattore" con una distribuzione probabilistica chiamata distribuzione beta.
È in ogni caso sorprendente che si possa generare un comportamento caotico e sensibile ai dati iniziali (effetto farfalla) con una semplice equazione di secondo grado!!!
Alcune applicazioni
Impieghi delle simulazioni
Abbiamo visto come poter simulare successioni di numeri pseudo-casuali consenta di effettuare simulazioni su un computer.
Le simulazioni sono fondamentali nell'industria moderna, perché consentono di svolgere calcoli su un oggetto, o su un processo, prima di metterlo effettivamente in piedi e quindi di studiare qualcosa che ancora non c'è con un notevole abbattimento dei costi.
Sono utilizzate in economia, finanza, informatica (per esempio per simulare il comportamento di utenti nel testare i programmi), biologia, ecologia, meteorologia (con tutti i problemi legati all'effetto farfalla e al caos) e in fisica, soprattutto nella fisica delle particelle elementari, ma non solo.
Titoli in borsa
x0 = N =
Machine learning
I numeri casuali servono ad addestrare gli algoritmi adattativi, come le reti neurali e gli algoritmi genetici
Una rete neurale è un modello matematico ipersemplificato del cervello umano che può essere usato per calcolare funzioni qualsiasi: per farlo, anziché contenere la codifica della funzione, la rete "scopre" un algoritmo "nascosto" e questo avviene addestrando la rete su dati di prova proposti secondo combinazioni casuali.
Un algoritmo genetico è un modello matematico di calcolo ispirato alla teoria dell'evoluzione, in cui i si cerca di risolvere un problema partendo da una soluzione casuale che viene fatta evolvere in modo da adattarsi al problema, e rimescolandone casualmente la struttura.
Rete neurale minimale: il perceptrone
Quando si esercita, se sbaglia a classificare usa i valori 0/1 dei dati di input per correggere una stringa di numeri associata a ciascun possibile output. Esempio:
Autenticazione forte
Oltre ai soliti username e password, per autenticare un utente a un sistema informatico in modo "forte", è possibile assegnargli un dispositivo che generi una sequenza pseudocasuale.
Se l'algoritmo e il seme della sequenza è anche noto al server del sistema, questo può generare la stessa sequenza e verificare la password "usa e getta" inserita dall'utente che l'ha letta sul dispositivo.
In questo modo la sicurezza delle credenziali non è legata solo a "ciò che si sa" (username e password) ma anche a "ciò che si ha" (il dispositivo OTP o una app su smartphone che generi la sequenza casuale associata dal server all'identità dell'utente).
Sicurezza informatica: lato utente
Praticamente tutte le nostre transazioni su Internet (bancarie, facebook, twitter, etc.) sono protette da sistemi di "crittografia a chiave pubblica": quando sull'indirizzo del sito il prefisso "https" il server del sito e il nostro computer comunicano in modo "sicuro".
La sicurezza riposa sulla difficoltà di fattorizzare numeri primi molto grandi, che sono utilizzati per produrre le chiavi pubbliche/private che garantiscono la segretezza dei dati.
In questi algoritmi e processi è spesso fondamentale poter generare numeri a caso, anche molto alti: senza questa possibilità non si potrebbero mettere in piedi le infrastrutture di sicurezza che reggono tutto il traffico economico di Internet!!!
Sicurezza informatica: lato hacker
La sicurezza delle connessioni "TCP/IP" di rete usate per collegarsi a Internet si basa sulla non predicibilità di alcuni numeri con i quali sono etichettate le "transazioni" sulla rete: la sicurezza di una qualsiasi sessione web è legata a questa impredicibilità.
Se gli hacker sanno che linguaggio di programmazione, o che infrastruttura, è utilizzata per una certa applicazione web, e conoscono l'algoritmo del generatore di numeri pseudo-casuali di quel linguaggio, potrebbero sfruttarne eventuali vulnerabilità (è successo con il linguaggio PHP diffuso per i siti Web).
Fattorizzazione di numeri primi
Un metodo dovuto a John Pollard (1941-) consente di usare un generatore pseudo-casuale per fattorizzare numeri primi, iterando la funzione f(x) = x2 + 1 (mod n) dove n è il numero da fattorizzare.
Non appena la sequenza diviene periodica (cioè si ripete) si termina con un successo o un fallimento: nel primo caso 1 < MCD(n, xi-xj) < n è il divisore, se invece il MCD è n l'algoritmo fallisce.
Fin dai suoi albori, il pensiero scientifico e razionale ha cercato di annullare la casualità, imponendo un ordine alle cose del mondo: un esempio tipico è la comprensione delle traiettorie dei corpi celesti in modo da prevederne le posizioni.
La simmetria è una delle caratteristiche della bellezza nel mondo antico: la linearità, o circolarità delle forme, e l'eliminazione di qualsiasi imperfezione o difetto, indice di una visione del mondo che rifiutava il caso.
Giovanni Paolo Pannini (1691-1765)
"Una intelligenza che, a un dato istante, conosca tutte le forze che animano
la natura, la posizione
rispettiva degli enti che la compongono, se fosse così vasta da sottoporre questi dati all’analisi
[matematica], abbraccerebbe nella medesima formula i movimenti dei più grandi corpi dell’universo, e
quelli dei più effimeri atomi.
Nulla sarebbe incerto per essa, e sia l’avvenire sia il passato sarebbero
presente ai suoi occhi"
Werner Heisenberg (1901-1976) fondò la Fisica Quantistica sul "principio di indeterminazione": non è possibile conoscere contemporaneamente e in modo preciso le condizioni iniziali delle equazioni del moto (posizione e velocità)!
Nel 1733 Georges-Louis Lecler conte di Buffon (1707-1788) propose un problema di "matematica dilettevole": qual è la probabilità che un ago, lanciato su un pavimento tracciato con linee parallele, cada di traverso una linea (dati lunghezza dell'ago e distanza fra le linee). Se la lunghezza dell'ago e la distanza delle linee coincidono, la probabilità è 
"Chiunque consideri metodi aritmetici per generare cifre a caso vive, naturalmente, nel peccato. Infatti, come è stato notato molte volte, non ci sono cose come i numeri a caso, ci sono solo metodi per produrre numeri a caso e una procedura rigorosamente aritmetica non è ovviamente un tale metodo."
Richard von Mises (1883-1953) ha tentato di definire cosa sia la casualità di una successione in termini di giochi d'azzardo: in sostanza, egli afferma, una successione numerica è casuale se non è possibile alterarne la statistica eliminandone una sotto-successione.
Iterare una funzione, come si fa nei generatori di numeri pseudo-casuali, può dare luogo a un comportamento caotico, che non è apparentemente possibile comprimere.