Shift-coupling and a zero-one law for random walk in random environment

This paper discusses several aspects of shift-coupling for random walk in random environment.     

Escape probabilities for slowly recurrent sets

Summary A setAZ ^d (d>-3) is defined to be slowly recurrent for simple random walk if it is recurrent but the probability of enteringA{z:n<|z|<-2n} tends to zero asn. A method is given to estimate escape probabilities for such sets, i.e., the probability of leaving the ball of radiusn without entering the set. The methods are applied to two examples. First, half-lines and finite unions of half-lines inZ ³ are considered. The second example is a random walk path in four dimensions. In the latter case it is proved that the probability that two random walk paths reach the ball of radiusn without intersecting is asymptotic toc(lnn)^–1/2, improving a result of the author.Research partially supported by the National Science Foundation     

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     

Zeno's walk: A random walk with refinements

Summary. A self-modifying random walk on is derived from an ordinary random walk on the integers by interpolating a new vertex into each edge as it is crossed. This process converges almost surely to a random variable which is totally singular with respect to Lebesgue measure, and which is supported on a subset of having Hausdorff dimension less than , which we calculate by a theorem of Billingsley. By generating function techniques we then calculate the exponential rate of convergence of the process to its limit point, which may be taken as a bound for the convergence of the measure in the Wasserstein metric. We describe how the process may viewed as a random walk on the space of monotone piecewise linear functions, where moves are taken by successive compositions with a randomly chosen such function. Received: 20 November 1995 / In revised form: 14 May 1996     

Spitzer's condition and ladder variables in random walks

Summary Spitzer's condition holds for a random walk if the probabilities _n =P{ _n > 0} converge in Cèsaro mean to , where 0<<1. We answer a question which was posed both by Spitzer [12] and by Emery [5] by showing that whenever this happens, it is actually true that n converges to . This also enables us to give an improved version of a result in Doney and Greenwood [4], and show that the random walk is in a domain of attraction, without centering, if and only if the first ladder epoch and height are in a bivariate domain of attraction.     

Limiting behavior of a diffusion in an asymptotically stable environment

Let V be a two sided random walk and let X denote a real valued diffusion process with generator . This process is the continuous equivalent of the one-dimensional random walk in random environment with potential V. Hu and Shi (1997) described the Lévy classes of X in the case where V behaves approximately like a Brownian motion. In this paper, based on some fine results on the fluctuations of random walks and stable processes, we obtain an accurate image of the almost sure limiting behavior of X when V behaves asymptotically like a stable process. These results also apply for the corresponding random walk in random environment.     

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     

On growth,recurrence and the Choquet-Deny Theorem for <Emphasis Type="Italic">p</Emphasis>-adic Lie groups

We first study the growth properties of p-adic Lie groups and its connection with p-adic Lie groups of type R and prove that a non-type R p-adic Lie group has compact neighbourhoods of identity having exponential growth. This is applied to prove the growth dichotomy for a large class of p-adic Lie groups which includes p-adic algebraic groups. We next study p-adic Lie groups that admit recurrent random walks and prove the natural growth conjecture connecting growth and the existence of recurrent random walks, precisely we show that a p-adic Lie group admits a recurrent random walk if and only if it has polynomial growth of degree at most two. We prove this conjecture for some other classes of groups also. We also prove the Choquet-Deny Theorem for compactly generated p-adic Lie groups of polynomial growth and also show that polynomial growth is necessary and sufficient for the validity of the Choquet-Deny for all spread-out probabilities on Zariski-connected p-adic algebraic groups. Counter example is also given to show that certain assumptions made in the main results can not be relaxed.     

Passage times of random walks and Lévy processes across power law boundaries

We establish an integral test involving only the distribution of the increments of a random walk S which determines whether limsup _n→∞(S_n/n^κ) is almost surely zero, finite or infinite when 1/2<κ<1 and a typical step in the random walk has zero mean. This completes the results of Kesten and Maller [9] concerning finiteness of one-sided passage times over power law boundaries, so that we now have quite explicit criteria for all values of κ≥0. The results, and those of [9], are also extended to Lévy processes.This work is partially supported by ARC Grant DP0210572.     

Biased random walks on directed trees

Summary. We define directed rooted labeled and unlabeled trees and find measures on the space of directed rooted unlabeled trees which are invariant with respect to transition probabilities corresponding to a biased random walk on a directed rooted labeled tree. We use these to calculate the speed of a biased random walk on directed rooted labeled trees. The results are mainly applied to directed trees with recurrent subtrees, where the random walker cannot escape. Received: 12 March 1997/ In revised form: 11 December 1997     

