SUPERCAT.DEV

Negli articoli 35 e 36 abbiamo iniziato a osservare una random walk come un processo che evolve passo dopo passo.

Ora aggiungiamo una nuova domanda:

quando decidiamo di smettere di osservare il processo?

Sembra una domanda innocua, ma esistono due tipi molto diversi di regole.

Una regola può dire:

mi fermo la prima volta che il saldo raggiunge +3

Questa decisione può essere presa realmente mentre il processo si svolge.

Un'altra può dire:

mi fermo nell'ultima volta in cui il saldo sarà zero prima del passo 10

Questa seconda frase definisce certamente un istante della traiettoria, ma per riconoscerlo mentre siamo lì dovremmo conoscere ciò che accadrà dopo.

La distinzione è il cuore dei tempi di arresto.

La regola operativa

Indichiamo con:

S_0, S_1, S_2, ...

la random walk osservata passo dopo passo.

Un tempo casuale T è un tempo di arresto se, arrivati al passo n, possiamo stabilire se:

$$ T = n $$

usando soltanto ciò che abbiamo osservato fino a quel momento.

Possiamo usare:

il passo corrente
il saldo corrente
tutti i passi precedenti
tutta la storia già osservata

ma non possiamo usare:

un risultato futuro
un massimo che verrà raggiunto più avanti
l'ultima visita a uno stato, se non sappiamo ancora se torneremo

Durrett formalizza questa idea dicendo che la decisione al tempo n deve dipendere dall'informazione disponibile al tempo n.

Nel corpo di questo articolo ci basta questa lettura operativa; non abbiamo bisogno del formalismo delle sigma-algebre.

Primo esempio: raggiungere una soglia

flowchart TD
    O["Osserva Sₙ"] --> C{"|Sₙ| = 3?"}
    C -->|No| N["Osserva il passo successivo"]
    N --> O
    C -->|Sì| T["T = n: arresto"]

La decisione usa soltanto l'informazione disponibile al tempo n: non richiede di conoscere il futuro.

Consideriamo ancora la random walk semplice simmetrica:

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

Definiamo:

T = primo n tale che |S_n| = 3

cioè ci fermiamo appena il saldo raggiunge +3 oppure -3.

Questa è una regola utilizzabile in tempo reale.

Al passo n conosciamo S_n.

Se:

$$ |S_n| < 3 $$

continuiamo.

Se:

$$ |S_n| = 3 $$

ci fermiamo.

Non serve conoscere nessun passo futuro.

Questo tipo di tempo viene chiamato hitting time, tempo di primo raggiungimento di un insieme di stati.

Nel nostro caso l'insieme è:

{-3,+3}

Quando possiamo fermarci?

Partendo da zero, per arrivare a +3 o -3 servono almeno tre passi.

Quindi:

$$ T \ge 3 $$

Inoltre la parità della random walk impone:

$$ T = 3, 5, 7, 9, ... $$

Non possiamo raggiungere una posizione dispari dopo un numero pari di passi.

Fermarsi al passo 3

Per avere T=3 dobbiamo fare:

+++ 

oppure:

---

Sono 2 sequenze su 2^3=8, quindi:

P(T=3)
=
2/8
=
1/4
=
25%

Se dopo tre passi non ci siamo fermati

La probabilità di non avere ancora raggiunto ±3 è:

$$ 1 - 1/4 = 3/4 $$

Se siamo ancora in gioco dopo il terzo passo, il saldo può essere soltanto:

-1 oppure +1

Da uno di questi due stati, nei due passi successivi c'è probabilità 1/4 di raggiungere la barriera dalla stessa parte:

+1 -> +2 -> +3

oppure:

-1 -> -2 -> -3

Perciò:

P(T=5)
=
(3/4)(1/4)
=
3/16
=
18,75%

Lo stesso ragionamento si ripete ogni due passi finché la soglia non viene raggiunta:

$$ \begin{gathered} P(T=3) = 1/4 \ P(T=5) = 3/16 \ P(T=7) = 9/64 \ P(T=9) = 27/256 \ P(T=11) = 81/1024 \end{gathered} $$

In generale, per k=1,2,3,...:

$$ P(T=2k+1) = (3/4)^{k-1} \cdot 1/4 $$

Quanto spesso abbiamo già finito entro 11 passi?

Per non aver raggiunto ±3 entro il passo 11 dobbiamo sopravvivere a cinque occasioni successive di arresto:

P(T>11)
=
(3/4)^5
=
243/1024
≈
23,73046875%

Quindi:

P(T<=11)
=
1 - 243/1024
=
781/1024
≈
76,26953125%

Questo è un calcolo sulla prima volta in cui tocchiamo la soglia.

Non va confuso con:

$$ P(|S_{11}|=3) $$

che guarda soltanto la posizione finale al passo 11 e dimentica se la traiettoria aveva già toccato ±3 in precedenza.

È la stessa differenza introdotta nell'articolo 35 fra endpoint e traiettoria.

Il tempo medio di primo raggiungimento

La distribuzione appena trovata permette anche di calcolare il valore atteso.

Se K conta quale delle occasioni di arresto è quella vincente, allora:

