SUPERCAT.DEV

Nel corso della serie abbiamo risolto problemi di probabilità in modi diversi.

A volte bastava una formula:

P(almeno un 6 in quattro lanci)
=
1-(5/6)^4

A volte abbiamo contato direttamente tutti gli esiti:

2.598.960 mani di poker

A volte abbiamo usato una simulazione Monte Carlo come controllo empirico.

E in problemi più complessi, come il Craps, abbiamo costruito un modello a stati prima ancora di scegliere come calcolarlo.

L’ultima domanda del percorso introduttivo è quindi metodologica:

Quando conviene usare una formula, quando enumerare tutto e quando simulare?

La risposta non dipende da quale metodo sembri più sofisticato.

Dipende da ciò che sappiamo del problema e dal costo necessario per ottenere una risposta affidabile.

Tre strumenti diversi

Possiamo distinguere tre approcci principali.

Il calcolo esatto analitico usa formule e ragionamento matematico.

L'enumerazione completa visita tutti gli esiti possibili e li conta.

La simulazione Monte Carlo genera soltanto un campione casuale degli esiti e usa le frequenze osservate per stimare le probabilità. Qui campione significa semplicemente l'insieme finito delle prove simulate che stiamo osservando: 10.000 simulazioni sono un campione di 10.000 risultati prodotti dal modello.

Tutti e tre possono essere utili.

Ma non producono lo stesso tipo di risposta.

Calcolo esatto: quando la struttura è chiara

Consideriamo il primo 6 di un dado.

La probabilità è:

$$ 1/6 $$

Non avrebbe senso lanciare virtualmente un dado un milione di volte per "scoprire" un valore che possiamo ottenere esattamente con:

1 caso favorevole
su
6 casi equiprobabili

La formula ci dà una risposta esatta e, soprattutto, spiega perché vale.

Un altro esempio esatto

Per due assi consecutivi da un mazzo:

$$ P = 4/52 \cdot 3/51 = 1/221 $$

Anche qui il calcolo è breve e preciso.

Una simulazione potrebbe produrre valori leggermente differenti a seconda del seed e del numero di esperimenti.

Ma nessuna di queste stime è più informativa di:

$$ 1/221 $$

quando il rapporto esatto è già disponibile.

Enumerazione completa: esatta ma computazionale

Nel poker a cinque carte abbiamo fatto qualcosa di diverso.

Il numero di mani possibili è:

C(52,5)
=
2.598.960

È un numero troppo grande per un conteggio manuale, ma abbastanza piccolo per un programma.

Abbiamo quindi potuto generare ogni mano una sola volta, classificarla e contare le categorie.

L'enumerazione completa è un metodo esatto.

Non contiene errore statistico.

Enumerazione e formula possono verificarsi a vicenda

Per il full avevamo la formula:

13
·
C(4,3)
·
12
·
C(4,2)
=
3.744

L'enumerazione completa ha trovato:

3.744

full.

I due metodi sono indipendenti nel modo in cui arrivano al risultato.

Quando coincidono, abbiamo una verifica molto forte.

Questo è spesso uno degli usi migliori dell'enumerazione: controllare un ragionamento combinatorio.

Il brute force può scoprire una congettura, ma non dimostrarla

C'è un quarto uso del computer che vale la pena distinguere dai tre strumenti precedenti: esplorare un problema quando non abbiamo ancora una formula.

Possiamo generare tutti i casi piccoli, osservare i conteggi e cercare una regolarità. Questa è una forma di matematica sperimentale.

Per esempio, un programma potrebbe produrre:

n = 1 -> 1 oggetto
n = 2 -> 2 oggetti
n = 3 -> 4 oggetti
n = 4 -> 8 oggetti
n = 5 -> 16 oggetti

La sequenza suggerisce immediatamente:

$$ 2^{n-1}. $$

Ma cinque casi verificati non dimostrano che la formula valga per ogni n.

