Consider a random walk in a graph and introduce a reinforcement on the edges so that the ones already traversed are more likely to be traversed in the future. We call such a process edge reinforced random walk (ERRW). In this thesis we review some results due to Pemantle about transience/recurrence of linearly edge reinforced random walks on infinite trees. We analyze the general case of a tree whose vertices are generated as individuals of a supercritical GaltonWatson branching process. We describe how the process can be reduced to a random walk in a random environment (RWRE) using exchangeability theory and we give criteria to determine whether the RWRE is transient or recurrent. Applying these tools we show that the ERRW on a tree can be either transient or recurrent depending on the strength of the reinforcement and in the case where the tree is binary we prove the existence of a phase transition.
Consider a random walk in a graph and introduce a reinforcement on the edges so that the ones already traversed are more likely to be traversed in the future. We call such a process edge reinforced random walk (ERRW). In this thesis we review some results due to Pemantle about transience/recurrence of linearly edge reinforced random walks on infinite trees. We analyze the general case of a tree whose vertices are generated as individuals of a supercritical GaltonWatson branching process. We describe how the process can be reduced to a random walk in a random environment (RWRE) using exchangeability theory and we give criteria to determine whether the RWRE is transient or recurrent. Applying these tools we show that the ERRW on a tree can be either transient or recurrent depending on the strength of the reinforcement and in the case where the tree is binary we prove the existence of a phase transition.
Edge reinforced random walk on GaltonWatson trees
CARLON, GIOVANNI
2022/2023
Abstract
Consider a random walk in a graph and introduce a reinforcement on the edges so that the ones already traversed are more likely to be traversed in the future. We call such a process edge reinforced random walk (ERRW). In this thesis we review some results due to Pemantle about transience/recurrence of linearly edge reinforced random walks on infinite trees. We analyze the general case of a tree whose vertices are generated as individuals of a supercritical GaltonWatson branching process. We describe how the process can be reduced to a random walk in a random environment (RWRE) using exchangeability theory and we give criteria to determine whether the RWRE is transient or recurrent. Applying these tools we show that the ERRW on a tree can be either transient or recurrent depending on the strength of the reinforcement and in the case where the tree is binary we prove the existence of a phase transition.File  Dimensione  Formato  

Tesi_GiovanniCarlon_2008007_Definitiva.pdf
accesso riservato
Dimensione
799.73 kB
Formato
Adobe PDF

799.73 kB  Adobe PDF 
The text of this website © Università degli studi di Padova. Full Text are published under a nonexclusive license. Metadata are under a CC0 License
https://hdl.handle.net/20.500.12608/52212