$$ K = 1,2,3,... $$

con probabilità di successo 1/4 a ogni occasione.

Quindi K ha media:

$$ E[K]=4 $$

Il tempo corrispondente è:

$$ T=2K+1 $$

perciò:

E[T]
=
2E[K]+1
=
9

Per la soglia ±3, quindi, il primo raggiungimento avviene in media dopo 9 passi.

Questo numero non significa che la soglia debba essere raggiunta entro il nono passo. Come abbiamo già visto per le distribuzioni geometriche, un valore atteso non è una scadenza.

Un tempo fissato è un tempo di arresto

La regola:

$$ T = 10 $$

è banalmente un tempo di arresto.

Al passo 10 sappiamo che dobbiamo fermarci; prima sappiamo che non dobbiamo farlo.

Possiamo anche combinare una soglia con un orizzonte massimo:

T = min(
    primo raggiungimento di ±3,
    11)

La regola significa:

fermati appena raggiungi ±3;
se non succede prima, fermati comunque al passo 11

Anche questa decisione utilizza soltanto informazione disponibile.

Questa versione limitata sarà importante nell'articolo successivo, perché un orizzonte massimo rende molto più semplice controllare rigorosamente che cosa succede al valore atteso quando introduciamo una regola di stop.

Una regola che sembra simile ma non è un tempo di arresto

Consideriamo invece:

L = ultima volta, entro il passo 10,
    in cui il saldo è zero

L è perfettamente definito dopo che abbiamo visto l'intera traiettoria.

Ma non è un tempo di arresto.

Supponiamo che i primi quattro passi siano:

+1, -1, +1, -1

La storia osservata è:

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

Al passo 4 siamo a zero.

Ora immaginiamo due futuri diversi, entrambi compatibili con esattamente la stessa storia fino al passo 4.

Primo futuro:

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

Dopo il passo 4 non torniamo più a zero, quindi:

$$ L=4 $$

Secondo futuro:

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

Qui torniamo a zero al passo 8, quindi:

$$ L=8 $$

Al passo 4 l'informazione disponibile è identica nei due casi.

Eppure per una traiettoria dovremmo decidere:

fermati: L=4

mentre per l'altra:

non fermarti: L non è ancora arrivato

La differenza è contenuta esclusivamente nel futuro.

Per questo L non è un tempo di arresto.

Un tempo casuale non è automaticamente un tempo di arresto

Questa distinzione è importante.

Un tempo di arresto è certamente una variabile casuale che assume valori temporali, ma non vale il contrario.

Possiamo definire, dopo aver osservato una traiettoria completa:

il momento dell'ultimo zero
il momento del massimo finale
il passo precedente alla più lunga serie futura di +1

Sono tutti tempi casuali ben definiti.

Ma per fermarci realmente in uno di quei momenti dovremmo conoscere il futuro.

La parola arresto contiene quindi un requisito informativo, non soltanto temporale.

Il legame con la rovina del giocatore

Nell'articolo 36 abbiamo chiesto quale barriera venga raggiunta per prima:

0 oppure B

Possiamo ora dare un nome al tempo in cui la partita termina:

T
=
primo n tale che S_n appartiene a {0,B}

Questo T è un hitting time e quindi un tempo di arresto.

La probabilità di assorbimento calcolata nell'articolo precedente riguardava dunque già implicitamente una regola di arresto, anche se non avevamo ancora introdotto il termine.

Verifica con C#

Per il nostro esempio possiamo mantenere separati tre compiti:

1. calcolare esattamente la distribuzione del primo hit di ±3;
2. simulare una regola di stop che legge soltanto tempo e saldo correnti;
3. mostrare con due traiettorie perché l'ultimo zero entro un orizzonte usa il futuro.

Uno snippet minimale per una regola valida è:

static bool SogliaRaggiunta(
    int saldo,
    int soglia)
{
    if (soglia <= 0)
        throw new ArgumentOutOfRangeException(nameof(soglia));

    return Math.Abs(saldo) >= soglia;
}

Dopo ogni passo possiamo chiamare questa funzione usando soltanto il saldo appena osservato.

Il file standalone associato all'articolo verifica inoltre esattamente:

P(T=3)   = 1/4
P(T=5)   = 3/16
P(T=7)   = 9/64
P(T=9)   = 27/256
P(T=11)  = 81/1024
P(T<=11) = 781/1024
E[T]     = 9

Lo standalone C# associato a questo articolo è:

TempiArresto.cs

La simulazione usa un seed fisso ed è soltanto una verifica empirica del comportamento già descritto matematicamente.

Il punto operativo

Un tempo di arresto non significa semplicemente:

un momento casuale in cui qualcosa accade

Significa:

un momento casuale che possiamo riconoscere
quando arriva,
con le informazioni disponibili fino a quel momento

Il primo raggiungimento di una soglia soddisfa questa regola.

L'ultima visita a zero prima di un orizzonte futuro no.

Questa distinzione ci permette finalmente di formulare in modo corretto una delle domande più frequenti nei giochi e nei processi casuali:

se scelgo una regola intelligente per fermarmi,
posso cambiare il valore atteso?

È la domanda dell'articolo 38.