Finite range random walk on free groups and homogeneous trees (Q1317234): Difference between revisions

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)].