La formula suggerita dai dati è una congettura: una proposizione che sembra plausibile e che ora dobbiamo giustificare oppure smentire.

Il ciclo corretto è:

brute force su casi piccoli
-> pattern osservato
-> congettura
-> dimostrazione o derivazione indipendente
-> nuovo controllo computazionale

Hopkins dedica volutamente parte di Hands-On Combinatorics a problemi nei quali bisogna cercare in uno spazio combinatorio, tornare indietro e usare brute force prima che emerga una struttura. Il punto non è sostituire la prova con il computer, ma usare il calcolo come strumento di scoperta.

Questo completa la gerarchia dei metodi: il computer può calcolare, enumerare, simulare e anche aiutare a formulare la domanda matematica giusta.

Quando l'enumerazione diventa impraticabile

Dieci lanci di un dado hanno:

6^10
=
60.466.176

sequenze.

Sono ancora enumerabili con un programma adeguato, ma il costo è già molto superiore rispetto a usare direttamente la binomiale.

Con venti lanci avremmo:

$$ 6^{20} \approx 3,66 \cdot 10^{15} $$

sequenze.

Enumerarle tutte non è più una strategia ragionevole per una domanda semplice come:

quanti 6 ottengo?

quando disponiamo già della formula binomiale.

Perché si chiama Monte Carlo?

Il nome non nasce nei casinò, anche se li richiama volutamente.

Kucharski ricostruisce la storia di Stanislaw Ulam, John von Neumann e Nicholas Metropolis a Los Alamos. Davanti a problemi troppo difficili da affrontare direttamente con le equazioni disponibili, l'idea fu di simulare ripetutamente eventi casuali con il computer e studiarne gli esiti.

Metropolis propose il nome metodo Monte Carlo, richiamando il gioco d'azzardo e uno zio di Ulam noto come giocatore.

La lezione metodologica è ancora attuale:

problema troppo complesso da risolvere direttamente
-> costruisci un modello corretto
-> genera molti casi secondo quel modello
-> usa le frequenze per stimare la quantità cercata

La potenza del metodo non deriva dal fatto che il caso "risolva" il problema. Deriva dal fatto che possiamo trasformare una quantità difficile da calcolare in una quantità che sappiamo campionare e misurare.

Fonte di contesto storico: Adam Kucharski, La scommessa perfetta, cap. 3, "Da Los Alamos a Monte Carlo".

Monte Carlo: campionare invece di visitare tutto

La simulazione Monte Carlo sceglie un'altra strada.

Invece di visitare tutti gli esiti, ne genera N casuali e stima:

P(evento)
≈
successi / N

Se simuliamo un milione di lanci di un dado e osserviamo una frequenza vicina a:

$$ 1/6 $$

abbiamo una buona stima.

Ma è importante usare la parola:

stima

Il risultato dipende dal campione casuale.

Monte Carlo non diventa esatto aumentando N

Aumentare il numero di simulazioni riduce l'errore tipico, ma non trasforma una simulazione finita in un calcolo esatto.

Con:

$$ N = 1.000 $$

otteniamo una frequenza.

Con:

$$ N = 1.000.000 $$

otteniamo normalmente una frequenza più stabile.

Ma entrambe rimangono osservazioni casuali.

La probabilità teorica del dado resta:

$$ 1/6 $$

non la frequenza generata da una particolare esecuzione.

Quanto diminuisce l'errore?

Una prova di Bernoulli è una prova che, rispetto alla domanda scelta, classifichiamo soltanto come successo o insuccesso. Per un evento Bernoulli con probabilità teorica p, la frequenza osservata su N prove ha deviazione standard:

sqrt(
    p(1-p)
    ------
      N
)

Questa quantità viene spesso chiamata errore standard della frequenza stimata.

Il punto fondamentale è la dipendenza da:

1/sqrt(N)

L'errore tipico non diminuisce come 1/N, ma molto più lentamente.

Quadruplicare il lavoro dimezza l'errore

Se passiamo da:

