Large deviations for random walks on Galton-Watson trees: Averaging and uncertainty (Q1601805)

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 and the quenched setting coincide. The authors give an interpretation and explanation in terms of an effect that they call uncertainty. By this, it is roughly meant that the position of the walker is uncertain if its distance to the root is given only. Intuitively speaking, if the tree would like to help to keep the probability of the event \(\{|X_n|>y n\}\) low, then all the particles in the \(n\)th generation had to take part in that, and this has a rather small probability since the size of the \(n\)th generation increases exponentially. Hence, annealed probabilities are roughly equal to the quenched ones. For random walk in random environment in dimension one, it is known that the annealed and quenched principles differ considerably, and it is conjectured that in large dimensions the difference should become smaller and smaller. In this sense, the present paper handles the boundary case of infinite dimension in an important special case.