Random Walks on Trees with Finitely Many Cone Types

This paper is devoted to the study of random walks on infinite trees with finitely many cone types (also called periodic trees). We consider nearest neighbour random walks with probabilities adapted to the cone structure of the tree, which include in particular the well studied classes of simple and homesick random walks. We give a simple criterion for transience or recurrence of the random walk and prove that the spectral radius is equal to 1 if and only if the random walk is recurrent. Furthermore, we study the asymptotic behaviour of return probabilitites and prove a local limit theorem. In the transient case, we also prove a law of large numbers and compute the rate of escape of the random walk to infinity, as well as prove a central limit theorem. Finally, we describe the structure of the boundary process and explain its connection with the random walk.     

Positive Discrete Spectrum of the Evolutionary Operator of Supercritical Branching Walks with Heavy Tails

We consider a continuous-time symmetric supercritical branching random walk on a multidimensional lattice with a finite set of the particle generation centres, i.e. branching sources. The main object of study is the evolutionary operator for the mean number of particles both at an arbitrary point and on the entire lattice. The existence of positive eigenvalues in the spectrum of an evolutionary operator results in an exponential growth of the number of particles in branching random walks, called supercritical in the such case. For supercritical branching random walks, it is shown that the amount of positive eigenvalues of the evolutionary operator, counting their multiplicity, does not exceed the amount of branching sources on the lattice, while the maximal of these eigenvalues is always simple. We demonstrate that the appearance of multiple lower eigenvalues in the spectrum of the evolutionary operator can be caused by a kind of ‘symmetry’ in the spatial configuration of branching sources. The presented results are based on Green’s function representation of transition probabilities of an underlying random walk and cover not only the case of the finite variance of jumps but also a less studied case of infinite variance of jumps.     

Tubular recurrence

We introduce the directed-edge-reinforced random walk and prove that the process is equivalent to a random walk in random environment. Using Oseledec"s multiplicative ergodic theorem, we obtain recurrence and transience criteria for random walks in random environment on graphs with a certain linear structure and apply them to directed-edge-reinforced random walks. This revised version was published online in August 2006 with corrections to the Cover Date.     

Tree-indexed random walks on groups and first passage percolation

Summary Suppose that i.i.d. random variables are attached to the edges of an infinite tree. When the tree is large enough, the partial sumsS along some of its infinite paths will exhibit behavior atypical for an ordinary random walk. This principle has appeared in works on branching random walks, first-passage percolation, and RWRE on trees. We establish further quantitative versions of this principle, which are applicable in these settings. In particular, different notions of speed for such a tree-indexed walk correspond to different dimension notions for trees. Finally, if the labeling variables take values in a group, then properties of the group (e.g., polynomial growth or a nontrivial Poisson boundary) are reflected in the sample-path behavior of the resulting tree-indexed walk.Partially supported by a grant from the Landau Center for Mathematical AnalysisPartially supported by NSF grant DMS-921 3595     

n维有向de Bruijn图和无向de Bruijn图上的随机游动

本文对有向和无向de Bruijn图上的随机游动进行了研究，得出了有向de Bruijn图上简单随机游动任意两点之间平均击中时间的显式表达式，并证明了有向和无向de Bruijn图上随机游动的快速收敛性。     

Displacement exponent for loop-erased random walk on the Sierpiński gasket

We prove that loop-erased random walks on the finite pre-Sierpiński gaskets can be extended to a loop-erased random walk on the infinite pre-Sierpiński gasket by using the ‘erasing-larger-loops-first’ method, and obtain the asymptotic behavior of the walk as the number of steps increases, in particular, the displacement exponent and a law of the iterated logarithm.     

A weakly supercritical mode in a branching random walk

The case of weakly supercritical branching random walks is considered. A theorem on asymptotic behavior of the eigenvalue of the operator defining the process is obtained for this case. Analogues of the theorems on asymptotic behavior of the Green function under large deviations of a branching random walk and asymptotic behavior of the spread front of population of particles are established for the case of a simple symmetric branching random walk over a many-dimensional lattice. The constants for these theorems are exactly determined in terms of parameters of walking and branching.     

The Branching-Ruin Number and the Critical Parameter of Once-Reinforced Random Walk on Trees

The motivation for this paper is the study of the phase transition for recurrence/ transience of a class of self-interacting random walks on trees, which includes the once-reinforced random walk. For this purpose, we define a quantity, which we call the branching-ruin number of a tree, which provides (in the spirit of Furstenberg [11] and Lyons [13]) a natural way to measure trees with polynomial growth. We prove that the branching-ruin number of a tree is equal to the critical parameter for the recurrence/transience of the once-reinforced random walk. We define a sharp and effective (i.e., computable) criterion characterizing the recurrence/transience of a larger class of self-interacting walks on trees, providing the complete picture for their phase transition. © 2019 Wiley Periodicals, Inc.     

Asymptotic direction for random walks in random environments

