Algoritmo random walk (e come programmarlo)

Il concetto di random walk viene utilizzato in diversi campi, dalla finanza alla scienza, per modellare situazioni in cui gli elementi si muovono in modo imprevedibile. In sostanza, è un modo semplice di rappresentare il caos o l’incertezza nel movimento.

Definizione

Una random walk è un processo nel quale ad ogni passo ci troviamo in un nodo in un grafo non diretto e seguiamo un arco uscente scelto in modo uniformemente casuale. Una catena di Markov è simile, in qualche modo, con la differenza che la random walk può essere vista come un caso particolare di quest’ultima.

A che serve camminare a caso in uno spazio n dimensionale? Una passeggiata casuale (random walk), per quanto possa sembrare strano, è un concetto matematico che descrive un percorso, nel quale ogni passo è deciso in modo casuale e presenta una notevole utilità pratica. Puoi immaginare una persona che si muove in avanti o indietro a caso su una linea, oppure ad un disegnare che approssima una linea per piccoli tratti al fine di creare un effetto fuzzy o sfumato. Ad ogni passo, la persona può decidere di andare a destra o a sinistra con la stessa probabilità, oppure con probabilità leggermente diverse a seconda dei casi. L’algoritmo è parte di strategie di decisione in cui, semplicemente, non c’è un modo per decidere con chiarezza quale scelta far prendere all’algoritmo, e per evitare stalli si decide casualmente pur di far procedere l’algoritmo (o una subroutine dello stesso).

Le random walks possono verificarsi in molte situazioni e sono utili per analizzare diverse situazioni. Considera il seguente gioco d’azzardo: un giocatore scommette 1 dollaro e può perderlo o vincere un dollaro aggiuntivo con probabilità 1/2. Poiché la probabilità di ciascuno di questi eventi è uguale, possiamo pensarla come una random walk su un grafico a linee, dove ogni nodo rappresenta l’ammontare della ricchezza in un determinato momento. Ciò ci consente di apprendere numerosi aspetti del gioco, come la distribuzione di probabilità dell’importo di denaro in un dato momento. Possiamo anche chiederci della probabilità che il giocatore rimanga senza soldi prima di vincere una certa quantità e, se ciò accade, qual è il tempo previsto prima che ciò avvenga.

Le random walk godono di determinate proprietà matematiche (che potete trovare qui, ad esempio) e della singolare caratteristica di garantire, nel lungo periodo, il ritorno al punto di partenza (quantomeno nel caso n=1 e n=2 dimensioni).