BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Wolfgang Woess

Wolfgang Woess appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.PRmath.GRmath.DGmath.FAmath.COFormal Languages and Automata TheoryInformation Theorymath.DSmath.ITmath.MGmath.SP

Catalog footprint

What is connected

27works
11topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

27 published item(s)

preprint2026arXiv

Diffusion on homogeneous ultrametric spaces: the contributions of Alessandro Figà-Talamanca

Alessandro Figà-Talamanca (1938-2023) was an influential Italian mathematician, scientific leader of the Italian group of harmonic analysis for many years. Since the late 1970ies, his interest focussed on harmonic analysis on free groups and trees. In the later years of his scientific work he became also interested in diffusion processes on homogeneous ultrametric spaces such as local fields and totally disconnected Abelian groups. This is related with the close connection of those spaces with trees and their boundaries and concerns, in particular, the construction of such processes via discrete-time walks on trees. The present notes provide rather detailed comments on this part of his work and the related, quite abundant literature. This is intended to become part of a volume of selected papers by Figà-Talamanca, accompanied by comments such as the present text.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Recurrence of 2-dimensional queueing processes, and random walk exit times from the quadrant

Let $X = (X_1, X_2)$ be a 2-dimensional random variable and $X(n), n \in \mathbb{N}$ a sequence of i.i.d. copies of $X$. The associated random walk is $S(n)= X(1) + \cdots +X(n)$. The corresponding absorbed-reflected walk $W(n), n \in \mathbb{N}$ in the first quadrant is given by $W(0) = x \in \mathbb{R}_+^2$ and $W(n) = \max \{ 0, W(n-1) - X(n) \}$, where the maximum is taken coordinate-wise. This is often called the Lindley process and models the waiting times in a two-server queue. We characterize recurrence of this process, assuming suitable, rather mild moment conditions on $X$. It turns out that this is directly related with the tail asymptotics of the exit time of the random walk $x + S(n)$ from the quadrant, so that the main part of this paper is devoted to an analysis of that exit time in relation with the drift vector, i.e., the expectation of $X$.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Boundary behaviour of $λ$-polyharmonic functions on regular trees

This paper studies the boundary behaviour of $λ$-polyharmonic functions for the simple random walk operator on a regular tree, where $λ$ is complex and $|λ|> ρ$, the $\ell^2$-spectral radius of the random walk. In particular, subject to normalisation by spherical, resp. polyspherical functions, Dirichlet and Riquier problems at infinity are solved and a non-tangential Fatou theorem is proved.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Multiple boundary representations of $λ$-harmonic functions on trees

