Central Limit Theorems for Drift and Entropy of Random Walks on Free Products
Lorenz A. Gilch · 2025
Read Central Limit Theorems for Drift and Entropy of Random Walks on Free Products by Lorenz A. Gilch (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-17601.txt.
Introduction
A random walk on a free product of graphs wanders through a combined landscape built from several simpler graphs glued together. Lorenz A Gilch, writing alone, studies the long run behaviour of a natural class of such walks, formed by mixing the walks on the separate pieces. Earlier work had already shown that these walks possess a definite drift, a steady average speed, and a definite entropy, which measures their randomness.
Gilch proves three central limit theorems for these walks, the bell curve style laws that describe how far a real walk typically strays from its average drift and entropy. He also shows how the spread of those curves changes smoothly when the walk depends on a few adjustable parameters. The results complete the statistical picture of drift and entropy for this class of walks.
Catalog record
| CREATOR | Lorenz A. Gilch |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 93 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-17601
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Central Limit Theorems for Drift and Entropy of Random Walks on Free Products Lorenz A. Gilch Abstract . In this article we consider a natural class of random walks on free products of graphs, which arise as convex combinations of random walks on the single factors. From the works of Gilch [ 6 , 7 ] it is well-known that for these random walks the asymptotic entropy as well as the drift w.r.t. the natural transition graph distance and also w.r.t. the word length exist. The aim of this article is to formulate three central limit theorems with respect to both drift definitions and the entropy. In the case that the random walk depends on finitely many parameters we show that the corresponding variances in the central limit theorems w.r.t. both drifts vary real-analytically in terms of these parameters, while the variance in the central limit theorem w.r.t. the entropy varies real-analytically at least in the case of free products of finite graphs. 1. Introduction Let V_{1},V_{2} be finite or countable, disjoint sets with |V_{i}|\geq 2 , and fix distinguished elements o_{i}\in V_{i} , i\in\{1,2\} . Suppose that each V_{i} carries a transition matrix P_{i}\in[0,1]^{V_{i}\times V_{i}} . The free product V:=V_{1}\ast V_{2} consists of all finite words over the alphabet (V_{1}\cup V_{2})\setminus\{o_{1},o_{2}\} such that two consecutive letters do not lie in the same V_{i} . We consider a transient Markov chain (X_{n})_{n\in\mathbb{N}_{0}} on V , starting at the empty word X_{0}:=o , with transition law given by a convex combination of the kernels P_{i} . Denote by \|x\| the word length of x\in V and let d(o,x) denote the distance of x to o w.r.t. the natural graph metric on the transition graph of the random walk on V . Then, by Gilch [ 6 ] , it is well-known that the (asymptotic) drifts \lim_{n\to\infty}\frac{\|X_{n}\|}{n}\quad\textrm{ and }\quad\lim_{n\to\infty}\frac{d(o,X_{n})}{n} exist almost surely and both limits are almost surely constant. Moreover, let \pi_{n} denote the distribution of X_{n} . In Gilch [ 7 ] it is shown that the (asymptotic) entropy \lim_{n\to\infty}-\frac{1}{n}\log\pi_{n}(X_{n}) exists almost surely and the limit is also almost surely constant. The aim of this note is to establish three central limit theorems w.r.t. the drifts and the entropy. In particular, we will show that if the random walk’s law depends on finitely many parameters, then the variances in these central limit theorems vary real-analytically in terms of these parameters, where analyticity of the variance in the entropy case is restricted to free products of finite graphs. Let me outline some results on random walks on free products and their importance. Random walks on free products have been studied extensively, and there is a broad range of literature. Asymptotics of return probabilities were elaborated in Gerl and Woess [ 4 ] , Woess [ 15 ] , Sawyer [ 12 ] , Cartwright and Soardi [ 3 ] , Lalley [ 9 , 10 ] , and Candellero and Gilch [ 2 ] ; explicit drift and entropy formulas for free products of finite groups were obtained by Mairesse and Mathéus [ 11 ] , while Gilch [ 6 , 7 ] calculated later explicit formulas for the drift and the entropy in the more general, inhomogeneous setting of free products of graphs. Spectral properties were analyzed in Shi et al. [ 13 ] . The relevance of free products in group theory arises from Stallings’ Splitting Theorem (see Stallings [ 14 ] ), which characterizes finitely generated groups with more than one geometric end as those admitting a representation as a nontrivial free product by amalgamation or as an HNN extension over a finite subgroup; we note that free products arise as the special case of amalgams over the trivial subgroup. Most prior works focus on free products of groups, which are space-homogeneous and admit transitive random walks. In this article we address the more general setting of free products of graphs, which are lacking such a homogenity. In particular, we revisit results of [ 6 , 7 ] on the drift and the entropy of random walks on free products of graphs, where the random walk’s trajectory is decomposed into disjoint segments via so-called exit times (\mathbf{e}_{k})_{k\in\mathbb{N}} . We will use this decomposition in order to derive three central limit theorems in association with the asymptotic drift and entropy of (X_{n})_{n\in\mathbb{N}_{0}} . With the help of a very detailed understanding of this exit time process, the hard main work of the proofs lies in the rigorous preparation of some setting such that some standard reasoning for deriving central limit theorems can be applied. The paper is organized as follows: Section 2 recalls the definitions of free products and associated random walks on them. In Section 3 we introduce last cone entry times (exit times) and derive a sequence of renewal times (\mathbf{T}_{k})_{k\in\mathbb{N}_{0}} . Finally, in Sections 4 , 5 and 6 we drive the proposed central limit theorems and show that the variances vary real-analytically, when the random walk’s probability law depends on finitely many parameters only. In the Appendix A we outsource some proofs for better fluidity of reading. 2. Free Products and Random Walks 2.1. Free Products Let V_{1},V_{2} be disjoint, finite or countable sets with |V_{i}|\geq 2 for i\in\mathcal{I}:=\{1,2\} . We fix a distinguished element o_{i}\in V_{i} , called the root of V_{i} , for each i\in\mathcal{I} , and we set V_{i}^{\times}:=V_{i}\setminus\{o_{i}\} . The case |V_{1}|=|V_{2}|=2 will be excluded; see Remark 2.2 .(i). The free product of V_{1} and V_{2} is given by the set V:=V_{1}\ast V_{2}:=\Bigl\{v_{1}\ldots v_{k}\,\Bigl|\,k\in\mathbb{N},\;v_{\ell}\in V_{1}^{\times}\cup V_{2}^{\times},\;v_{i}\in V_{j}^{\times}\Rightarrow v_{i+1}\notin V_{j}^{\times}\Bigr\}\cup\{o\}, the set of finite words over the alphabet V_{1}^{\times}\cup V_{2}^{\times} with no two consecutive letters coming from the same V_{j}^{\times} , where o denotes the empty word. A partial composition law is defined as follows: if we have u=u_{1}\ldots u_{m} , v=v_{1}\ldots v_{n}\in V , m,n\in\mathbb{N} , and u_{m}\in V_{i}^{\times} , v_{1}\notin V_{i}^{\times} for some i\in\mathcal{I} , then uv is the concatenated word, which is again an element of V . We write \delta(u):=i , and make the convention uo_{j}=u=ou=uo for j\in\mathcal{I}\setminus\{\delta(u)\} . Furthermore, the word length of u=u_{1}\ldots u_{m} is denoted by \|u\|:=m . For u\in V , the cone rooted at u is given by C(u):=\{w\in V\mid w\text{ has prefix }u\}, the set of words in V starting with u . 2.2. Random Walks Let P_{i}=\bigl(p_{i}(x,y)\bigr)_{x,y\in V_{i}} be transition matrices on V_{i} , i\in\mathcal{I} , such that every x\in V_{i}^{\times} is accessible from o_{i} in finitely many steps with positive probability, that is, P_{i}^{n_{x}}(o_{i},x)>0 for some n_{x}\in\mathbb{N} . For sake of simplicity, we assume that p_{i}(x,x)=0 for every i\in\mathcal{I} and all x\in V_{i} , and we assume that there exist j\in\mathcal{I} , y\in V_{j}^{\times} and n_{y}\in\mathbb{N} with P_{j}^{n_{y}}(y,y)>0 ; see Remarks 2.2 .(iii). Fix \alpha\in(0,1) , and set \alpha_{1}:=\alpha , \alpha_{2}:=1-\alpha . Define the lifted transition matrix \overline{P}_{i}=\bigl(\overline{p}_{i}(x,y)\bigr)_{x,y\in V} by \overline{p}_{i}(uv,uw):=p_{i}(v,w), if u=u_{1}\ldots u_{m} with u_{m}\notin V_{i} and v,w\in V_{i} , i\in\mathcal{I} ; otherwise, we set \overline{p}_{i}(x,y):=0 . A natural random walk on V is governed by the transition matrix P=\bigl(p(x,y)\bigr)_{x,y\in V}:=\alpha_{1}\overline{P}_{1}+\alpha_{2}\overline{P}_{2}. The transition graph \mathcal{X} w.r.t. P arises from the transition graphs \mathcal{X}_{1},\mathcal{X}_{2} w.r.t. P_{1} , P_{2} in a natural way as follows: take copies of \mathcal{X}_{1} and \mathcal{X}_{2} and