$$ N $$

a:

4N

allora:

1/sqrt(4N)
=
1/(2sqrt(N))

L'errore standard si dimezza.

Per ridurre l'errore di un fattore 10 dobbiamo aumentare il numero di simulazioni di circa un fattore:

100

Questa è una delle caratteristiche più importanti da conoscere quando si usa Monte Carlo.

Esempio con P(6)=1/6

Per un singolo 6:

$$ p = 1/6 $$

Con:

$$ N = 1.000 $$

l'errore standard della frequenza è circa:

1,18 punti percentuali

Con:

$$ N = 10.000 $$

scende a circa:

0,373 punti percentuali

Con:

$$ N = 1.000.000 $$

è circa:

0,0373 punti percentuali

Il miglioramento è reale, ma richiede una crescita molto forte del numero di esperimenti.

Un intervallo indicativo

Per campioni sufficientemente grandi e probabilità non troppo vicine a 0 o 1, una regola statistica comune usa circa:

±1,96 · errore standard

per costruire un intervallo normale approssimativo al 95%.

Per p=1/6 e un milione di prove, la semilarghezza è circa:

0,0730 punti percentuali

Questo non significa che ogni simulazione debba cadere necessariamente in quell'intervallo.

È una proprietà probabilistica dell'intero procedimento di campionamento.

L'intervallo normale è inoltre un'approssimazione, non una nuova formula esatta.

Gli eventi rari sono più difficili da simulare

Consideriamo una scala colore nel poker a cinque carte.

La probabilità esatta è:

40 / 2.598.960
≈
0,001539%

In:

100.000

mani simulate, il numero medio teorico di scale colore è soltanto circa:

1,54

Potremmo quindi osservare:

0
1
2
3

eventi senza che la simulazione abbia necessariamente un problema.

La frequenza relativa sarebbe molto instabile.

Un milione di mani non è enorme per un evento raro

Con:

1.000.000

mani simulate, il numero medio teorico di scale colore è circa:

15,39

È ancora un conteggio piccolo.

Una differenza di poche occorrenze cambia sensibilmente la stima percentuale.

Nel nostro caso l'enumerazione completa delle:

2.598.960

mani è quindi nettamente preferibile: costa poco e dà il risultato esatto.

Il paradosso pratico

A volte una simulazione di un milione di casi sembra "enorme".

Ma se lo spazio completo contiene soltanto circa 2,6 milioni di esiti, enumerare tutto può essere più sensato.

Il numero di simulazioni, preso da solo, non dice se Monte Carlo sia una buona scelta.

Dobbiamo confrontarlo con:

dimensione dello spazio
costo per valutare un esito
rarità dell'evento
precisione richiesta

Quando Monte Carlo diventa davvero utile

Monte Carlo è particolarmente interessante quando lo spazio è enorme, la struttura esatta è difficile da contare, il processo contiene molti stati e regole oppure vogliamo esplorare una distribuzione complessa senza enumerare ogni percorso possibile.

Un simulatore di gioco completo può avere:

stati
decisioni
carte residue
regole opzionali
strategie
sequenze di eventi

che rendono l'enumerazione esaustiva molto costosa.

In quel contesto la simulazione può diventare uno strumento pratico fondamentale.

Prima di simulare, proviamo a raggruppare gli esiti

Uno spazio con centinaia o migliaia di risultati non è automaticamente un problema da Monte Carlo.

Nel capitolo su Arkham Horror di Teaching Mathematics Through Games, un'abilità richiede di pescare 2 token distinti da un sacchetto di 17 e scegliere quello più favorevole. Gli esiti non ordinati sono:

$$ \binom{17}{2}=136. $$

Un'altra situazione pesca 3 token:

$$ \binom{17}{3}=680. $$

680 casi sono più di quanti vorremmo calcolare a mano uno per uno, ma sono ancora perfettamente enumerabili. Soprattutto, il capitolo mostra che possiamo raggruppare gli esiti secondo la proprietà che determina il risultato, invece di trattarli tutti separatamente.

