What is the difference between a square and a triangle?

Pierre Tarrès előadásának absztraktja

2008. május 8. csütörtök 16:15

 
 
Edge-Reinforced Random Walk (ERRW), introduced by Coppersmith and Diaconis [1] in 1986, is a process evolving in an environment constantly modified by its own behaviour: at each step, the probability to move along an edge is proportional to a function - called the weight function - of the number of visits to this edge. A similar notion of Vertex-Reinforced Random Walk [6] (VRRW) favours the more visits to vertices instead.

 
Sellke proved in 1994 that, if the weight function is reciprocally summable then on any graph of bounded degree without odd cycles, the (strongly) ERRW ends up visiting the same (random) edge back and forth. The Rubin construction he used towards the proof could not carry on to other graphs, even in the "simple" case of a triangle, thus introducing the "triangle conjecture" that the same behaviour should occur in general. A simple linear algebra argument [5] illustrates the difference in this respect between odd and even cycles.

 
Sellke's conjecture for nondecreasing weight functions was proved in a joint work with V. Limic [4]. However, our method requires a more detailed analysis of the behaviour of the walk.

 
The purpose of this talk is to give an introduction to this question, as well as a general overview of the subject and its techniques: martingales methods, Pólya urn models, a correspondence with random walks in random environment [2, 3, 7], Ray-Knight local time analysis [10]. The above variety of techniques reflects a large range of behaviours for reinforced random walks. It is worth noting in particular that, although VRRW and ERRW have analogous definitions, they show significantly different behaviours in the case of linear weight on the integer lattice: VRRW eventually gets stuck on five (random) consecutive sites almost surely [9], whereas the ERRW visits all sites of the lattice infinitely often, almost surely [1].

  References
 
[1]D. Coppersmith and P. Diaconis, Random walks with reinforcement, Unpublished manuscript (1986).
[2]P. Diaconis, Recent progress on de Finetti's notions of exchangeability, Bayesian statistics (Valencia,1987) 3 (1988), Oxford Univ. Press, New York, 111--125.
[3]M.S. Keane and S.W.W. Rolles, Edge-reinforced random walk on finite graphs, Infinite dimensional stochastic analysis (Amsterdam, 1999), R. Neth. Acad. Arts. Sci. Amsterdam (2000), 217--234.
[4]V. Limic and P. Tarrès, Attracting edge and strongly edge reinforced random walks, To appear in Annals of Probability (2007).
[5]V. Limic and P. Tarrès, Attracting edge: a commentary, To be submitted to the Proceedings of the X Brazilian school of Probability (2007).
[6]R. Pemantle, Random processes with reinforcement, Massachussets Institute of Technology Doctoral Dissertation (1988).
[7]R. Pemantle, Phase transition in reinforced random walk and RWRE on trees, Annals of Probability 16 (1988), 1229--1241.
[8]T. Sellke, Reinforced random walks on the d-dimensional integer lattice, Technical report 94-26, Purdue University (1994).
[9]P. Tarrès, VRRW on Z eventually gets stuck on five points, Annals of Probability 32(2B) (2004), 2650--2701.
[10]B. Tóth, Self-interacting random motions -- A Survey, Random Walks -- A Collection of Surveys (editors: P. Révész and B. Tóth) 9, Bolyai Society Mathematical Studies, 9 (1999), 349--384.

 
Balázs Márton, 2008.03.17