Quasi-isometries between groups with infinitely many ends

Let G, F be finitely generated groups with infinitely many ends and let? be graph of groups decompositions of F, G such that all edge groups are finite and all vertex groups have at most one end. We show that G, F are quasi-isometric if and only if every one-ended vertex group of is quasi-isometric to some one-ended vertex group of and every one-ended vertex group of is quasi-isometric to some one-ended vertex group of?. From our proof it also follows that if G is any finitely generated group, of order at least three, the groups: and are all quasi-isometric. Received: April 7, 2000; revised version: October 6, 2000     

Markov processes of infinitely many nonintersecting random walks

Consider an N-dimensional Markov chain obtained from N one-dimensional random walks by Doob h-transform with the q-Vandermonde determinant. We prove that as N becomes large, these Markov chains converge to an infinite-dimensional Feller Markov process. The dynamical correlation functions of the limit process are determinantal with an explicit correlation kernel. The key idea is to identify random point processes on ${\mathbb Z}$ with q-Gibbs measures on Gelfand–Tsetlin schemes and construct Markov processes on the latter space. Independently, we analyze the large time behavior of PushASEP with finitely many particles and particle-dependent jump rates (it arises as a marginal of our dynamics on Gelfand–Tsetlin schemes). The asymptotics is given by a product of a marginal of the GUE-minor process and geometric distributions.     

A structure theorem for boundary-transitive graphs with infinitely many ends

We prove a structure theorem for locally finite connected graphsX with infinitely many ends admitting a non-compact group of automorphisms which is transitive in its action on the space of ends, Ω _X . For such a graphX, there is a uniquely determined biregular treeT (with both valencies finite), a continuous representationφ : Aut(X) → Aut(T) with compact kernel, an equivariant homeomorphism λ : Ω _X → Ω _T , and an equivariant map τ : Vert(X) → Vert(T) with finite fibers. Boundary-transitive trees are described, and some methods of constructing boundary-transitive graphs are discussed, as well as some examples.     

Finitely additive random walks on infinitely generated free groups

We consider any purely finitely additive probability measure supported on the generators of an infinitely generated free group and the Markov strategy with stationary transition probability . As well as for the case of random walks (with countably additive transition probability) on finitely generated free groups, we prove that all bounded sets are transient. Finally, we consider any finitely additive measure (supported on the group generators) and we prove that the classification of the state space depends only on the continuous part of .     

Boundaries and random walks on finitely generated infinite groups

We prove that almost every path of a random walk on a finitely generated nonamenable group converges in the compactification of the group introduced by W. J. Floyd. In fact, we consider the more general setting of ergodic cocycles of some semigroup of one-Lipschitz maps of a complete metric space with a boundary constructed following Gromov. We obtain in addition that when the Floyd boundary of a finitely generated group is non-trivial, then it is in fact maximal in the sense that it can be identified with the Poisson boundary of the group with reasonable measures. The proof relies on works of Kaimanovich together with visibility properties of Floyd boundaries. Furthermore, we discuss mean proximality of ϖΓ and a conjecture of McMullen. Lastly, related statements about the convergence of certain sequences of points, for example quasigeodesic rays or orbits of one-Lipschitz maps, are obtained.     

Coalescent random walks on graphs

Inspired by coalescent theory in biology, we introduce a stochastic model called “multi-person simple random walks” or “coalescent random walks” on a graph G. There are any finite number of persons distributed randomly at the vertices of G. In each step of this discrete time Markov chain, we randomly pick up a person and move it to a random adjacent vertex. To study this model, we introduce the tensor powers of graphs and the tensor products of Markov processes. Then the coalescent random walk on graph G becomes the simple random walk on a tensor power of G. We give estimates of expected number of steps for these persons to meet all together at a specific vertex. For regular graphs, our estimates are exact.     

Embedding finite graphs into graphs colored with infinitely many colors

We prove that for any cardinalτ and for any finite graphH there is a graphG such that for any coloring of the pairs of vertices ofG withτ colors there is always a copy ofH which is an induced subgraph ofG so that both the edges of the copy and the edges of the complement of the copy are monochromatic. Research supported by Hungarian National Science Foundation OTKA grant 1805.     

Random walks on random simple graphs

