Amenable group actions on infinite graphs

Dedicated to Professor Gert Sabidussi on the occasion of his sixtieth birthday     

Poisson approximation for non-backtracking random walks

Random walks on expander graphs were thoroughly studied, with the important motivation that, under some natural conditions, these walks mix quickly and provide an efficient method of sampling the vertices of a graph. The authors of [3] studied non-backtracking random walks on regular graphs, and showed that their mixing rate may be up to twice as fast as that of the simple random walk. As an application, they showed that the maximal number of visits to a vertex, made by a non-backtracking random walk of length n on a high-girth n-vertex regular expander, is typically (1+o(1)))log n/log log n, as in the case of the balls and bins experiment. They further asked whether one can establish the precise distribution of the visits such a walk makes. In this work, we answer the above question by combining a generalized form of Brun’s sieve with some extensions of the ideas in [3]. Let N _t denote the number of vertices visited precisely t times by a non-backtracking random walk of length n on a regular n-vertex expander of fixed degree and girth g. We prove that if g = ω(1), then for any fixed t, N _t /n is typically 1/et! + o(1). Furthermore, if g = Ω(log log n), then N _t /n is typically 1+o(1)/et! niformly on all t ≤ (1 − o(1)) log n/log log n and 0 for all t ≥ (1 + o(1)) log n/log log n. In particular, we obtain the above result on the typical maximal number of visits to a single vertex, with an improved threshold window. The essence of the proof lies in showing that variables counting the number of visits to a set of sufficiently distant vertices are asymptotically independent Poisson variables.     

Spectra of ergodic group actions

LetG be a locally compact second countable abelian group, (X, μ) aσ-finite Lebesgue space, and (g, x) →gx a non-singular, properly ergodic action ofG on (X, μ). Let furthermore Γ be the character group ofG and let Sp(G, X) ⊂ Γ denote theL ^∞-spectrum ofG on (X, μ). It has been shown in [5] that Sp(G, X) is a Borel subgroup of Γ and thatσ (Sp(G, X))<1 for every probability measureσ on Γ with lim sup_g→∞Re (g)<1, where is the Fourier transform ofσ. In this note we prove the following converse: ifσ is a probability measure on Γ with lim sup_g→∞Re (g)<1 (g)=1 then there exists a non-singular, properly ergodic action ofG on (X, μ) withσ(Sp(G, X))=1.     

On the cohomology of ergodic group actions

We consider three problems concerning cocycles of ergodic group actions: behavior of cohomology under the restriction of an ergodic semi-simple Lie group action to a lattice subgroup; “compactness” of bounded cocyles; and the relation of relative almost periodicity to relative discrete spectrum for extensions of ergodic actions.     

Martin boundaries of random walks on Fuchsian groups

Let Γ be a finitely generated non-elementary Fuchsian group, and let μ be a probability measure with finite support on Γ such that supp μ generates Γ as a semigroup. If Γ contains no parabolic elements we show that for all but a small number of co-compact Γ, the Martin boundaryM of the random walk on Γ with distribution μ can be identified with the limit set Λ of Γ. If Γ has cusps, we prove that Γ can be deformed into a group Γ', abstractly isomorphic to Γ, such thatM can be identified with Λ', the limit set of Γ'. Our method uses the identification of Λ with a certain set of infinite reduced words in the generators of Γ described in [15]. The harmonic measure ν (ν is the hitting distribution of random paths in Γ on Λ) is a Gibbs measure on this space of infinite words, and the Poisson boundary of Γ, μ can be identified with Λ, ν.     

Cocycles and the structure of ergodic group actions

We show, for a large class of groups, the existence of cocycles taking values in these groups and which define ergodic skew products. We apply this to prove a generalization of Ambrose’s representation theorem for ergodic actions of these groups.     

Maximal ergodic theorems for some group actions

We prove maximal ergodic inequalities for a sequence of operators and for their averages in the noncommutative Lp-space. We also obtain the corresponding individual ergodic theorems. Applying these results to actions of a free group on a von Neumann algebra, we get noncommutative analogues of maximal ergodic inequalities and pointwise ergodic theorems of Nevo-Stein.     

Large deviations for Poisson systems of independent random walks

Summary We prove large deviation theorems for occupation time functionals of independent random walks started from a Poisson field on Z ^d. In dimensions 1 and 2 the large deviation tails are larger than exponential. Exact asymptotics are derived.Partially supported by the National Science Foundation under Grant MCS 81-02131 and MCS 81-00256Alfred P. Sloan Research Fellow     

The Poisson boundary of lamplighter random walks on trees

Let be the homogeneous tree with degree q + 1 ≥ 3 and a finitely generated group whose Cayley graph is . The associated lamplighter group is the wreath product , where is a finite group. 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”. Supported by ESF program RDSES and by Austrian Science Fund (FWF) P15577.     

Space-time boundaries for random walks obtained from diffuse measures

We define a “space-time” boundary (referring to space-time harmonic functions) to encompass random walks obtained from compactly supported diffuse measures on Euclidean space, and then prove that in many cases, a qualitative analogue of the Ney-Spitzer theorem (1966) holds, namely that the space-time boundary admits a natural identification with the convex hull of the support of the measure. This can also be interpreted as a generalization to the diffuse case of the weighted moment mapping of algebraic geometry. In many more cases, a weaker analogue holds, identifying the faithful extreme space-time harmonic functions with the interior of the convex body. Partially supported by an operating grant from NSERC (Canada).     

