Problema dell’arresto ottimale: quando conviene fermarsi?

Una decisione da prendere: che fare?

È il pomeriggio del 24 dicembre e, come ogni anno, vi siete presi all’ultimo secondo con i  regali di Natale. Vi resta un pomeriggio per acquistare l’ultimo regalo, il più importante, quello per il vostro/ la vostra partner. La situazione è questa: vi recate nel solito centro commerciale stracolmo di persone e dovete scegliere in quale dei 50 negozi fermarvi e comprare il regalo. Quello che potete fare è entrare nel negozio, dare un’occhiata veloce alle idee regalo più adeguate e valutare se fermarvi ad acquistare l’articolo o uscire e proseguire con la ricerca. Supponiamo che, sia per la folla sia per il poco tempo a disposizione, una volta che avete scartato un negozio non ci possiate più tornare. Quello che può sembrare un banale problema da ritardatari in realtà nasconde un problema matematico molto complesso. In matematica il problema dell’arresto ottimale si occupa di scegliere l’esatto momento in cui effettuare un’azione per rendere massima una nostra richiesta (ha moltissime applicazioni in vari ambiti che spiegheremo più avanti). Ed è proprio il nostro caso: l’obiettivo è trovare il momento giusto per fermarsi in un negozio sapendo che ovviamente stiamo cercando l’articolo “migliore”, che trovi un giusto compromesso tra spesa e felicità di chi lo riceverà. Al termine di una complicata dimostrazione algebrica risulta che la strategia migliore è la seguente: chiamato n il numero di scelte disponibili, si scarta il primo 37% di queste, si prosegue e si sceglie la prima opzione che è migliore della migliore di quelle precedentemente scartate. In tal modo abbiamo il 37% circa di probabilità di effettuare la scelta migliore. Nel nostro caso, sarebbero stati da scartare i primi 37% di 50 negozi, cioè i primi 18 negozi (circa). Ma perché? Ecco che la matematica ci viene in aiuto.

Come entra in gioco la matematica

La curva che indica la probabilità di trovare la scelta giusta (y) fermandosi al punto x è

\(\)\[
y=\left(-\frac{x}{n}\right)*log\left(\frac{x}{n}\right)
\]\(\)

dove n è il numero di scelte che abbiamo a disposizione. Ecco un esempio con n=50.

Come si può notare, la funzione di probabilità presenta un massimo poco prima di x=20 e la probabilità (asse y) in quel punto è circa 0.4 (o 40% in percentuale). Infatti, tramite un rapido studio di funzione, essa raggiunge il massimo quando

\(\)\[ x=\frac{n}{e} \]\(\)

dove e=2.71828 è il numero di Eulero (o di Nepero), costante matematica importantissima. È immediato notare quindi che abbiamo il massimo della probabilità quando

\(\)\[ x=\frac{n}{e}=n*\left(\frac{1}{2.718282}\right)=n*0.3678794 \approx n*0.37 \]\(\)

Ovvero, in altri termini, quando il punto in cui ci fermiamo (x) è pari al 37% circa del totale delle nostre scelte; è quindi conveniente rifiutare il primo 37%. Per ottenere il valore della probabilità massima basta inserire

\(\)\[ x=\frac{n}{e} \]\(\)

all’interno della funzione originale

\(\)\[ y=\left(-\frac{x}{n}\right)*log\left(\frac{x}{n}\right) \]\(\)

ottenendo

\(\)\[ y=\frac{1}{e} \]\(\)

cioè circa 37%. Tramite il software statistico RStudio è possibile implementare questo problema. Il seguente grafico è stato ottenuto ponendo n=500 ed effettuando 1000 replicazioni. Come si può notare la probabilità massima è sempre circa uguale al 37%, viene raggiunta quando ci fermiamo al 37% delle scelte (il 37% di 500 è circa 184) mentre la funzione in blu è

\(\)\[ y=\left(-\frac{x}{500}\right)*log\left(\frac{x}{500}\right) \]\(\)

e si adatta molto bene ai punti.

Aspetti computazionali: quante prove fare e con quante scelte?

È chiaro che la curva di probabilità stimata sarà tanto più accurata quanto più sarà alto il numero di replicazioni (B). Per replicazioni si intende il numero di volte in cui viene provato il “gioco”. Per esempio, se entro nel centro commerciale 3 volte ed eseguo ogni volta la strategia migliore è poco probabile (in media) che funzioni. Se invece provo idealmente a ripetere la procedura 10000 volte è chiaro che i risultati sono migliori, ovvero le probabilità stimate dal risultato del  problema dell’arresto ottimale si avvicinano sempre di più a quelle teoriche (vere). Ecco un esempio ponendo n=50 costante e facendo variare B. La curva nera è stimata, quella rossa è teorica. È da sottolineare un problema dell’aumentare B: l’eccessivo tempo di calcolo da parte del programma.

Notiamo invece come, facendo variare il numero di scelte n e tenendo costante B=1000, al crescere di n aumenta la precisione ma decresce la regolarità della curva stimata. Deduciamo quindi che a parità di numero di replicazioni l’algoritmo fa più fatica a “lisciare” la funzione di probabilità stimata. Ciò che conta per avere un risultato ottimale è quindi un giusto compromesso tra il numero di tentativi ed il numero di prove: avrò in questo modo dei valori stimati molto più vicini a quelli attesi (reali).

Qui vediamo cosa succede se con 50 negozi ci fermiamo proprio sul 18° e ripetiamo la procedura 1000 volte. Come si può notare, le probabilità stimate più frequenti sono comprese tra 36% e 37%, in linea con il teorema, ma si possono avere anche delle probabilità più piccole (34%) o più grandi (40%), ma con minore frequenza. Questo significa che, se aumenta il numero di tentativi può succedere (raramente) che, pur adottando la strategia migliore, il risultato non sia in linea con quello atteso. Fa parte della variabilità statistica.

Nelle pubblicazioni scientifiche questo problema trova il nome di “secretary problem”, il problema della segretaria; fa riferimento al problema di un capo che cerca la migliore candidata su n scelte possibili. Si può trovare anche con il nome di “problema del matrimonio”. Oggi trova applicazioni in medicina, quando si vuole decidere il momento esatto in cui interrompere un trattamento farmacologico o in finanza, per trovare il punto più economicamente conveniente in cui abbassare le perdite di un investimento, e così via.