Irrfahrten auf freien Produkten, amalgamierten Produkten, Bäumen und Strings über unendlichem Alphabet
Final Report Abstract
The purpose of this project was devoted to the investigation of random walks on different structures, and to categorize structures in terms of the random walk. The structures studied were free products, free products by amalgamation, directed covers of infinite connected graphs, and strings over an infinite alphabet. In order to investigate the behaviour of random walks on these structures mathematical techniques from probability theory (random walks), structure theory (algebra, geometry and graph theory) and analysis (potential theory) were applied. During the study of random walks on directed covers of infinite graphs, that is, trees generated by infinite graphs, first natural questions have been in finding criteria for recurrence, transience and ergodicity. Here it turned out that the upper Collatz-Wielandt number is a critical value for such a criterion. Moreover, a formula for the rate of escape with respect to arbitrary length functions have been found, which led in particular to existence and also to a formula for the asymptotic entropy of the random walk on a directed cover. The results about entropy constitute also a new result for directed covers of finite graphs. Furthermore, the asymptotic behaviour of n-step return probabilities of random walks on free products of groups has been studied. The question was to investigate the range of different asymptotic behaviour. It turned out that a free product of m factors may have up to m + 1 different behaviours: the random walk on the free product either inherits its asymptotic behaviour from one of its free factors, or the nstep return probabilities behave asymptotically like ϱ^n n^-3/2, where ϱ is the spectral radius of the random walk. In particular, a complete classification is given to decide which behaviour occurs. Another topic within this project was the study of the asymptotic entropy of random walks on free products of graphs. While in the case of free products of groups the existence of entropy is well-known by Kingman's subadditive ergodic theorem, in the inhomogeneous case of free products of graphs the question of existence was not known a-priori. However, with the use of generating function techniques it turned out that entropy also exists in this case and equals the rate of escape with respect to the Greenian metric. Different formulas were provided using different techniques. The investigation of branching random walks on free products was another part of the project. The aim was to study the boundary behaviour of the branching process. This included the question which ends of the geometric boundary are hit and to determine the size of this boundary. Phase transitions have been discovered which point out whether ends described by finite words are hit or not. Existence of the boxcounting dimension has been proven, which is shown to be equal to the Hausdorff dimension in our setting. Formulas for the dimensions of the whole boundary and the boundary, which is hit by the branching process, have been provided. Ongoing work with Anders Karlsson asks for the qualitative behaviour of the drift of symmetric nearest neighbour random walks on free groups with d generators. The conjecture is that the drift function - seen as a function in d- 1 parameters, which are identified with the probabilities of going into the directions of the different generators - is a concave function. This question seems to be difficult, and the work is still ongoing.
Publications
- Asymptotic Entropy of Random Walks on Free Products, Electronic Journal of Probability, Volume 16, pages 76-105, 2011
Lorenz A. Gilch
- Random Walks on Directed Covers of Graphs. Journal of Theoretical Probability. Volume 24, Issue 1, pages 118-149, 2011
Lorenz A. Gilch, Sebastian Müller
(See online at https://doi.org/10.1007/s10959-009-0256-0)
