Asymptotic properties of random walks on graphs

"Random walks" is a topic situated in between probability, potential theory, harmonic analysis, geometry, graph theory, and algebra. The beauty of the subject stems from this linkage, both in the way of thinking and in the methods employed, of different fields. Random walks are random processes (Markov chains) which are adapted to a given structure (geometric or algebraic) of the underlying state space on which they evolve. The structures considered here are discrete and infinite graphs and groups. From the probabilistic viewpoint, the question is what impacct the particular type of structure has on various aspects of the behaviour of the random walk, such as transience/recurrence, asymptotic behaviour of transition probabilities, rate of escape and convergence to a boundary at infinity, and harmonic functions. Vice versa, random walks are also a tool for understanding and describing the structure of graphs, groups and related objects. The purpose of the present project is to study specific features of random walk, mainly on trees and tree-like structures of the following type: (A) trees with finitely many cone types, among which the so-called comb lattices, (B) a more general class of "context-free" graphs, (C) transitive graphs with infinitely many ends, (D) products of certain trees, (E) the Diestel-Leader graphs. The specific features are: (a) asymptotic behaviour of transition probabilities, (b) asymptotic behaviour of Green and Martin kernels and the Martin boundary, (c) spatial behaviour of random walk trajectories, (d) internal diffusion limited aggregation.

A random walk is a random process on a graph (network), where a particle (walker) moves randomly from point to point. Randomness is provided by a transition matrix which encodes the probabilities to move to a next point, given the actual position. These probabilities are assumed to be adapted to the underlying graph structure by some conditions that have to be specified from case to case. The general theme of the project has been the study of the interplay between structural (geometric, combinatorial, or algebraic) properties of the graph, which is assumed infinite here, and probabilistic as well as analytic features of the random walk: what can we deduce from the type of structure about the behaviour of the random process, and vice versa, what do properties of the latter tell us about the underlying structure ? The interested reader may look at an introductory article by Woess (in German) and a more advanced overview by Saloff-Coste (published in the Notices of the A.M.S), both available online at www.math.tugraz.at/~woess/#research , or also the advanced monograph by Woess, "Random Walks on Infinite Graphs and Groups", Cambridge Univ. Press, 2000. Among the achievements of the project, let me outline the subject of lamplighter random walks. In this case, in addition to the moves on the graph, there is a "lamp" at each point. Initially, all lamps are "off", and when the walker moves along, he chooses randomly at each step whether to switch the lamp where he stands or to leave it as it is. In order to understand the process, one has to consider a higher level "lamplighter graph" where one keeps track both of the actual walker`s position and the configuration of lamps that are switched on. In the typical situation when the base graph is a two-way-infinite line, we made a little breakthrough thanks to a precise understanding of the geometry of the associated lamplighter graph: it is a Diestel-Leader graph, horocyclic product of two homogenous trees. This allowed us to describe precisely the harmonic functions of the random walk (i.e., its potential theory) via the Martin boundary, to introduce an explicit method for computing the spectrum of the transition operator, and the asymptotic behaviour of n-step transition probabilities. This was done for Diestel-Leader graphs in general, and subsequently, we introduced horocyclic products of an arbitrary number of trees and exhibited many of their interesting features. One of them is that the transition operator always has pure point spectrum. Further highlights of the project concern cogrowth and non-backtracking random walks, and asymptotics of random walks on trees with a "fractal" structure.