Random walks on finite rank solvable groups

We establish the lower bound p _2t (e,e)exp(-t ^1/3), for the large times asymptotic behaviours of the probabilities p _2t (e,e) of return to the origin at even times 2t, for random walks associated with finite symmetric generating sets of solvable groups of finite Prüfer rank. (A group has finite Prüfer rank if there is an integer r, such that any of its finitely generated subgroup admits a generating set of cardinality less or equal to r.) Mathematics Subject Classification (2000) 20F16, 20F69, 82B41     

Random walks on free products of cyclic groups

Let G be a free product of a finite family of finite groups,with the set of generators being formed by the union of thefinite groups. We consider a transient nearest-neighbour randomwalk on G. We give a new proof of the fact that the harmonicmeasure is a special Markovian measure entirely determined bya finite set of polynomial equations. We show that in severalsimple cases of interest, the polynomial equations can be explicitlysolved to get closed form formulae for the drift. The examplesconsidered are /2 /3, /3 /3, /k /k and the Hecke groups /2 /k.We also use these various examples to study Vershik's notionof extremal generators, which is based on the relation betweenthe drift, the entropy and the growth of the group.     

Random walks on groups

A finite group G is partitioned into nonempty disjoint subsets C₀, C₁,…,C_m such that for every g₁∈C_i the number of ordered pairs (g₂,g₃) for which g₂∈C_ν,g₃∈C_j, and g₁g₂ = g₃ is independent of the particular choice of g₁. A sequence of mutually independent random elements γ₀, γ₁,…, γ_n,… is chosen in G in such a way that for n = 1,2,… the probability $\text{P}\text{{γ}{}_{\mathrm{n}}\text{= g}}$ depends only on the class C_ν which contains g. Let ξ_n = jif γ₀γ₁?γ_n∈C_j. Then $\text{{ξ}{}_{\mathrm{n}}\text{; n ≧ 0}}$ is a homogeneous Markov chain with state space I = {0,1,…,m}. The aim of this paper is to determine the n-step transition probabilities of the Markov chain $\text{{ξ}{}_{\mathrm{n}}\text{; n ≧ 0}}$. The results derived in this paper lead also to a probabilistic interpretation and a generalization of group characters.     

Random walks on abelian-by-cyclic groups

We describe the large time asymptotic behaviors of the probabilities of return to the origin associated to finite symmetric generating sets of abelian-by-cyclic groups. We characterize the different asymptotic behaviors by simple algebraic properties of the groups.

     

Random walks in random environments on metric groups

Random walks in random environments on countable metric groups with bounded jumps of the walking particle are considered. The transition probabilities of such a random walk from a pointx εG (whereG is the group in question) are described by a vectorp(x) ε ℝ^|W| (whereW ⊏G is fixed and |W|<∞). The set {p(x),x εG} is assumed to consist of independent identically distributed random vectors. A sufficient condition for this random walk to be transient is found. As an example, the groups ℤ ^d , free groups, and the free product of finitely many cyclic groups of second order are considered. Translated fromMatematicheskie Zametki, Vol. 67, No. 1, pp. 129–135, January, 2000.     

Occurrence problem for free solvable groups

We study the problem on the existence of an algorithm verifying whether systems of linear equations over a group ring of a free metabelian group are solvable. The occurrence problem for free solvable groups of derived length 3is proved undecidable. We give an example of a group with undecidable word problem which is finitely presented in a variety of solvable groups and is defined by the relations from the last commutator subgroup. Translated fromAlgebra i Logika, Vol. 34, No. 2, pp. 211-232, March-April, 1995.     

Random walks on compact groups and the existence of cocycles

We show that certain skew products in ergodic theory are isomorphic to the shifts defined by random walks. We conclude the existence of cocycles for any finite measure preserving ergodic automorphism or flow, taking values in an arbitrary compact group, which determine ergodic skew products.     

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 .     

Random walks in disordered systems with long-range transitions. Asymptotically exactly solvable models

Random-jump models of transport in disordered systems are studied. They are described by the master equationP=–AP, whereA is the generator of a spatially and temporally uniform random walk on a regular lattice, is a diagonal operator, and _xy = _{x xy} , where { _x } are independent non-negative bounded random variables having the same distribution. A detailed analysis is made of the case when the transition rates are due to an interaction of multipole type and _x have several negative first moments (model of isotropic random jumps with long-range transport). Methods are developed for constructing asymptotic expansions of the propagator for small values of the Laplace parameter and at large times. An expansion is also obtained by means of a functional integral. The influence of both the long-range interaction and the disorder of the medium on the establishment of the long-time asymptotic behavior is considered. A method of investigating systems with forced drift along a certain direction is suggested. Methods of transforming asymptotically exactly solvable problems and connections with other known systems and realistic models are discussed. An estimate is obtained of thel ₁ norm of the resolvent of a Markov process with countable set of states andl ₁-bounded generator.Institute of Theoretical and Experimental Physics. Translated from Teoreticheskaya i Matematicheskaya Fizika, Vol. 94, No. 3, pp. 496–514, March, 1993.     

Random walks,Kleinian groups,and bifurcation currents

Let (ρ _λ ) _λ∈Λ be a holomorphic family of representations of a finitely generated group G into PSL(2,ℂ), parameterized by a complex manifold Λ. We define a notion of bifurcation current in this context, that is, a positive closed current on Λ describing the bifurcations of this family of representations in a quantitative sense. It is the analogue of the bifurcation current introduced by DeMarco for holomorphic families of rational mappings on ℙ¹. Our definition relies on the theory of random products of matrices, so it depends on the choice of a probability measure μ on G.     

Random walks on graphs

In this paper the following Markov chains are considered: the state space is the set of vertices of a connected graph, and for each vertex the transition is always to an adjacent vertex, such that each of the adjacent vertices has the same probability. Detailed results are given on the expectation of recurrence times, of first-entrance times, and of symmetrized first-entrance times (called commuting times). The problem of characterizing all connected graphs for which the commuting time is constant over all pairs of adjacent vertices is solved almost completely.     

Random walks on amalgams

Let be a locally compact amalgam of compact groups. We use the action of on a suitable tree to study all random walks on which can be described as nearest neighbour random walks on the tree. In particular, we derive the asymptotic behaviour ofn-step transition probabilities.The second author was partially supported by CNR-research fellowship No. 212.223.     

Random walks on trees

The classical gambler's ruin problem, i.e., a random walk along a line may be viewed graph theoretically as a random walk along a path with the endpoints as absorbing states. This paper is an investigation of the natural generalization of this problem to that of a particle walking randomly on a tree with the endpoints as absorbing barriers. Expressions in terms of the graph structure are obtained from the probability of absorption at an endpoint e in a walk originating from a vertex v, as well as for the expected length of the walk.