Random walks supported on random points ofZ/nZ

Summary This paper considers random walks on the integers modn supported onk points and asks how long does it take for these walks to get close to uniformly distributed. Ifk is a constant, Greenhalgh showed that at least some constant timesn ^2/(k–1) steps are necessary to make the distance of the random walk from the uniform distribution small; here we show that ifn is prime, some constant timesn ^2/(k–1) steps suffice to make this distance small for almost all choices ofk points. The proof uses the Upper Bound Lemma of Diaconis and Shahshahani and some averaging techniques. This paper also explores some cases wherek varies withn. In particular, ifk=(logn) ^a , we find different kinds of results for different values ofa, and these results disprove a conjecture of Aldous and Diaconis.Research Supported in Part by a Rackham Faculty Fellowship at the University of Michigan     

Maxima of branching random walks vs. independent random walks

In recent years several authors have obtained limit theorems for the location of the right most particle in a supercritical branching random walk. In this paper we will consider analogous problems for an exponentially growing number of independent random walks. A comparison of our results with the known results of branching random walk then identifies the limit behaviors which are due to the number of particles and those which are determined by the branching structure.     

Biased random walks

How much can an imperfect source of randomness affect an algorithm? We examine several simple questions of this type concerning the long-term behavior of a random walk on a finite graph. In our setup, at each step of the random walk a “controller” can, with a certain small probability, fix the next step, thus introducing a bias. We analyze the extent to which the bias can affect the limit behavior of the walk. The controller is assumed to associate a real, nonnegative, “benefit” with each state, and to strive to maximize the long-term expected benefit. We derive tight bounds on the maximum of this objective function over all controller's strategies, and present polynomial time algorithms for computing the optimal controller strategy.     

Almost sure estimates for the concentration neighborhood of Sinai’s walk

We consider Sinai’s random walk in random environment. We prove that infinitely often (i.o.) the size of the concentration neighborhood of this random walk is bounded almost surely. We also get that i.o. the maximal distance between two favorite sites is bounded almost surely.     

Restricted random walks on a graph

The problem of a restricted random walk on graphs, which keeps track of the number of immediate reversal steps, is considered by using a transfer matrix formulation. A closed-form expression is obtained for the generating function of the number ofn-step walks withr reversal steps for walks on any graph. In the case of graphs of a uniform valence, we show that our result has a probabilistic meaning, and deduce explicit expressions for the generating function in terms of the eigenvalues of the adjacency matrix. Applications to periodic lattices and the complete graph are given.Supported in part by National Science Foundation Grant DMR-9614170.     

The drift of a one-dimensional self-avoiding random walk

Summary We prove that a self-avoiding random walk on the integers with bounded increments grows linearly. We characterize its drift in terms of the Frobenius eigenvalue of a certain one parameter family of primitive matrices. As an important tool, we express the local times as a two-block functional of a certain Markov chain, which is of independent interest.     

Random walks on generalized lattices

A generalized lattice is a graph on which the groupZ ^d acts almost transitively. The relations among various features of random walks on generalized lattices are studied. In particular we relate the mean displacement, the drift-freeness of the random walk and the existence of linear harmonic functions. Applications to recurrence criteria are given.     

Random walk on the infinite cluster of the percolation model

Summary We consider random walk on the infinite cluster of bond percolation on ^d . We show that, in the supercritical regime whend3, this random walk is a.s. transient. This conclusion is achieved by considering the infinite percolation cluster as a random electrical network in which each open edge has unit resistance. It is proved that the effective resistance of this network between a nominated point and the points at infinity is almost surely finite.G.R.G. acknowledges support from Cornell University, and also partial support by the U.S. Army Research Office through the Mathematical Sciences Institute of Cornell UniversityH.K. was supported in part by the N.S.F. through a grant to Cornell University     

Logarithmic speeds for one-dimensional perturbed random walks in random environments

We study the random walk in a random environment on Z⁺={0,1,2,…}${\mathbb{Z}}^{+}=\{0,1,2,\dots \}$, where the environment is subject to a vanishing (random) perturbation. The two particular cases that we consider are: (i) a random walk in a random environment perturbed from Sinai’s regime; (ii) a simple random walk with a random perturbation. We give almost sure results on how far the random walker is from the origin, for almost every environment. We give both upper and lower almost sure bounds. These bounds are of order (logt)^β${(logt)}^{\beta }$, for β∈(1,∞)$\beta \in (1,\infty )$, depending on the perturbation. In addition, in the ergodic cases, we give results on the rate of decay of the stationary distribution.