SUPERCAT.DEV

Finora abbiamo quasi sempre posto una domanda del tipo:

qual è la probabilità che X valga questo numero?

Con una random walk cambiamo prospettiva.

Immaginiamo un gioco puramente matematico nel quale ogni turno produce uno dei due risultati:

+1 con probabilità 1/2
-1 con probabilità 1/2

Il valore atteso di un singolo turno è zero. Ma dopo il primo turno continuiamo a giocare, poi ancora, e osserviamo il saldo cambiare passo dopo passo.

La domanda non è più soltanto:

dove sarò dopo 10 passi?

ma anche:

quale percorso avrò seguito per arrivarci?

Questa distinzione fra posizione a un tempo fissato e intera traiettoria è il primo nuovo concetto di questa parte della serie. Una traiettoria è la sequenza completa degli stati attraversati nel tempo; una singola traiettoria osservata o simulata viene anche chiamata realizzazione del processo.

Dal singolo passo al processo

flowchart LR
    S0["S₀ = 0"] -->|+1| S1["S₁ = 1"]
    S1 -->|+1| S2["S₂ = 2"]
    S2 -->|-1| S3["S₃ = 1"]
    S3 -->|+1| S4["S₄ = 2"]
    S4 -->|-1| S5["S₅ = 1"]

Ogni arco rappresenta un incremento; ogni nodo mostra il saldo raggiunto dopo quel passo.

Indichiamo con:

X_i

il risultato del passo i:

X_i = +1 oppure -1

Nel modello simmetrico:

$$ \begin{gathered} P(X_i=+1)=1/2 \ P(X_i=-1)=1/2 \end{gathered} $$

Assumiamo inoltre che i passi siano indipendenti.

Dopo n passi il saldo è:

S_n
=
X_1 + X_2 + ... + X_n

La successione:

S_0, S_1, S_2, ...

con:

$$ S_0 = 0 $$

è una random walk unidimensionale semplice e simmetrica.

Una possibile traiettoria di dieci passi potrebbe essere:

Quella traiettoria termina in 0.

Ma non è la random walk. È soltanto una delle 2^10 sequenze possibili di dieci passi.

Dove possiamo essere dopo n passi?

Dopo un passo possiamo essere soltanto in:

-1, +1

Dopo due passi:

-2, 0, +2

Dopo tre:

-3, -1, +1, +3

Compare subito un vincolo di parità.

Dopo un numero pari di passi possiamo trovarci soltanto in posizioni pari; dopo un numero dispari di passi soltanto in posizioni dispari.

Inoltre:

$$ -n \le S_n \le n $$

Quindi chiedere, per esempio:

$$ P(S_{10} = 3) $$

non richiede nessun calcolo sofisticato:

$$ P(S_{10} = 3)=0 $$

perché 3 non è raggiungibile dopo un numero pari di passi.

Questo è un evento impossibile dentro un modello valido, non un errore di input.

Il collegamento con la binomiale

Chiamiamo:

H_n

il numero di passi +1 fra i primi n.

Nel cammino simmetrico:

H_n ~ Binomiale(n, 1/2)

Se ci sono H_n passi positivi, quelli negativi sono:

$$ n - H_n $$

Il saldo finale è quindi:

S_n
=
H_n - (n-H_n)

ossia:

S_n
=
2H_n - n

Questa relazione permette di riutilizzare direttamente la binomiale dell'articolo 10.

Se vogliamo terminare in una posizione s, dobbiamo avere:

$$ s = 2h - n $$

quindi:

$$ h = (n+s)/2 $$

Se questo numero non è intero oppure cade fuori da 0..n, la posizione è impossibile.

Altrimenti:

$$ P(S_n=s) = C(n,(n+s)/2) / 2^n $$

Questa è la distribuzione esatta della posizione al tempo n per la random walk semplice simmetrica.

Dieci passi: distribuzione completa

Per n=10 abbiamo:

posizione   cammini       probabilità
-10              1        0,09765625%
 -8             10        0,97656250%
 -6             45        4,39453125%
 -4            120       11,71875000%
 -2            210       20,50781250%
  0            252       24,60937500%
 +2            210       20,50781250%
 +4            120       11,71875000%
 +6             45        4,39453125%
 +8             10        0,97656250%
+10              1        0,09765625%

La somma dei conteggi è:

1+10+45+120+210+252+210+120+45+10+1
=
1024
=
2^10

come deve essere.

Tornare esattamente a zero

Per finire in 0 dopo dieci passi servono cinque passi positivi e cinque negativi:

P(S_10=0)
=
C(10,5)/2^10
=
252/1024
=
63/256
=
24,609375%

Quasi un quarto delle sequenze di dieci passi termina esattamente al punto di partenza.

Ma attenzione: questo non significa che quasi un quarto delle traiettorie rimanga vicino allo zero durante tutto il percorso.

Una traiettoria può allontanarsi molto e poi tornare.

Terminare abbastanza lontano

Per esempio:

$$ |S_{10}| \ge 6 $$

significa terminare in:

-10, -8, -6, +6, +8, +10

I cammini favorevoli sono:

2(1+10+45)
=
112

quindi:

P(|S_10|>=6)
=
112/1024
=
7/64
=
10,9375%

