Passeggiata in due direzioni

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.

Per creare una lista di queste scelte con Javascript occorre memorizzare le posizioni via via occupate, per esempio attraverso una matrice inizializzata

var M=[[false],[false,true,false],[false]]
var m=1;

dove

M=[M[0], ..., M[m-y], ...M[2m]]  con y=m, ..., -m
M[m-y]=[M[m-y][0], ..., M[m-y][m-|y|-x], ...,M[m-y][2(m-|y|)]] con x = m-|y|, ..., |y|-m 

che si amplia man mano si amplia quando le posizioni raggiunte $(x,y,z) \longrightarrow M[m-z][m-|z|-y][m-|z|-|y|-x]$ sono tali che $|x|+|y| = m$

if (Math.abs(x)+Math.abs(y)==m){
	M=	[[false],...M.map(Y=>[false,...Y,false]),[false]];
	m++
}

ponendo poi, ogni volta che si aggiorna la posizione,

M[m-y][m-|y|-x]=true;

Possiamo elencare le posizioni vicine a $(x,y)$ non già occupate, tra le quali scegliere se possibile dove muovere al passo successivo

scelta=[];
if(! M[m-y-1][m-Math.abs(y+1)-x]) scelta.push([0,1]);
if(! M[m-y+1][m-Math.abs(y-1)-x]) scelta.push([0,-1]);
if(! M[m-y][m-Math.abs(y)-x-1]) scelta.push([1,0]);
if(! M[m-y][m-Math.abs(y)-x+1]) scelta.push([-1,0]);
...

Così ad esempio per passi si ottiene:

Si osservi che la passeggiata può terminare prima di completare il numero di passi stabilito, quando tutte le posizioni vicine sono già state precedentemente occupate.

Interessante sarebbe studiare ad esempio la variabile aleatoria "la passeggiata si blocca dopo k passi", oppure quante siano le passeggiate di questo tipo di $n$ passi.

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.