Positive Harmonic Functions of Transformed Random Walks

Potential Analysis - In this paper, we will study the behavior of the space of positive harmonic functions associated with the random walk on a discrete group under the change of probability...     

Quenched Large Deviations for Multidimensional Random Walk in Random Environment with Holding Times

We consider a random walk in random environment with random holding times, that is, the random walk jumping to one of its nearest neighbors with some transition probability after a random holding time. Both the transition probabilities and the laws of the holding times are randomly distributed over the integer lattice. Our main result is a quenched large deviation principle for the position of the random walk. The rate function is given by the Legendre transform of the so-called Lyapunov exponents for the Laplace transform of the first passage time. By using this representation, we derive some asymptotics of the rate function in some special cases.     

Random walks on almost connected locally compact groups: Boundary and convergence

We prove that, given an arbitrary spread out probability measure μ on an almost connected locally compact second countable groupG, there exists a homogeneous spaceG/H, called the μ-boundary, such that the space of bounded μ-harmonic functions can be identified withL ^∞ (G/H). The μ-boundary is an amenable contractive homogeneous space. We also establish that the canonical projection onto the μ-boundary of the right random walk of law μ always converges in probability and, whenG is amenable, it converges almost surely. The μ-boundary can be characterised as the largest homogeneous space among those homogeneous spaces in which the canonical projection of the random walk converges in probability.     

An Interlacing Technique for Spectra of Random Walks and Its Application to Finite Percolation Clusters

A comparison technique for random walks on finite graphs is introduced, using the well-known interlacing method. It yields improved return probability bounds. A key feature is the incorporation of parts of the spectrum of the transition matrix other than just the principal eigenvalue. As an application, an upper bound of the expected return probability of a random walk with symmetric transition probabilities is found. In this case, the state space is a random partial graph of a regular graph of bounded geometry and transitive automorphism group. The law of the random edge-set is assumed to be invariant with respect to some transitive subgroup of the automorphism group (‘invariant percolation’). Given that this subgroup is unimodular, it is shown that this invariance strengthens the upper bound of the expected return probability, compared with standard bounds such as those derived from the Cheeger inequality. The improvement is monotone in the degree of the underlying transitive graph.     

First Passage Time Distribution for Linear Functions of a Random Walk

In this paper, theorems about asymptotic behavior of the local probabilities of crossing the linear boundaries by a perturbed random walk are proved.     

Random walk in mixed random environment without uniform ellipticity

We study a random walk in random environment on ?₊. The random environment is not homogeneous in law, but is a mixture of two kinds of site, one in asymptotically vanishing proportion. The two kinds of site are (i) points endowed with probabilities drawn from a symmetric distribution with heavy tails at 0 and 1, and (ii) “fast points” with a fixed systematic drift. Without these fast points, the model is related to the diffusion in heavy-tailed (“stable”) random potential studied by Schumacher and Singh; the fast points perturb that model. The two components compete to determine the behaviour of the random walk; we identify phase transitions in terms of the model parameters. We give conditions for recurrence and transience and prove almost sure bounds for the trajectories of the walk.     

Random walks on finite volume homogeneous spaces

Extending previous results by A. Eskin and G. Margulis, and answering their conjectures, we prove that a random walk on a finite volume homogeneous space is always recurrent as soon as the transition probability has finite exponential moments and its support generates a subgroup whose Zariski closure is semisimple.     

Random walks on graphs with a strong isoperimetric property

A random walk on a graph is a Markov chain whose state space consists of the vertices of the graph and where transitions are only allowed along the edges. We study (strongly) reversible random walks and characterize the class of graphs where then-step transition probabilities tend to zero exponentially fast (geometric ergodicity). These characterizations deal with an isoperimetric property, norm inequalities for certain associated operators, and eigenvalues of the Laplace operator. There is some (strong) similarity with the theory of (non)amenable groups.     

Effective Polynomial Ballisticity Conditions for Random Walk in Random Environment

The conditions (T)_γ, γ ? (0,1), which were introduced by Sznitman in 2002, have had a significant impact on research in random walk in a random environment. Among others, these conditions entail a ballistic behavior as well as an invariance principle. They require the stretched exponential decay of certain slab exit probabilities for the random walk under the averaged measure and are asymptotic in nature. The main goal of this paper is to show that in all relevant dimensions (i.e., d ≥ 2), in order to establish the conditions (T)_γ, it is actually enough to check a corresponding condition (??) of polynomial type. In addition to only requiring an a priori weaker decay of the corresponding slab exit probabilities than (T)_γ, another advantage of the condition (??) is that it is effective in the sense that it can be checked on finite boxes. In particular, this extends the conjectured equivalence of the conditions (T)_γ, γ ? (0,1), to all relevant dimensions. © 2014 Wiley Periodicals, Inc.     

Recurrence and transience of multitype branching random walks

We study a discrete time Markov process with particles being able to perform discrete time random walks and create new particles, known as branching random walk (BRW). We suppose that there are particles of different types, and the transition probabilities, as well as offspring distribution, depend on the type and the position of the particle. Criteria of (strong) recurrence and transience are presented, and some applications (spatially homogeneous case, Lamperti BRW, many-dimensional BRW) are studied.     