Valore atteso: zero non significa immobilità

Per un singolo passo:

E[X_i]
=
(+1)(1/2)+(-1)(1/2)
=
0

Per linearità del valore atteso:

E[S_n]
=
E[X_1]+...+E[X_n]
=
0

Quindi:

$$ E[S_n]=0 $$

per ogni n.

Questo però non significa:

$$ S_n = 0 $$

né significa che la traiettoria resti vicina allo zero.

Il valore atteso descrive il centro della distribuzione delle possibili posizioni finali.

La dispersione cresce con il tempo

Per ogni passo simmetrico:

$$ X_i^2 = 1 $$

quindi:

$$ E[X_i^2]=1 $$

ed essendo E[X_i]=0:

$$ \operatorname{Var}(X_i)=1 $$

I passi sono indipendenti, perciò le varianze si sommano:

Var(S_n)
=
Var(X_1)+...+Var(X_n)
=
n

La deviazione standard è quindi:

sigma(S_n)=sqrt(n)

Per esempio, dopo 100 passi:

E[S_100]=0
sigma(S_100)=10

La posizione media resta zero, ma la scala naturale delle fluttuazioni cresce come la radice quadrata del numero di passi.

Questo richiama l'intuizione dell'articolo 26 sul teorema centrale del limite, ma qui il punto importante è un altro: stiamo osservando un processo nel tempo, non soltanto una somma finale.

Distribuzione finale e traiettoria non sono la stessa cosa

Consideriamo due sequenze che terminano entrambe in 0 dopo dieci passi.

La prima può oscillare poco:

0 -> 1 -> 0 -> 1 -> 0 -> 1 -> 0 -> 1 -> 0 -> 1 -> 0

La seconda può arrivare prima a +5 e poi tornare:

0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 4 -> 3 -> 2 -> 1 -> 0

Entrambe hanno:

$$ S_{10}=0 $$

ma hanno storie molto diverse.

Se chiediamo soltanto:

$$ P(S_{10}=0) $$

queste differenze non contano.

Se invece chiediamo:

la traiettoria ha mai raggiunto +5?
quando ha toccato per la prima volta +5?
ha raggiunto +5 prima di -3?

la sola distribuzione finale non basta più.

Sono proprio queste domande che aprono il resto del percorso sui processi casuali.

E se il passo positivo non ha probabilità 1/2?

Possiamo generalizzare il modello:

$$ \begin{gathered} P(X_i=+1)=p \ P(X_i=-1)=1-p \end{gathered} $$

Il numero di passi positivi resta binomiale:

H_n ~ Binomiale(n,p)

quindi, per una posizione raggiungibile s:

$$ P(S_n=s) = C(n,(n+s)/2) p^{(n+s)/2} (1-p)^{(n-s)/2} $$

Il valore atteso di un passo diventa:

E[X_i]
=
p-(1-p)
=
2p-1

perciò:

$$ E[S_n] = n(2p-1) $$

La varianza di un passo è:

$$ \operatorname{Var}(X_i)=4p(1-p) $$

quindi:

Var(S_n)=4np(1-p)

Quando p=1/2 ritroviamo:

$$ \begin{gathered} E[S_n]=0 \ \operatorname{Var}(S_n)=n \end{gathered} $$

Questa generalizzazione sarà importante quando introdurremo barriere e probabilità di rovina.

Verifica con C#

Lo standalone C# associato a questo articolo è:

RandomWalk.cs

Per il cammino simmetrico non serve Monte Carlo per conoscere la distribuzione a tempo fissato: possiamo calcolarla esattamente con coefficienti binomiali.

Uno snippet essenziale è:

static BigInteger ConteggioCammini(
    int passi,
    int posizione)
{
    if (passi < 0)
        throw new ArgumentOutOfRangeException(nameof(passi));

    if (posizione < -passi || posizione > passi)
        return BigInteger.Zero;

    if (((passi + posizione) & 1) != 0)
        return BigInteger.Zero;

    int positivi = (passi + posizione) / 2;
    return Combinazioni(passi, positivi);
}

Il file standalone associato all'articolo:

calcola esattamente la distribuzione per n=10
verifica che i conteggi sommino a 2^10
verifica E[S_10]=0
verifica Var(S_10)=10
verifica P(S_10=0)=63/256
verifica P(|S_10|>=6)=7/64
genera inoltre una singola traiettoria con seed fisso

La simulazione della traiettoria non serve a stimare i valori appena calcolati: serve a mostrare visivamente la differenza fra una realizzazione e la distribuzione di tutte le realizzazioni possibili.

Il punto operativo

Una random walk ci costringe a distinguere due oggetti:

S_n
= posizione casuale a un tempo fissato

e:

S_0, S_1, ..., S_n
= intera traiettoria casuale

La prima può essere studiata con strumenti già noti, come la binomiale.

La seconda apre domande nuove:

quale soglia viene raggiunta per prima?
quanto tempo serve per raggiungerla?
che cosa succede se ci fermiamo quando la raggiungiamo?

Nel prossimo articolo aggiungeremo due barriere al cammino e studieremo una delle domande classiche della probabilità:

partendo da un capitale finito, qual è la probabilità di raggiungere un obiettivo prima di arrivare a zero?

È il problema della rovina del giocatore.