L'ordine mentale corretto è quindi:

quanto è grande lo spazio?
-> quali esiti sono davvero equivalenti per la domanda?
-> posso raggrupparli con combinatoria o simmetrie?
-> solo dopo: serve Monte Carlo?

Una buona classificazione può trasformare un problema apparentemente enorme in pochi casi distinti.

Un modello corretto può essere ancora incompleto

C'è un secondo insegnamento utile nello stesso esempio.

Se confrontiamo due abilità guardando soltanto la probabilità di superare un test, possiamo ottenere un calcolo perfettamente corretto. Ma alcune abilità evitano anche effetti negativi aggiuntivi prodotti da certi token. Se quel costo non compare nella quantità che stiamo misurando, il confronto risponde a una domanda più stretta di quella che ci interessava davvero.

In altre parole:

$$ \boxed{ \text{calcolo corretto} \not\Rightarrow \text{modello completo} } $$

Prima di discutere precisione numerica dobbiamo quindi chiederci anche:

che cosa stiamo ottimizzando?
quali costi o benefici abbiamo escluso?
la variabile scelta rappresenta davvero la decisione?

Questo problema è diverso da un errore di implementazione: il programma può essere corretto e convergere al valore esatto del modello scelto, mentre il modello misura soltanto una parte del fenomeno.

Fonte di contesto didattico: Aaron Montgomery, “Probability Problems from the Arkham Horror Card Game”, in Mindy Capaldi (ed.), Teaching Mathematics Through Games, cap. 6.

Ma il modello deve essere corretto

Una simulazione non corregge un modello sbagliato.

Se nel Texas Hold'em contiamo 10 out quando in realtà due sono duplicati o non puliti, simulare cento milioni di mani non risolve l'errore concettuale.

Se nel blackjack rimettiamo accidentalmente nel sabot una carta che dovrebbe essere già uscita, il programma può convergere magnificamente verso la probabilità sbagliata.

Monte Carlo riduce l'errore casuale della stima.

Non elimina gli errori di modello o di implementazione.

Prima il modello, poi il metodo numerico

Questa è probabilmente la regola più importante dell'intera serie.

Prima dobbiamo decidere:

che cosa costituisce un esito
quali informazioni sono note
quali eventi sono favorevoli
se le prove sono indipendenti
se c'è reinserimento
quali stati esistono

Solo dopo scegliamo:

formula
enumerazione
simulazione

Un metodo numerico sofisticato applicato a uno spazio campionario sbagliato produce soltanto una risposta sbagliata con più cifre decimali.

Monte Carlo e MCMC non sono la stessa cosa

Nello stesso capitolo Kucharski segue un'evoluzione successiva: combinare il campionamento Monte Carlo con una catena di Markov, facendo dipendere ogni nuova configurazione dallo stato corrente invece di ricominciare ogni volta da una nuova ipotesi indipendente.

Nasce così la famiglia dei metodi Markov Chain Monte Carlo, o MCMC.

Per questa serie è importante non fondere i due concetti:

Qui continuiamo a parlare del primo caso. MCMC richiede un articolo separato perché introduce domande nuove: come progettare la catena, quanto a lungo farla evolvere e quando i campioni ottenuti sono sufficientemente informativi.

Il collegamento diventerà più naturale dopo gli articoli sulle catene di Markov.

Fonte di contesto: Adam Kucharski, La scommessa perfetta, cap. 3.

Formula esatta e simulazione insieme

Monte Carlo è comunque molto utile come controllo indipendente.

Nel Craps abbiamo ottenuto:

P(win Pass Line)
=
244/495
≈
49,2929%

Possiamo poi simulare un milione di Pass Line complete.

Se la frequenza empirica risulta vicina al 49,3%, abbiamo un controllo ragionevole del modello.

Se invece ottenessimo una differenza enorme, non dovremmo mediare formula e simulazione.