This paper looks at random regular simple graphs and considers nearest neighbor random walks on such graphs. This paper considers walks where the degree d of each vertex is around (log n)^a where a is a constant which is at least 2 and where n is the number of vertices. By extending techniques of Dou, this paper shows that for most such graphs, the position of the random walk becomes close to uniformly distributed after slightly more than log n/log d steps. This paper also gets similar results for the random graph G(n, p), where p = d/(n − 1). © 1996 John Wiley & Sons, Inc.     

Deterministic random walks on finite graphs

The rotor‐router model, also known as the Propp machine, is a deterministic process analogous to a random walk on a graph. Instead of distributing tokens to randomly chosen neighbors, the Propp machine deterministically serves the neighbors in a fixed order by associating to each vertex a “rotor‐router” pointing to one of its neighbors. This paper investigates the discrepancy at a single vertex between the number of tokens in the rotor‐router model and the expected number of tokens in a random walk, for finite graphs in general. We show that the discrepancy is bounded by O (mn) at any time for any initial configuration if the corresponding random walk is lazy and reversible, where n and m denote the numbers of nodes and edges, respectively. For a lower bound, we show examples of graphs and initial configurations for which the discrepancy at a single vertex is Ω(m) at any time (> 0). For some special graphs, namely hypercube skeletons and Johnson graphs, we give a polylogarithmic upper bound, in terms of the number of nodes, for the discrepancy. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 46,739–761, 2015     

Free groups and ends of graphs

Let X be a connected graph. An automorphism of X is said to be parabolic if it leaves no finite subset of vertices in X invariant and fixes precisely one end of X and hyperbolic if it leaves no finite subset of vertices in X invariant and fixes precisely two ends of X. Various questions concerning dynamics of parabolic and hyperbolic automorphisms are discussed.The set of ends which are fixed by some hyperbolic element of a group G acting on X is denoted by ?(G). If G contains a hyperbolic automorphism of X and G fixes no end of X, then G contains a free subgroup F such that ?(F) is dense in ?(G) with respect to the natural topology on the ends of X.As an application we obtain the following: A group which acts transitively on a connected graph and fixes no end has a free subgroup whose directions are dense in the end boundary.     

Maximum hitting time for random walks on graphs

For x and y vertices of a connected graph G, let T_G(x, y) denote the expected time before a random walk starting from x reaches y. We determine, for each n > 0, the n-vertex graph G and vertices x and y for which T_G(x, y) is maximized. the extremal graph consists of a clique on ?(2n + 1)/3?) (or ?)(2_n ? 2)/3?) vertices, including x, to which a path on the remaining vertices, ending in y, has been attached; the expected time T_G(x, y) to reach y from x in this graph is approximately 4_n³/27.     

A random environment for linearly edge-reinforced random walks on infinite graphs

We consider linearly edge-reinforced random walk on an arbitrary locally finite connected graph. It is shown that the process has the same distribution as a mixture of reversible Markov chains, determined by time-independent strictly positive weights on the edges. Furthermore, we prove bounds for the random weights, uniform, among others, in the size of the graph.      

Expected cover times of random walks on symmetric graphs

We give very simple proofs for an (N–1)H _N–1 lower bound and anN ² upper bound for the expected cover time of symmetric graphs.     

On the cover time of random walks on graphs

This article deals with random walks on arbitrary graphs. We consider the cover time of finite graphs. That is, we study the expected time needed for a random walk on a finite graph to visit every vertex at least once. We establish an upper bound ofO(n ²) for the expectation of the cover time for regular (or nearly regular) graphs. We prove a lower bound of (n logn) for the expected cover time for trees. We present examples showing all our bounds to be tight.Mike Saks was supported by NSF-DMS87-03541 and by AFOSR-0271. Jeff Kahn was supported by MCS-83-01867 and by AFOSR-0271.     

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 Λ, ν.     

Recurrent random walks on certain classes of groups

This article is divided into two parts: in the first we give some results about renewal and normality of a recurrent random walk (r.w.) on an abelian group, without the Harris hypothesis, which will extend the theorems of S.C. Port and C.J. Stone ([8]) to a larger class of functions. They are stated in the Theorems 1.14 and 1.15. The technique will be to approximate the recurrent r.w. by a Harris recurrent r.w., for which the recent results of A. Brunel and D. Revuz ([2–4]) hold.the second part the results of the first part are extended to a particular class of nonabelian groups.The author wishes to thank A. Brunel for several very useful conversations and suggestions.