We consider a countable tree $T$, possibly having vertices with infinite degree, and an arbitrary stochastic nearest neighbour transition operator $P$. We provide a boundary integral representation for general eigenfunctions of $P$ with eigenvalue $λ\in \mathbb{C}$, under the condition that the oriented edges can be equipped with complex-valued weights satisfying three natural axioms. These axioms guarantee that one can construct a $λ$-Poisson kernel. The boundary integral is with respect to distributions, that is, elements in the dual of the space of locally constant functions. Distributions are interpreted as finitely additive complex measures. In general, they do not extend to $σ$-additive measures: for this extension, a summability condition over disjoint boundary arcs is required. Whenever $λ$ is in the resolvent of $P$ as a self-adjoint operator on a naturally associated $\ell^2$-space and the diagonal elements of the resolvent (`Green function') do not vanish at $λ$, one can use the ordinary edge weights corresponding to the Green function and obtain the ordinary $λ$-Martin kernel. We then consider the case when $P$ is invariant under a transitive group action. In this situation, we study the phenomenon that in addition to the $λ$-Martin kernel, there may be further choices for the edge weights which give rise to another $λ$-Poisson kernel with associated integral representations. In particular, we compare the resulting distributions on the boundary. The material presented here is closely related to the contents of our `companion' paper arXiv:1802.01976

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Polyharmonic functions for finite graphs and Markov chains

On a finite graph with a chosen partition of the vertex set into interior and boundary vertices, a $λ$-polyharmonic function is a complex function $f$ on the vertex set which satisfies $(λ\cdot I - P)^n f(x) = 0$ at each interior vertex. Here, $P$ may be the normalised adjaceny matrix, but more generally, we consider the transition matrix $P$ of an arbitrary Markov chain to which the (oriented) graph structure is adapted. After describing these `global' polyharmonic functions, we turn to solving the Riquier problem, where $n$ boundary functions are preassigned and a corresponding `tower' of $n$ successive Dirichlet type problems are solved. The resulting unique solution will be polyharmonic only at those points which have distance at least $n$ from the boundary. Finally, we compare these results with those concerning infinite trees with the end boundary, as studied by Cohen, Colonnna, Gowrisankaran and Singman, and more recently, by Picardello and Woess.

0 citations0 reviewsNo code linkedOpen access
preprint2018arXiv

Boundary representations of $λ$-harmonic and polyharmonic functions on trees

On a countable tree $T$, allowing vertices with infinite degree, we consider an arbitrary stochastic irreducible nearest neighbour transition operator $P$. We provide a boundary integral representation for general eigenfunctions of $P$ with eigenvalue $λ\in \mathbb{C}$. This is possible whenever $λ$ is in the resolvent set of $P$ as a self-adjoint operator on a suitable $\ell^2$-space and the on-diagonal elements of the resolvent ("Green function") do not vanish at $λ$. We show that when $P$ is invariant under a transitive (not necessarily fixed-point-free) group action, the latter condition holds for all $λ\ne 0$ in the resolvent set. These results extend and complete previous results by Cartier, by Figà-Talamanca and Steger, and by Woess. For those eigenvalues, we also provide an integral representation of $λ$-polyharmonic functions of any order $n$, that is, functions $f: T \to \mathbb{C}$ for which $(λ\cdot I - P)^n f=0$. This is a far-reaching extension of work of Cohen et al., who provided such a representation for simple random walk on a homogeneous tree and eigenvalue $λ=1$. Finally, we explain the (much simpler) analogous results for "forward only" transition operators, sometimes also called martingales on trees.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Brownian motion on treebolic space: positive harmonic functions

Treebolic space HT(q,p) is a key example of a strip complex in the sense of Bendikov, Saloff-Coste, Salvatori, and Woess [Adv. Math. 226 (2011), 992-1055]. It is an analog of the Sol geometry, namely, it is a horocylic product of the hyperbolic upper half plane with a "stretching" parameter q and the homogeneous tree T with vertex degree p+1 < 2, the latter seen as a one-complex. In a previous paper [arXiv:1212.6151, Rev. Mat. Iberoamericana, in print] we have explored the metric structure and isometry group of that space. Relying on the analysis on strip complexes, a family of natural Laplacians with "vertical drift" and the escape to infinity of the associated Brownian motion were considered. Here, we undertake a potential theoretic study, investigating the positive harmonic functions associated with those Laplacians. The methodological subtleties stem from the singularites of treebolic space at its bifurcation lines. We first study harmonic functions on simply connected sets with "rectangular" shape that are unions of strips. We derive a Poisson representation and obtain a solution of the Dirichlet problem on sets of that type. This provides properties of the density of the induced random walk on the collection of all bifuraction lines. Subsequently, we prove that each positive harmonic function with respect to that random walk has a unique extension which is harmonic with respect to the Laplacian on treebolic space. Finally, we derive a decomposition theorem for positive harmonic functions on the entire space that leads to a characterisation of the weak Liouville property. We determine all minimal harmonic functions in those cases where our Laplacian arises from lifting a (smooth) hyperbolic Laplacian with drift from the hyperbolic plane to treebolic space.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Brownian motion on treebolic space: escape to infinity

Treebolic space is an analog of the Sol geometry, namely, it is the horocylic product of the hyperbolic upper half plane H and the homogeneous tree T with degree p+1 > 2, the latter seen as a one-complex. Let h be the Busemann function of T with respect to a fixed boundary point. Then for real q > 1 and integer p > 1, treebolic space HT(q,p) consists of all pairs (z=x+i y,w) in H x T with h(w) = log_{q} y. It can also be obtained by glueing together horziontal strips of H in a tree-like fashion. We explain the geometry and metric of HT and exhibit a locally compact group of isometries (a horocyclic product of affine groups) that acts with compact quotient. When q=p, that group contains the amenable Baumslag-Solitar group BS(p)$ as a co-compact lattice, while when q and p are distinct, it is amenable, but non-unimodular. HT(q,p) is a key example of a strip complex in the sense of our previous paper in Advances in Mathematics 226 (2011) 992-1055. Relying on the analysis of strip complexes developed in that paper, we consider a family of natural Laplacians with "vertical drift" and describe the associated Brownian motion. The main difficulties come from the singularites which treebolic space (as any strip complex) has along its bifurcation lines. In this first part, we obtain the rate of escape and a central limit theorem, and describe how Brownian motion converges to the natural geometric boundary at infinity. Forthcoming work will be dedicated to positive harmonic functions.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Isotropic Markov semigroups on ultra-metric spaces

Let (X,d) be a locally compact separable ultra-metric space. Given a reference measure μ on X and a step length distribution on the non-negative reals, we construct a symmetric Markov semigroup P^t acting in L^2(X,μ). We study the corresponding Markov process. We obtain upper and lower bounds of its transition density and its Green function, give a transience criterion, estimate its moments and describe the Markov generator and its spectrum, which is pure point. In the particular case when X is the field of p-adic numbers, our construction recovers fractional derivative and the Taibleson Laplacian (spectral multiplier), and we can also apply our theory to the study of the Vladimirov Laplacian which is closely related to the concept of p-adic Quantum Mechanics. Even in this well established setting, several of our results are new. We also elaborate the relation between our processes and Kigami's jump processes on the boundary of a tree which are induced by a random walk. In conclusion, we provide examples illustrating the interplay between the fractional derivatives and random walks.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

What is a horocyclic product, and how is it related to lamplighters?

This is a rather personal introductory outline of an interesting class of geometric, resp. graph- and group-theoretical structures. After an introductive section about their genesis, the general construction of horocyclic products is presented. Three closely related basic structures of this type are explained in more detail: Diestel-Leader graphs, treebolic spaces, and Sol-groups, resp. -manifolds. Emphasis is on their geometry, isometry groups, quasi-isometry classification and boundary at infinity. Subsequently, it is clarified under which parametrisation they admit discrete groups of isometries acting with compact quotient. Finally, further develpoments are reviewed briefly. Remark: the posted version contains a correction of a misprint that appeared on the bottom of page 22 in the version which appeared in IMN.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

On the duality between jump processes on ultrametric spaces and random walks on trees

The purpose of these notes is to clarify the duality between a natural class of jump processes on compact ultrametric spaces - studied in current work of Bendikov, Girgor'yan and Pittet - and nearest neighbour walks on trees. Processes of this type have appeared in recent work of Kigami. Every compact ultrametric space arises as the boundary of a locally finite tree. The duality arises via the Dirichlet forms: one on the tree associated with a random walk and the other on the boundary of the tree, which is given in terms of the Naïm kernel. Here, it is explained that up to a linear time change by a unique constant, there is a one-to-one correspondence between the above processes and Dirichlet regular random walks.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Brownian motion and Harmonic functions on Sol(p,q)

The Lie group Sol(p,q) is the semidirect product induced by the action of the real numbers R on the plane R^2 which is given by (x,y) --> (exp{p z} x, exp{-q z} y), where z is in R. Viewing Sol(p,q) as a 3-dimensional manifold, it carries a natural Riemannian metric and Laplace-Beltrami operator. We add a linear drift term in the z-variable to the latter, and study the associated Brownian motion with drift. We derive a central limit theorem and compute the rate of escape. Also, we introduce the natural geometric compactification of Sol(p,q) and explain how Brownian motion converges almost surely to the boundary in the resulting topology. We also study all positive harmonic functions for the Laplacian with drift, and determine explicitly all minimal harmonic functions. All this is carried out with a strong emphasis on understanding and using the geometric features of Sol(p,q), and in particular the fact that it can be described as the horocyclic product of two hyperbolic planes with curvatures -p^2 and -q^2, respectively.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Entropy sensitivity of languages defined by infinite automata, via Markov chains with forbidden transitions

A language L over a finite alphabet is growth-sensitive (or entropy sensitive) if forbidding any set of subwords F yields a sub-language L^F whose exponential growth rate (entropy) is smaller than that of L. Let (X, E, l) be an infinite, oriented, labelled graph. Considering the graph as an (infinite) automaton, we associate with any pair of vertices x,y in X the language consisting of all words that can be read as the labels along some path from x to y. Under suitable, general assumptions we prove that these languages are growth-sensitive. This is based on using Markov chains with forbidden transitions.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Stochastic dynamical systems with weak contractivity properties (with a chapter featuring results of Martin Benda)

Consider a proper metric space X and a sequence of i.i.d. random continuous mappings F_n from X to X. It induces the stochastic dynamical system (SDS) X_n^x = F_n(X_{n-1}^x) starting at x in X. In this paper, we study existence and uniqueness of invariant measures, as well as recurrence and ergodicity of this process. In the first part, we elaborate, improve and complete the unpublished work of Martin Benda on local contractivity, which merits publicity and provides an important tool for studying stochastic iterations. We consider the case when the F_n are contractions and, in particular, discuss recurrence criteria and their sharpness for reflected random walk. In the second part, we consider the case where the F_n are Lipschitz mappings. The main results concern the case when the associated Lipschitz constants are log-centered. Prinicpal tools are the Chacon-Ornstein theorem and a hyperbolic extension of the space X as well as the process (X_n^x). The results are applied to the reflected affine stochastic recursion on the non-negative half-line.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

Context-free pairs of groups I: Context-free pairs and graphs

Let $G$ be a finitely generated group, $A$ a finite set of generators and $K$ a subgroup of $G$. We call the pair $(G,K)$ context-free if the set of all words over $A$ that reduce in $G$ to an element of $K$ is a context-free language. When $K$ is trivial, $G$ itself is called context-free; context-free groups have been classified more than 20 years ago in celebrated work of Muller and Schupp as the virtually free groups. Here, we derive some basic properties of such group pairs. Context-freeness is independent of the choice of the generating set. It is preserved under finite index modifications of $G$ and finite index enlargements of $K$. If $G$ is virtually free and $K$ is finitely generated then $(G,K)$ is context-free. A basic tool is the following: $(G,K)$ is context-free if and only if the Schreier graph of $(G,K)$ with respect to $A$ is a context-free graph.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

Context-free pairs of groups. II - cuts, tree sets, and random walks

This is a continuation of the study, begun by Ceccherini-Silberstein and Woess, of context-free pairs of groups and the related context-free graphs in the sense of Muller and Schupp. Instead of the cones (connected components with respect to deletion of finite balls with respect to the graph metric), a more general approach to context-free graphs is proposed via tree sets consisting of cuts of the graph, and associated structure trees. The existence of tree sets with certain "good" properties is studied. With a tree set, a natural context-free grammar is associated. These investigations of the structure of context free pairs, resp. graphs are then applied to study random walk asymptotics via complex analysis.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

The heat semigroup and Brownian motion on strip complexes

We introduce the notion of strip complex. A strip complex is a special type of complex obtained by gluing "strips" along their natural boundaries according to a given graph structure. The most familiar example is the one dimensional complex classically associated with a graph, in which case the strips are simply copies of the unit interval (our setup actually allows for variable edge length). A leading key example is treebolic space, a geometric object studied in a number of recent articles, which arises as a horocyclic product of a metric tree with the hyperbolic plane. In this case, the graph is a regular tree, the strips are the closed unit interval times the real line, and each strip is equipped with the hyperbolic geometry of a specific strip in upper half plane. We consider natural families of Dirichlet forms on a general strip complex and show that the associated heat kernels and harmonic functions have very strong smoothness properties. We study questions such as essential selfadjointness of the underlying differential operator acting on a suitable space of smooth functions satisfying a Kirchoff type condition at points where the strip complex bifurcates. Compatibility with projections that arise from proper group actions is also considered.

0 citations0 reviewsNo code linkedOpen access
preprint2008arXiv

On the spectrum of lamplighter groups and percolation clusters

Let $G$ be a finitely generated group and $X$ its Cayley graph with respect to a finite, symmetric generating set $S$. Furthermore, let $H$ be a finite group and $H \wr G$ the lamplighter group (wreath product) over $G$ with group of "lamps" $H$. We show that the spectral measure (Plancherel measure) of any symmetric "switch--walk--switch" random walk on $H \wr G$ coincides with the expected spectral measure (integrated density of states) of the random walk with absorbing boundary on the cluster of the group identity for Bernoulli site percolation on $X$ with parameter $p = 1/|H|$. The return probabilities of the lamplighter random walk coincide with the expected (annealed) return probabilites on the percolation cluster. In particular, if the clusters of percolation with parameter $p$ are almost surely finite then the spectrum of the lamplighter group is pure point. This generalizes results of Grigorchuk and Zuk, resp. Dicks and Schick regarding the case when $G$ is infinite cyclic. Analogous results relate bond percolation with another lamplighter random walk. In general, the integrated density of states of site (or bond) percolation with arbitrary parameter $p$ is always related with the Plancherel measure of a convolution operator by a signed measure on $H \wr G$, where $H = Z$ or another suitable group.

0 citations0 reviewsNo code linkedOpen access
preprint2006arXiv

Horocyclic products of trees

Let T_1,..., T_d be homogeneous trees with degrees q_1+1,..., q_d+1>=3, respectively. For each tree, let h:T_j->Z be the Busemann function with respect to a fixed boundary point (end). Its level sets are the horocycles. The horocyclic product of T_1,...,T_d is the graph DL(q_1,...,q_d) consisting of all d-tuples x_1...x_d in T_1x...xT_d with h(x_1)+...+h(x_d)=0, equipped with a natural neighbourhood relation. In the present paper, we explore the geometric, algebraic, analytic and probabilistic properties of these graphs and their isometry groups. If d=2 and q_1=q_2=q then we obtain a Cayley graph of the lamplighter group (wreath product) (Z/qZ) wr Z. If d=3 and q_1=q_2=q_3=q then DL is the Cayley graph of a finitely presented group into which the lamplighter group embeds naturally. Also when d>=4 and q_1=...=q_d=q is such that each prime power in the decomposition of q is larger than d-1, we show that DL is a Cayley graph of a finitely presented group. This group is of type F_{d-1}, but not F_d. It is not automatic, but it is an automata group in most cases. On the other hand, when the q_j do not all coincide, DL(q_1,...,q_d) is a vertex-transitive graph, but is not the Cayley graph of a finitely generated group. Indeed, it does not even admit a group action with finitely many orbits and finite point stabilizers. The l^2-spectrum of the ``simple random walk'' operator on DL is always pure point. When d=2, it is known explicitly from previous work, while for d=3 we compute it explicitly. Finally, we determine the Poisson boundary of a large class of group-invariant random walks on DL. It coincides with a part of the geometric boundary of DL.

0 citations0 reviewsNo code linkedOpen access
preprint2006arXiv

The Poisson boundary of lamplighter random walks on trees

Let T be the homogeneous tree with degree and G a finitely generated group whose Cayley graph is T. The associated lamplighter group is the wreath product of the cyclic group of order r with G. For a large class of random walks on this group, we prove almost sure convergence to a natural geometric boundary. If the probability law governing the random walk has finite first moment, then the probability space formed by this geometric boundary together with the limit distribution of the random walk is proved to be maximal, that is, the Poisson boundary. We also prove that the Dirichlet problem at infinity is solvable for continuous functions on the active part of the boundary, if the lamplighter "operates at bounded range".

0 citations0 reviewsNo code linkedOpen access
preprint2005arXiv

Positive harmonic functions for semi-isotropic random walks on trees, lamplighter groups, and DL-graphs

We determine all positive harmonic functions for a large class of "semi-isotropic" random walks on the lamplighter group, i.e., the wreath product of the cyclic group of order q with the infinite cyclic group. This is possible via the geometric realization of a Cayley graph of that group as the Diestel-Leader graph DL(q,q). More generally, DL(q,r) is the horocyclic product of two homogeneous trees with respective degrees $q+1$ and $r+1$, and our result applies to all DL-graphs. This is based on a careful study of the minimal harmonic functions for semi-isotropic walks on trees.

0 citations0 reviewsNo code linkedOpen access
preprint2005arXiv

The spectrum of the averaging operator on a network (metric graph)

A network is a countable, connected graph X viewed as a one-complex, where each edge [x,y]=[y,x] (x,y in X^0, the vertex set) is a copy of the unit interval within the graph's one-skeleton X^1 and is assigned a positive conductance c(xy). A reference "Lebesgue" measure on X^1 is built up by using Lebesgue measure with total mass c(xy) on each edge [x,y]. There are three natural operators on X : the transition operator P acting on functions on X^0 (the reversible Markov chain associated with the conductances), the averaging operator A over spheres of radius 1 on X^1, and the Laplace operator on X^1 (with Kirchhoff conditions weighted by c(.) at the vertices). The relation between the l^2-spectrum of P and the H^2-spectrum of the Laplacian was described by Cattaneo (Mh. Math. 124, 1997). In this paper we describe the relation between the l^2-spectrum of P and the L^2-spectrum of A.

0 citations0 reviewsNo code linkedOpen access
preprint2004arXiv

Green kernel estimates and the full Martin boundary for random walks on lamplighter groups and Diestel-Leader graphs

We determine the precise asymptotic behaviour (in space) of the Green kernel of simple random walk with drift on the Diestel-Leader graph $DL(q,r)$, where $q,r \ge 2$. The latter is the horocyclic product of two homogeneous trees with respective degrees $q+1$ and $r+1$. When $q=r$, it is the Cayley graph of the wreath product (lamplighter group) ${\mathbb Z}_q \wr {\mathbb Z}$ with respect to a natural set of generators. We describe the full Martin compactification of these random walks on $DL$-graphs and, in particular, lamplighter groups. This completes and provides a better approach to previous results of Woess, who has determined all minimal positive harmonic functions.

0 citations0 reviewsNo code linkedOpen access
preprint2004arXiv

Lamplighters, Diestel-Leader graphs, random walks, and harmonic functions

The lamplighter group over $\mathbb Z$ is the wreath product $\mathbb Z_q \wr \mathbb Z$. With respect to a natural generating set, its Cayley graph is the Diestel-Leader graph $DL(q,q)$. We study harmonic functions for the "simple" Laplacian on this graph, and more generally, for a class of random walks on $DL(q,r)$, where $q,r \ge 2$. The DL-graphs are horocyclic products of two trees, and we give a full description of all positive harmonic functions in terms of the boundaries of these two trees. In particular, we determine the minimal Martin boundary, that is, the set of minimal positive harmonic functions.

0 citations0 reviewsNo code linkedOpen access
preprint2004arXiv

Non-backtracking random walks and cogrowth of graphs

Let X be a locally finite, connected graph without vertices of degree 1. Non-backtracking random walk moves at each step with equal probability to one of the "forward" neighbours of the actual state, i.e., it does not go back along the preceding edge to the preceding state. This is not a Markov chain, but can be turned into a Markov chain whose state space is the set of oriented edges of X. Thus we obtain for infinite X that the n-step non-backtracking transition probabilities tend to zero, and we can also compute their limit when X is finite. This provides a short proof of old results concerning cogrowth of groups, and makes the extension of that result to arbitrary regular graphs rigorous. Even when X is non-regular, but "small cycles are dense" in X, we show that the graph X is non-amenable if and only if the non-backtracking n-step transition probabilities decay exponentially fast. This is a partial generalization of the cogrowth criterion for regular graphs which comprises the original cogrowth criterion for finitely generated groups of Grigorchuk and Cohen.

0 citations0 reviewsNo code linkedOpen access