Dovremmo cercare un errore nel codice o nella modellazione.

Quando un risultato esatto è disponibile, esso rimane il riferimento.

La riproducibilità e il seed

Una simulazione usa un generatore pseudo-casuale.

Per rendere riproducibili test ed esempi didattici possiamo usare un seed fisso:

var random =
    new Random(42);

Questo permette di rieseguire lo stesso esperimento in condizioni compatibili.

È molto utile per:

test
debug
documentazione
confronto tra versioni

Ma non rende la simulazione "più casuale" o "più esatta".

Serve alla riproducibilità.

Un seed solo non misura l'incertezza

Se eseguiamo una simulazione con seed 42, il risultato da solo non ci dice quanto sia stabile la stima.

Possiamo aumentare N, calcolare un errore standard teorico quando appropriato oppure eseguire repliche indipendenti con seed diversi per osservare la variabilità tra simulazioni.

Il seed fisso è un ottimo strumento ingegneristico, ma non sostituisce l'analisi statistica dell'errore.

Enumerazione completa e memoria

Enumerare non significa necessariamente memorizzare tutti gli esiti.

Nel poker abbiamo potuto generare una mano, classificarla, incrementare un contatore, scartarla e passare alla successiva.

Quindi il costo può essere principalmente tempo di CPU, senza richiedere memoria proporzionale al numero totale di esiti.

Questo rende possibili enumerazioni che sembrerebbero troppo grandi se immaginassimo di conservare ogni combinazione in una lista.

Un criterio pratico

Quando affrontiamo un nuovo problema possiamo seguire questa sequenza mentale.

Prima chiediamoci:

Posso derivare un risultato esatto con una formula semplice?

Se sì, usiamo quella.

Altrimenti:

Posso enumerare tutto in un tempo ragionevole?

Se sì, l'enumerazione ci dà ancora un risultato esatto.

Se entrambe le strade sono impraticabili:

Posso simulare correttamente il processo e quantificare l'incertezza della stima?

A quel punto Monte Carlo diventa una scelta naturale.

Un esempio C#: tre modi per P(6)

Lo standalone C# associato a questo articolo è:

EsattoEnumerazioneMonteCarlo.cs

Per un dado il calcolo analitico è:

double esatta =
    1.0 / 6.0;

L'enumerazione completa è:

int favorevoli = 0;

for (int faccia = 1;
     faccia <= 6;
     faccia++)
{
    if (faccia == 6)
        favorevoli++;
}

double enumerata =
    favorevoli / 6.0;

La simulazione è:

var random =
    new Random(42);

int successi = 0;
const int prove = 1_000_000;

for (int i = 0; i < prove; i++)
{
    if (random.Next(1, 7) == 6)
        successi++;
}

double simulata =
    (double)successi / prove;

I primi due metodi restituiscono teoricamente lo stesso valore esatto.

Il terzo produce una stima casuale vicina.

Calcoliamo anche l'errore standard

static double ErroreStandardBernoulli(
    double probabilita,
    long prove)
{
    if (probabilita < 0.0 ||
        probabilita > 1.0)
    {
        throw new ArgumentOutOfRangeException(
            nameof(probabilita));
    }

    if (prove <= 0)
        throw new ArgumentOutOfRangeException(nameof(prove));

    return
        Math.Sqrt(
            probabilita
            *
            (1.0 - probabilita)
            /
            prove);
}

Per:

$$ \begin{gathered} p = 1/6 \ N = 1.000.000 \end{gathered} $$

otteniamo un errore standard di circa:

0,0003727

come probabilità, cioè:

0,03727 punti percentuali

Un confronto automatico

Possiamo scrivere un programma che stampi:

risultato esatto
risultato enumerato
risultato simulato
errore assoluto della simulazione
errore standard teorico

Questo è didatticamente molto più utile che mostrare soltanto una percentuale Monte Carlo.

Ci ricorda che una stima deve essere letta insieme alla sua precisione.