In this paper we study the existence of an asymptotic direction for random walks in random i.i.d. environments (RWRE). We prove that if the set of directions where the walk is transient contains a non-empty open set, the walk admits an asymptotic direction. The main tool to obtain this result is the construction of a renewal structure with cones. We also prove that RWRE admits at most two opposite asymptotic directions.     

The survival of branching annihilating random walk

Summary Branching annihilating random walk is an interacting particle system on . As time evolves, particles execute random walks and branch, and disappear when they meet other particles. It is shown here that starting from a finite number of particles, the system will survive with positive probability if the random walk rate is low enough relative to the branching rate, but will die out with probability one if the random walk rate is high. Since the branching annihilating random walk is non-attractive, standard techniques usually employed for interacting particle systems are not applicable. Instead, a modification of a contour argument by Gray and Griffeath is used.     

On the norms of group-invariant transition operators on graphs

In this paper we consider reversible random walks on an infinite grapin, invariant under the action of a closed subgroup of automorphisms which acts with a finite number of orbits on the vertex-set. Thel ²-norm (spectral radius) of the simple random walk is equal to one if and only if the group is both amenable and unimodular, and this also holds for arbitrary random walks with bounded invariant measure. In general, the norm is bounded above by the Perron-Frobenius eigenvalue of a finite matrix, and this bound is attained if and only if the group is both amenable and unimodular.     

Biased random walks on Galton–Watson trees

Summary. We consider random walks with a bias toward the root on the family tree T of a supercritical Galton–Watson branching process and show that the speed is positive whenever the walk is transient. The corresponding harmonic measures are carried by subsets of the boundary of dimension smaller than that of the whole boundary. When the bias is directed away from the root and the extinction probability is positive, the speed may be zero even though the walk is transient; the critical bias for positive speed is determined. Received: 7 July 1995 / In revised form: 9 January 1996     

Limit distributions for the number of particles in branching random walks

We study branching random walks with continuous time. Particles performing a random walk on ?², are allowed to be born and die only at the origin. It is assumed that the offspring reproduction law at the branching source is critical and the random walk outside the source is homogeneous and symmetric. Given particles at the origin, we prove a conditional limit theorem for the joint distribution of suitably normalized numbers of particles at the source and outside it as time unboundedly increases. As a consequence, we establish the asymptotic independence of such random variables.     

The heavy range of randomly biased walks on trees

We focus on recurrent random walks in random environment (RWRE) on Galton–Watson trees. The range of these walks, that is the number of sites visited at some fixed time, has been studied in three different papers Andreoletti and Chen (2018), Aïdékon and de Raphélis (2017) and de Raphélis (2016). Here we study the heavy range: the number of edges frequently visited by the walk. The asymptotic behavior of this process when the number of visits is a power of the number of steps of the walk is given for all recurrent cases. It turns out that this heavy range plays a crucial role in the rate of convergence of an estimator of the environment from a single trajectory of the RWRE.     

Scaling limit of local time of Sinai’s random walk

We prove that the local times of a sequence of Sinai’s random walks converge to those of Brox’s diffusion by proper scaling. Our proof is based on the intrinsic branching structure of the random walk and the convergence of the branching processes in random environment.     

Nombre de branchement d’un pseudogroupe

Lyons has defined an average number of branches per vertex of an infinite locally finite rooted tree. This number has an important role in several probabilistic processes such as random walk and percolation. In this paper, we extend the notion of branching number to any measurable graphed pseudogroup of finite type acting on a probability space. We prove that such a pseudogroup is Liouvillian (i.e. almost every orbit does not admit non-constant bounded harmonic functions) if its branching number is equal to 1. In order to prove that this actually generalizes results of C. Series and V. Kaimanovich on equivalence relations with polynomial and subexponential growth, we describe an example of minimal lamination whose holonomy pseudogroup has exponential growth and branching number equal to 1.     

Nombre de branchement d’un pseudogroupe

Lyons has defined an average number of branches per vertex of an infinite locally finite rooted tree. This number has an important role in several probabilistic processes such as random walk and percolation. In this paper, we extend the notion of branching number to any measurable graphed pseudogroup of finite type acting on a probability space. We prove that such a pseudogroup is Liouvillian (i.e. almost every orbit does not admit non-constant bounded harmonic functions) if its branching number is equal to 1. In order to prove that this actually generalizes results of C. Series and V. Kaimanovich on equivalence relations with polynomial and subexponential growth, we describe an example of minimal lamination whose holonomy pseudogroup has exponential growth and branching number equal to 1.     

Hitting times with taboo for a random walk

For a symmetric homogeneous and irreducible random walk on the d-dimensional integer lattice, which have a finite variance of jumps, we study passage times (taking values in [0,??]) determined by a starting point x, a hitting state y, and a taboo state z. We find the probability that these passage times are finite, and study the distribution tail. In particular, it turns out that, for the above-mentioned random walks on ? ^d except for a simple random walk on ?, the order of the distribution tail decrease is specified by dimension d only. In contrast, for a simple random walk on ?, the asymptotic properties of hitting times with taboo essentially depend on mutual location of the points x, y, and z. These problems originated in recent study of a branching random walk on ? ^d with a single source of branching.