Passeggiate casuali

Con memoria, a passo costante in due direzioni ortogonali, simmetriche, autoevitanti.

Analizziamo il caso in cui l’ubriaco si muove, con passo costante e uguale probabilità di seguire una delle due direzioni ortogonali, in un verso o quello opposto, ma evitando le posizioni in cui è già stato. Questo della passeggiata casuale auto-evitante (Self Avoiding Random Walk) è un ambito di non poca importanza nella modellazione del comportamento topologico di molecole come le proteine, il cui volume fisico proibisce l'occupazione multipla dello stesso punto spaziale.

Occorrerà memorizzare le posizioni via via occupate e tener presente che la passeggiata può terminare prima di completare il numero di passi stabilito, quando tutte le posizioni vicine sono già state precedentemente occupate.

P = [[0,0]]; scelta = [[1,0],[0,1],[-1,0],[0,-1]]; i = 0; while(scelta.length > 0 && i < n){ [x,y] = scelta[Math.floor(Math.random()*scelta.length)]; P.push([x,y]); scelta = [[x+1,y],[x,y+1],[x-1,y],[x,y-1]].filter(v => ! P.some((([x0,y0]) => x==x0 && y==y0)); i++ }

Così ad esempio per passi si ottiene:


Possiamo visualizzare anche la distribuzione sperimentale della distanza della posizione finale della passeggiata simulando passeggiate con 30 passi.

Si ottiene come distanza media.

Possiamo visualizzare anche la distribuzione sperimentale relativa alla variabile aleatoria "la passeggiata si interrompe dopo k passi" simulando passeggiate con 30 passi.

Si ottiene come valore medio.

Possiamo visualizzare anche la distribuzione sperimentale relativa alla variabile aleatoria "numero passeggiate fino a 30 passi interrotte prima della fine" simulando passeggiate.

Tuttavia molte delle domande basilari relative a questo modello sono difficili da risolvere in modo matematicamente rigoroso. In particolare, non sappiamo molto su quanto lontano giunga una passeggiata casuale auto-evitante di n passi dal suo punto di partenza, o anche quante passeggiate di questo tipo ci siano. Queste e altre importanti questioni sulla passeggiata auto-evitante rimangono irrisolte in senso matematico rigoroso, sebbene le comunità di fisica e chimica abbiano raggiunto un consenso sulle risposte con una varietà di metodi non rigorosi, comprese le simulazioni al computer. Ma ci sono stati progressi anche tra i matematici, in gran parte nell'ultimo decennio.

... l'esatta enumerazione di tutti i possibili percorsi è stata effettuata fino ad oggi solo per $N < 34$, con ulteriori enumerazioni rese difficili a causa della crescita esponenziale del numero di percorsi all'aumentare di N. Valori maggiori di N possono essere studiati mediante estrapolazione dei dati di numerazione esatta, o mediante simulazioni Monte Carlo. (da N. Madras, G. Slade, The Self-Avoiding Walk, Birkhauser)

In particolare su quest'ultima questione si può vedere Self-Avoiding Walk su Wolfram Mathworld.

❮❮