On the connection between polynomial and Poisson plans of random walks

In the present paper we consider the relation between the distributions of probability of attaining the boundary point of a polynomial plan and that of a Poisson plan. This relation is used to compare the moments of the functions of the boundary point coordinates, the closedness and completeness conditions of plans, the classes of the unbiased estimates and the unbiased estimated functions of the unknown parameters. Translated fromStatisticheskie Metody Otsenivaniya i Proverki Gipotez, pp. 144–156, Perm, 1991.     

A note on the Poisson boundary of lamplighter random walks

The main goal of this paper is to determine the Poisson boundary of lamplighter random walks over a general class of discrete groups Γ endowed with a “rich” boundary. The starting point is the Strip Criterion of identification of the Poisson boundary for random walks on discrete groups due to Kaimanovich (Ann. Math. 152:659–692, 2000). A geometrical method for constructing the strip as a subset of the lamplighter group \mathbb Z₂\wr G{\mathbb {Z}_{2}\wr \Gamma} starting with a “smaller” strip in the group Γ is developed. Then, this method is applied to several classes of base groups Γ: groups with infinitely many ends, hyperbolic groups in the sense of Gromov, and Euclidean lattices. We show that under suitable hypothesis the Poisson boundary for a class of random walks on lamplighter groups is the space of infinite limit configurations.     

A note on the Poisson boundary of lamplighter random walks

The main goal of this paper is to determine the Poisson boundary of lamplighter random walks over a general class of discrete groups Γ endowed with a “rich” boundary. The starting point is the Strip Criterion of identification of the Poisson boundary for random walks on discrete groups due to Kaimanovich (Ann. Math. 152:659–692, 2000). A geometrical method for constructing the strip as a subset of the lamplighter group ${\mathbb {Z}_{2}\wr \Gamma}$ starting with a “smaller” strip in the group Γ is developed. Then, this method is applied to several classes of base groups Γ: groups with infinitely many ends, hyperbolic groups in the sense of Gromov, and Euclidean lattices. We show that under suitable hypothesis the Poisson boundary for a class of random walks on lamplighter groups is the space of infinite limit configurations.     

Some ergodic and rigidity properties of discrete Heisenberg group actions

The goal of this paper is to study ergodic and rigidity properties of smooth actions of the discrete Heisenberg group \(\mathcal{H}\). We establish the decomposition of the tangent space of any C^∞ compact Riemannian manifold M for Lyapunov exponents, and show that all Lyapunov exponents for the central elements are zero. We obtain that if an \(\mathcal{H}\) action contains an Anosov element, then under certain conditions on the eigenvalues of this element, the action of each central element is of finite order. In particular, there is no faithful codimension one Anosov Heisenberg group action on any compact manifold, and there is no faithful codimension two Anosov Heisenberg group action on tori. In addition, we show smooth local rigidity for higher rank ergodic \(\mathcal{H}\) actions by toral automorphisms, using a generalization of the KAM (Kolmogorov–Arnold–Moser) iterative scheme.     

Length of clustering algorithms based on random walks with an application to neuroscience

In this paper we show how the notions of conductance and cutoff can be used to determine the length of the random walks in some clustering algorithms. We consider graphs which are globally sparse but locally dense. They present a community structure: there exists a partition of the set of vertices into subsets which display strong internal connections but few links between each other. Using a distance between nodes built on random walks we consider a hierarchical clustering algorithm which provides a most appropriate partition. The length of these random walks has to be chosen in advance and has to be appropriate. Finally, we introduce an extension of this clustering algorithm to dynamical sequences of graphs on the same set of vertices.     

The Poisson Boundary of Amenable Extensions

 We obtain two new criteria of amenability of a closed normal subgroup H in a locally compact group G. The first one is formulated in terms of convergence of convolutions of probability measures on G, and the second one in terms of the Poisson boundaries of random walks on G and on the quotient group G/H. Received 10 April 2001; in revised form 18 December 2001     

Actions of large semigroups and random walks on isometric extensions of boundaries

Let G be a real algebraic semi-simple group, X an isometric extension of the flag space of G by a compact group C. We assume that G is topologically transitive on X. We consider a closed sub-semigroup T of G and a probability measure μ on T such that T is Zariski-dense in G and the support of μ generates T. We show that there is a finite number of T-invariant minimal subsets in X and these minimal subsets are the supports of the extremal μ-stationary measures on X. We describe the structure of these measures, we show the conditional equidistribution on C of the μ-random walk and we calculate the algebraic hull of the corresponding cocycle. A certain subgroup generated by the “spectrum” of T can be calculated and plays an essential role in the proofs.     

Amenable actions and almost invariant sets

In this paper, we study the connections between properties of the action of a countable group on a countable set and the ergodic theoretic properties of the corresponding generalized Bernoulli shift, i.e., the corresponding shift action of on , where is a measure space. In particular, we show that the action of on is amenable iff the shift has almost invariant sets.