The *-Edge Reinforced random walk, bayesian statistics and statistical physics
Pierre Tarres
In this course we study the so-called Edge-Reinforced Random Walk (ERRW), Vertex-Reinforced Jump Process, and their non-reversible generalizations called *-Edge-Reinforced Random Walk (*-ERRW) and *-Vertex-Reinforced Jump Process (*-VRJP).
We first introduce those processes through their motivation from Bayesian statistics for Markov Chains. To that end, we start with the Polya urn, a process in which at every time step one adds a ball of a given color with a probability proportional to the number of balls of that color in the urn. This allows us to define the notion of exchangeability, de Finetti’s theorem, Bayesian conjugate priors and posteriors and sufficient statistics.
Then we introduce the Edge-Reinforced Random Walk on a discrete locally finite graph, introduced in the seminal work of Coppersmith and Diaconis (1986), which moves to a nearest-neighbor with a probability proportional to the number of crossings of the corresponding edge. We prove that this process satisfies a partially exchangeability property, in the sense of Diaconis and Freedman (1982), which makes it a random walk in random environment but also enables one to do similar Bayesian statistics (Diaconis and Rolles, 2006). We also show how that Bayesian approach enables one to guess the mixing measure of the process, which was first computed by Coppersmith and Diaconis (1986), Keane and Rolles (2000) through a different technique.
Then we introduce the Vertex-Reinforced Jump Process (VRJP), first proposed by Werner and introduced by Davis and Volkov (2002), a continuous time process on a discrete locally finite graph, which moves to an adjacent vertex at a rate proportional to its current local time. We show how this process is related to the ERRW, see Tarrès (2011) and Sabot and Tarrès (2015). We also show how one can guess through Bayesian statistics the limiting measure, which was first computed for general discrete graphs by Sabot and Tarrès (2015) by a different technique. We discuss how that measure is related to the so-called supersymmetric hyperbolic sigma field model first studied by Disertori, Spencer and Zirnbauer (2010). We introduce an alternative approach for the study of that measure, through a random Schrödinger approach by Sabot, Tarrès and Zeng (2017).
Those results enable one to deduce recurrence/transience criteria, see in particular Sabot and Tarrès (2015), Disertori, Sabot and Tarrès (2014), Sabot and Zeng (2019), Poudevigne (2019). An alternative proof of recurrence not using those explicit links was proposed independently by Angel, Crawford and Kozma (2014). We briefly discuss recent work and consequences by various authors.
Then we introduce the *-Edge-Reinforced Random Walk (*-ERRW) through its motivation from Bayesian statistics of variable order Markov Chains. The process is again partially exchangeable in the sense of Diaconis and Freedman (1982). It can also be associated to a continuous process called the *-Vertex Reinforced Random Walk, which itself is in general not exchangeable, but can be made exchangeable through averaging of the initial local time.
Again we guess the limiting measure of both process through the same Bayesian technique, and explain the corresponding random Schrödinger approach, see Sabot and Tarrès (2021).
Prerequisites: we only assume elementary knowledge of measure theoretic probability theory.
Note:In addition to the 3 lectures, this course will feature open discussion sessions on Tuesday 14UTC and Wednesday 16UTC. Students are encouraged to bring questions to these sessions, which will not be recorded.