Cammino auto-evitante su un reticolo
Ciao a tutti, vi propongo un "giochino" interessante sul quale vorrei la vostra opinione.
(ho provato a cercare su internet, stupidamente in italiano, "cammino auto-evitante" e ho trovato perlopiù sito di psichiatria.....!)
Consideriamo un reticolo tridimensionale discreto (cubico, per esempio).
Supponiamo che questo reticolo sia di estensione finita, di lato L per esempio.
Un cammino auto-evitante su questo reticolo è fatto così: il camminatore estrae ad ogni passo un numero e a seconda dell'estrazione si muove con uguale probabilità in una delle sei direzioni consentite. L'unica regola è che non può tornare su una casella già visitata. Se estrae un numero che lo porterebbe su una casella vietata, rimane fermo dov'è. Si dimostra numericamente (ma è anche ovvio) che per reticoli finiti il camminatore prima o poi si blocca (ossia si trova in una posizione nella quale tutte le caselle vicine sono occupate). Più specificamente, data una serie di cammini indipendenti, esiste un tempo caratteristico al quale è molto probabile che la maggior parte di questi cammini si sia bloccato.
La domanda è: è plausibile l'esistenza di questo tempo caratteristico anche per un reticolo di estensione L infinita?
Io penso di sì: questo tempo sarebbe definito come il tempo al quale, mediamente, è probabile che un cammino si sia bloccato. Questo numero mi viene intorno ai 50.000 passi. Tuttavia le incertezze sulle misure mi vengono piuttosto alte, quindi non è detto effettivamente che tale tempo esista. Voi, in linea del tutto teorica (oppure se qualcuno conosce già il risultato!), cosa ne pensate di questo problemino? L'esistenza del tempo caratteristico per reticoli infiniti è plausibile?
Grazie
Fabio
(ho provato a cercare su internet, stupidamente in italiano, "cammino auto-evitante" e ho trovato perlopiù sito di psichiatria.....!)
Consideriamo un reticolo tridimensionale discreto (cubico, per esempio).
Supponiamo che questo reticolo sia di estensione finita, di lato L per esempio.
Un cammino auto-evitante su questo reticolo è fatto così: il camminatore estrae ad ogni passo un numero e a seconda dell'estrazione si muove con uguale probabilità in una delle sei direzioni consentite. L'unica regola è che non può tornare su una casella già visitata. Se estrae un numero che lo porterebbe su una casella vietata, rimane fermo dov'è. Si dimostra numericamente (ma è anche ovvio) che per reticoli finiti il camminatore prima o poi si blocca (ossia si trova in una posizione nella quale tutte le caselle vicine sono occupate). Più specificamente, data una serie di cammini indipendenti, esiste un tempo caratteristico al quale è molto probabile che la maggior parte di questi cammini si sia bloccato.
La domanda è: è plausibile l'esistenza di questo tempo caratteristico anche per un reticolo di estensione L infinita?
Io penso di sì: questo tempo sarebbe definito come il tempo al quale, mediamente, è probabile che un cammino si sia bloccato. Questo numero mi viene intorno ai 50.000 passi. Tuttavia le incertezze sulle misure mi vengono piuttosto alte, quindi non è detto effettivamente che tale tempo esista. Voi, in linea del tutto teorica (oppure se qualcuno conosce già il risultato!), cosa ne pensate di questo problemino? L'esistenza del tempo caratteristico per reticoli infiniti è plausibile?
Grazie
Fabio
Risposte
Non so aiutarti nello specifico del tuo problema, ma posso segnalarti un problema vagamente simile che è noto con il nome di percolazione. Si considera un reticolo quadrato di lato $L$, i cui siti vengono impostati con probabilità $p$ come occupati o liberi, e si va a vedere se esiste un percorso costituito da siti liberi che porti da un lato all'altro del reticolo. Si studia quindi qual è il valore critico della probabilità $p_c$ per cui compare un percorso nel limite termodinamico, ovvero $L\to\infty$.
Puoi consultare ad esempio questo lavoro, magari cercando qualcosa sull'argomento puoi trovare anche qualcosa riguardo il tuo problema.
Puoi consultare ad esempio questo lavoro, magari cercando qualcosa sull'argomento puoi trovare anche qualcosa riguardo il tuo problema.
"SaturnV":
La domanda è: è plausibile l'esistenza di questo tempo caratteristico anche per un reticolo di estensione L infinita?
Io penso di sì: questo tempo sarebbe definito come il tempo al quale, mediamente, è probabile che un cammino si sia bloccato. Questo numero mi viene intorno ai 50.000 passi. Tuttavia le incertezze sulle misure mi vengono piuttosto alte, quindi non è detto effettivamente che tale tempo esista. Voi, in linea del tutto teorica (oppure se qualcuno conosce già il risultato!), cosa ne pensate di questo problemino? L'esistenza del tempo caratteristico per reticoli infiniti è plausibile?
Grazie
Fabio
Come dici te "in linea del tutto teorica" penso anche io di si.
Ragionando in modo piu' semplice e considerando una matrice a solo due dimensioni (anzichè 3), è facile pensare che il percorso ad un certo punto si blocchi. (..pensiamo anche al giochino del serpente presente sui cellulari, ma con la coda che non si accorcia).
Il fatto che la matrice sia poi infinita, non influenza cmq, che "il serpente" si aggrovigli su se stesso.
"Lord K":
Prima di rispondere al tuo interessante quesito, potresti farmi/ci vedere come è la dimostrazione formale del fatto che in un reticolo finito ci si fermi dopo un numero finito di passi??? Se avessimo quella sotto mano sarebbe più semplice seguire il discorso
Il fatto che "ci si fermi" mi pare ovvio, dato che il numero di posizioni possibili e' finito. Meno evidente e' il fatto che il cammino "si blocchi", cioe' che ci si fermi perche' tutte le posizioni adiacenti sono
ricoperte. Ma se non sbaglio la probabilita' di fermarsi indetinitamente in una posizione che ammette via d'uscita dovrebbe essere zero.
Non me ne intendo pero'
Ho svolto un'analisi numerica (al calcolatore) del problema.
A partire da L=10 fino a L=200 (quindi fino a 8 milioni di siti) si nota chiaramente che graficando lo spostamento dall'origine in funzione del tempo, dopo un certo tempo t, tale grafico (ottenuto mediando un milione di realizzazioni del percorso aleatorio) possiede derivata nulla, si appiattisce. Ho definito tempo critico il tempo in cui avviene tale appiattimento. Questo fenomeno avviene, a tempi diversi a crescenti, per ogni dimensione del reticolo considerato.
Per reticoli grandi (da L=100 a L=200) tale tempo tende a stazionare a poco meno di 50.000 passi. Sembra appunto che tenda asintoticamente a un valore limite per reticoli infiniti.
Fabio[/img]
A partire da L=10 fino a L=200 (quindi fino a 8 milioni di siti) si nota chiaramente che graficando lo spostamento dall'origine in funzione del tempo, dopo un certo tempo t, tale grafico (ottenuto mediando un milione di realizzazioni del percorso aleatorio) possiede derivata nulla, si appiattisce. Ho definito tempo critico il tempo in cui avviene tale appiattimento. Questo fenomeno avviene, a tempi diversi a crescenti, per ogni dimensione del reticolo considerato.
Per reticoli grandi (da L=100 a L=200) tale tempo tende a stazionare a poco meno di 50.000 passi. Sembra appunto che tenda asintoticamente a un valore limite per reticoli infiniti.
Fabio[/img]
Prima di rispondere al tuo interessante quesito, potresti farmi/ci vedere come è la dimostrazione formale del fatto che in un reticolo finito ci si fermi dopo un numero finito di passi??? Se avessimo quella sotto mano sarebbe più semplice seguire il discorso 
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo