Finite range random walk on free groups and homogeneous trees
type: Item
instance of: scholarly article
title: Finite range random walk on free groups and homogeneous trees
zbMATH Open document ID: 0804.60006
author: Steven P. Lalley
published in: The Annals of Probability
publication date: 1995-01-15T00:00:00Z
review text: Let \({\mathcal G}\) be the free group with \(L\) generators. A finite-range random walk \(Z_ n\), \(n>0\), is a Markov chain on \({\mathcal G}\) with \(Z_ 0= e\) and transition probabilities \[ P(Z_{n+1}= gx\mid Z_ n=g)= p_ x, \qquad g,x\in {\mathcal G}, \] where \(p_ x\), \(x\in {\mathcal G}\), is a probability distribution on \({\mathcal G}\) with finite support. It is further assumed that the random walk is irreducible and aperiodic. The first main result is a local limit theorem describing the asymptotics of the \(n\)-fold convolution \(p^{*n}\) at a fixed \(x\in{\mathcal G}\) \[ p^{*n} (x)\sim B_ x R^{-n} \sqrt{R}/ 2\sqrt {\pi} n^{3/2}, \] where the constant \(R\in (0,\infty)\) depends on the distribution \(p\) only. In the later sections, information is obtained on \(p^{*n}(x)\) for variable \(x\). If the reduced word length \(| x|\) (the length of the minimal representation of \(x\) as a product of the generators and their inverses) grows linearly with \(n\), then a so-called saddlepoint approximation holds for \(p^{*n} (x)\). Another saddlepoint approximation is shown to hold for the word length functional \(| Z_ n|\). Many of the results were known before for important special cases, notably nearest neighbor random walks (\(p\) is concentrated on a generating set) and isotropic random walks \((p_ x= p_{| x|})\). The techniques need to be thoroughly reshaped, however, to work for the general finite-range random walks. The basic tool here is a generalized Perron-Frobenius theory of nonnegative matrices. -- An overview of probability theory on infinite graphs and groups is provided in a recent large survey by \textit{W. Woess} [Bull. Lond. Math. Soc. 26, No. 1, 1-60 (1994)].
reviewed by: Göran Högnäs
Mathematics Subject Classification ID: 60B15
Mathematics Subject Classification ID: 60F05
Mathematics Subject Classification ID: 60F99
Mathematics Subject Classification ID: 60G50
zbMATH DE Number: 528633
zbMATH Keywords: boundary process
zbMATH Keywords: word length functional
zbMATH Keywords: random walk
zbMATH Keywords: saddlepoint approximation
zbMATH Keywords: nearest neighbor random walks
zbMATH Keywords: Perron-Frobenius theory of nonnegative matrices
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1214/aop/1176989012
OpenAlex ID: W2059128173
DOI: 10.1214/AOP/1176989012
Recommended article: Q3330257
Recommended article: Random walks on the affine group of a homogeneous tree in the drift-free case
Recommended article: Branching random walks on free products of groups
Recommended article: Random walks on free solvable groups
Recommended article: Q4450069
Recommended article: Finitely additive random walks on infinitely generated free groups
Recommended article: Some asymptotic properties of random walks on free groups
Recommended article: Random walks on free products of cyclic groups
description: scientific article; zbMATH DE number 528633