First return probabilities of birth and death chains and associated orthogonal polynomials

For a birth and death chain on the nonnegative integers, integral representations for first return probabilities are derived. While the integral representations for ordinary transition probabilities given by Karlin and McGregor (1959) involve a system of random walk polynomials and the corresponding measure of orthogonality, the formulas for the first return probabilities are based on the corresponding systems of associated orthogonal polynomials. Moreover, while the moments of the measure corresponding to the random walk polynomials give the ordinary return probabilities to the origin, the moments of the measure corresponding to the associated polynomials give the first return probabilities to the origin.

As a by-product we obtain a new characterization in terms of canonical moments for the measure of orthogonality corresponding to the first associated orthogonal polynomials. The results are illustrated by several examples.

     

Random walks on diestel-leader graphs

We investigate various features of a quite new family of graphs, introduced as a possible example of vertex-transitive graph not roughly isometric with a Cayley graph of some finitely generated group. We exhibit a natural compactification and study a large class of random walks, proving theorems concerning almost sure convergence to the boundary, a strong law of large numbers and a central limit theorem. The asymptotic type of then-step transition probabilities of the simple random walk is determined.     

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.     

On Transience Conditions for Markov Chains and Random Walks

We prove a new transience criterion for Markov chains on an arbitrary state space and give a corollary for real-valued chains. We show by example that in the case of a homogeneous random walk with infinite mean the proposed sufficient conditions are close to those necessary. We give a new proof of the well-known criterion for finiteness of the supremum of a random walk.     

Random Walks on the Affine Group of a Homogeneous Tree in the Drift-Free Case

The affine group of a homogeneous tree is the group of all its isometries fixing an end of its boundary. We consider a random walk with law μ on this group and the associated random processes on the tree and its boundary. In the drift-free case there exists on the boundary of the tree a unique μ-invariant Radon measure. In this paper we describe its behaviour at infinity.     

Random Walks on Dihedral Groups

In this paper, we look at the lower bounds of two specific random walks on the dihedral group. The first theorem discusses a random walk generated with equal probabilities by one rotation and one flip. We show that roughly p ² steps are necessary for the walk to become close to uniformly distributed on all of D _2p where p≥3 is an integer. Next we take a random walk on the dihedral group generated by a random k-subset of the dihedral group. The latter theorem shows that it is necessary to take roughly p ^2/(k−1) steps in the typical random walk to become close to uniformly distributed on all of D _2p . We note that there is at least one rotation and one flip in the k-subset, or the random walk generated by this subset has periodicity problems or will not generate all of D _2p .     

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.     

Invariance principle for nonhomogeneous random walks on the grid ℤ1

A nonhomogeneous random walk on the grid ℤ¹ with transition probabilities that differ from those of a certain homogeneous random walk only at a finite number of points is considered. Trajectories of such a walk are proved to converge to trajectories of a certain generalized diffusion process on the line. This result is a generalization of the well-known invariance principle for the sums of independent random variables and Brownian motion. Translated fromMatematicheskie Zametki, Vol. 66, No. 3, pp. 459–472, September, 1999.     

Random walk centrality and a partition of Kemeny’s constant

We consider an accessibility index for the states of a discrete-time, ergodic, homogeneous Markov chain on a finite state space; this index is naturally associated with the random walk centrality introduced by Noh and Reiger (2004) for a random walk on a connected graph. We observe that the vector of accessibility indices provides a partition of Kemeny’s constant for the Markov chain. We provide three characterizations of this accessibility index: one in terms of the first return time to the state in question, and two in terms of the transition matrix associated with the Markov chain. Several bounds are provided on the accessibility index in terms of the eigenvalues of the transition matrix and the stationary vector, and the bounds are shown to be tight. The behaviour of the accessibility index under perturbation of the transition matrix is investigated, and examples exhibiting some counter-intuitive behaviour are presented. Finally, we characterize the situation in which the accessibility indices for all states coincide.     

The Dirichlet problem at infinity for random walks on graphs with a strong isoperimetric inequality

Summary We study the spatial behaviour of random walks on infinite graphs which are not necessarily invariant under some transitive group action and whose transition probabilities may have infinite range. We assume that the underlying graphG satisfies a strong isoperimetric inequality and that the transition operatorP is strongly reversible, uniformly irreducible and satisfies a uniform first moment condition. We prove that under these hypotheses the random walk converges almost surely to a random end ofG and that the Dirichlet problem forP-harmonic functions is solvable with respect to the end compactification If in addition the graph as a metric space is hyperbolic in the sense of Gromov, then the same conclusions also hold for the hyperbolic compactification in the place of the end compactification. The main tool is the exponential decay of the transition probabilities implied by the strong isoperimetric inequality. Finally, it is shown how the same technique can be applied to Brownian motion to obtain analogous results for Riemannian manifolds satisfying Cheeger's isoperimetric inequality. In particular, in this general context new (and simpler) proofs of well known results on the Dirichlet problem for negatively curved manifolds are obtained.The first author was partially supported by Consiglio Nazionale delle Ricerche, GNAFA Current address: Department of Mathematics, University of Edinburgh, Edinburgh EH9 3JZ, Scotland