Non confondiamo precisione numerica e accuratezza del modello

Un programma può stampare:

0,166742000000

con dodici cifre decimali.

Ma quelle cifre non implicano che conosciamo la probabilità con dodici cifre di accuratezza.

La formattazione numerica non crea informazione.

Una simulazione da poche migliaia di prove può avere molte cifre stampate ma pochissime cifre statisticamente significative.

Allo stesso modo, una formula esatta implementata con double può mostrare un piccolo errore di rappresentazione floating-point pur provenendo da un ragionamento matematico esatto.

Dobbiamo distinguere:

esattezza matematica
errore statistico
errore floating-point
errore di modello

Sono problemi diversi.

Quando usare BigInteger

Nei conteggi combinatori abbiamo spesso usato:

BigInteger

perché numeri come:

$$ 52! $$

superano rapidamente i tipi interi standard.

Una buona strategia è mantenere il conteggio esatto con BigInteger e convertire a double soltanto quando vogliamo visualizzare una probabilità decimale.

Questo evita di introdurre approssimazioni prima del necessario.

Quando una frazione è più informativa di un decimale

Nel Craps:

$$ 244/495 $$

ci dice esattamente quale probabilità abbiamo derivato.

Il decimale:

49,292929...

è utile per l'intuizione.

Quando possibile è spesso utile conservare:

forma esatta
+
forma decimale

anziché sostituire subito il rapporto con una lunga sequenza di cifre.

Monte Carlo e convergenza

La legge dei grandi numeri ci dice, in condizioni appropriate, che la frequenza osservata converge verso la probabilità teorica quando il numero di prove cresce.

Ma "converge" non significa:

si avvicina a ogni nuova prova

Una simulazione può essere più vicina al valore esatto a 100.000 prove che a 200.000 e poi tornare più vicina a 1.000.000.

La convergenza è un comportamento asintotico, non un percorso monotono.

Il valore di una simulazione cresce quando sappiamo cosa confrontare

Monte Carlo è spesso particolarmente utile quando conosciamo già alcuni risultati esatti.

Possiamo usare casi semplici come test del simulatore:

dado -> 1/6
due assi -> 1/221
Pass Line -> 244/495

Se il motore di simulazione riproduce correttamente questi casi entro l'errore atteso, aumenta la nostra fiducia prima di applicarlo a scenari più complessi privi di soluzione semplice.

Questa è una pratica molto utile anche nello sviluppo software scientifico.

Una gerarchia utile

Possiamo riassumere così.

Se una formula esatta è semplice:

preferisci la formula

Se la formula è difficile ma lo spazio è gestibile:

enumera tutto

Se lo spazio è enorme o il processo troppo complesso:

usa Monte Carlo

ma misura l'incertezza e valida il simulatore su casi noti.

In molti progetti reali i tre metodi convivono.

Non sono concorrenti: sono strumenti complementari.

Il punto pratico

Il metodo migliore non è quello con più codice o più casualità.

È quello che fornisce la risposta necessaria con il minor numero di assunzioni e con un errore ben compreso.

Il calcolo esatto è preferibile quando la struttura matematica è accessibile.

L'enumerazione completa è preziosa quando lo spazio può essere visitato integralmente e vogliamo un risultato esatto o una verifica indipendente.

Il Monte Carlo diventa fondamentale quando lo spazio o il processo sono troppo grandi, ma produce una stima e richiede attenzione a:

numero di prove
errore standard
eventi rari
seed e riproducibilità
correttezza del modello

La serie è partita da una domanda elementare:

Quanti esiti devo contare?

e ha attraversato spazi campionari, combinatoria, probabilità condizionata, distribuzioni, valore atteso, rischio, giochi di carte e processi a stati.

Il filo conduttore è rimasto lo stesso:

prima modellare correttamente il problema, poi scegliere come calcolarlo.

È questa la competenza più importante da portare fuori dai singoli giochi e applicare a qualunque problema di probabilità finita.