Large deviations for random walks on Galton-Watson trees: Averaging and uncertainty
type: Item
instance of: scholarly article
title: Large deviations for random walks on Galton-Watson trees: Averaging and uncertainty
zbMATH Open document ID: 0996.60110
author: Amir Dembo
author: Nina Gantert
author: Yuval Peres
author: Ofer Zeitouni
publication date: 2002-06-27T00:00:00Z
review text: Let \(T\) be a Galton-Watson tree, i.e., the random graph whose vertices are the individuals of a branching process, equipped with edges between each individual and its immediate offspring. We start with one particle at time 0, the root, and we assume that the offspring distributions of the individuals are i.i.d. and that there is always at least one child. In particular, the tree is supercritical and expands exponentially fast. By \(|j|\) we denote the distance of the vertex \(j\) from the root, i.e., the number of the generation of \(j\). On \(T\), we consider a nearest-neighbor random walk \((X_n)_{n\in\mathbb N_0}\) whose transition probabilities are given, with a parameter \(\lambda>0\), as follows. Jumps from the root are made to any of the immediate offspring of the root with equal probability, and jumps from any other vertex to the parent are made with probability \(1/(\lambda+k)\) and to any of the \(k\) offspring with probability \(\lambda/(\lambda+k)\). This random walk is called the \(\lambda\)-biased random walk and has been studied in various papers; for \(\lambda=1\) it is equal to the simple random walk. The \(\lambda\)-biased random walk on the Galton-Watson tree may be seen as an infinite-dimensional example of a random walk in random environment. The authors derive large-deviation principles for the distance of the walker to the root at time \(n\), \(|X_n|\), as \(n\to\infty\), both in the annealed setting (where the probability is taken with respect to the tree and the walk) and in the quenched setting (where the probability is taken only with respect to the walk, conditionally on the tree). More precisely, the logarithmic rate of the probability of the event \(\{|X_n|>y n\}\) is identified in terms of a rate function \(J_\lambda(y)\) for \(y\in[0,1]\). The rate function turns out to be convex and continuous. There is no phase transition in the parameter \(\lambda\). Interestingly, it turns out that the large-deviation principles in the annealed …
Mathematics Subject Classification ID: 60K37
Mathematics Subject Classification ID: 60F10
Mathematics Subject Classification ID: 60J80
Mathematics Subject Classification ID: 82C44
zbMATH DE Number: 1761130
zbMATH Keywords: random walk in random environment
zbMATH Keywords: large deviations
zbMATH Keywords: Galton-Watson tree
reviewed by: W. König
MaRDI profile type: Publication
full work available at URL: s004400100162
OpenAlex ID: W1964978805
DOI: 10.1007/S004400100162
published in: Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete
description: scientific article; zbMATH DE number 1761130