Quenched invariance principle for simple random walk on percolation clusters

We consider the simple random walk on the (unique) infinite cluster of super-critical bond percolation in ℤ ^d with d≥2. We prove that, for almost every percolation configuration, the path distribution of the walk converges weakly to that of non-degenerate, isotropic Brownian motion. Our analysis is based on the consideration of a harmonic deformation of the infinite cluster on which the random walk becomes a square-integrable martingale. The size of the deformation, expressed by the so called corrector, is estimated by means of ergodicity arguments.     

Simple random walk on long range percolation clusters I: heat kernel bounds

In this paper, we derive upper bounds for the heat kernel of the simple random walk on the infinite cluster of a supercritical long range percolation process. For any d ?? 1 and for any exponent ${s \in (d, (d+2) \wedge 2d)}$ giving the rate of decay of the percolation process, we show that the return probability decays like ${t^{-{d}/_{s-d}}}$ up to logarithmic corrections, where t denotes the time the walk is run. Our methods also yield generalized bounds on the spectral gap of the dynamics and on the diameter of the largest component in a box. The bounds and accompanying understanding of the geometry of the cluster play a crucial role in the companion paper (Crawford and Sly in Simple randomwalk on long range percolation clusters II: scaling limit, 2010) where we establish the scaling limit of the random walk to be ??-stable Lévy motion.     

Biased random walk in a one-dimensional percolation model

We consider random walk with a nonzero bias to the right, on the infinite cluster in the following percolation model: take i.i.d. bond percolation with retention parameter p$p$ on the so-called infinite ladder, and condition on the event of having a bi-infinite path from −∞$-\infty$ to ∞$\infty$. The random walk is shown to be transient, and to have an asymptotic speed to the right which is strictly positive or zero depending on whether the bias is below or above a certain critical value which we compute explicitly.     

Identifying several biased coins encountered by a hidden random walk

Suppose that attached to each site z ∈ ? is a coin with bias θ(z), and only finitely many of these coins have nonzero bias. Allow a simple random walker to generate observations by tossing, at each move, the coin attached to its current position. Then we can determine the biases {θ(z)}_z∈?, using only the outcomes of these coin tosses and no information about the path of the random walker, up to a shift and reflection of ?. This generalizes a result of Harris and Keane. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2004     

On the speed of a cookie random walk

We consider the model of the one-dimensional cookie random walk when the initial cookie distribution is spatially uniform and the number of cookies per site is finite. We give a criterion to decide whether the limiting speed of the walk is non-zero. In particular, we show that a positive speed may be obtained for just three cookies per site. We also prove a result on the continuity of the speed with respect to the initial cookie distribution.      

Sizes of the largest clusters for supercritical percolation on random recursive trees

We consider Bernoulli bond‐percolation on a random recursive tree of size , with supercritical parameter for some fixed. We show that with high probability, the largest cluster has size close to whereas the next largest clusters have size of order only and are distributed according to some Poisson random measure. Copyright © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 44, 29–44, 2014     

The oscillating random walk

{Y_n;n=0, 1, …} denotes a stationary Markov chain taking values in R^d. As long as the process stays on the same side of a fixed hyperplane E⁰, it behaves as an ordinary random walk with jump measure μ or ν, respectively. Thus ordinary random walk would be the special case μ = ν. Also the process Y′_n = |Y′_n?1?Z_n| (with the Z_n as i.i.d. real random varia bles) may be regarded as a special case. The general process is studied by a Wiener–Hopf type method. Exact formulae are obtained for many quantities of interest. For the special case that the Y_n are integral-valued, renewal type conditions are established which are necessary and sufficient for recurrence.     

On the mixing time of a simple random walk on the super critical percolation cluster

 We study the robustness under perturbations of mixing times, by studying mixing times of random walks in percolation clusters inside boxes in Z ^d . We show that for d≥2 and p>p _c (Z ^d ), the mixing time of simple random walk on the largest cluster inside is Θ(n ² ) – thus the mixing time is robust up to a constant factor. The mixing time bound utilizes the Lovàsz-Kannan average conductance method. This is the first non-trivial application of this method which yields a tight result. Received: 16 December 2001 / Revised version: 13 August 2002 / Published online: 19 December 2002     

Quenched invariance principles for walks on clusters of percolation or among random conductances

In this work we principally study random walk on the supercritical infinite cluster for bond percolation on ^d. We prove a quenched functional central limit theorem for the walk when d4. We also prove a similar result for random walk among i.i.d. random conductances along nearest neighbor edges of ^d, when d1.V. Sidoravicius would like to thank the FIM for financial support and hospitality during his multiple visits to ETH. His research was also partially supported by FAPERJ and CNPq.     

Diffusivity of a random walk on random walks

We consider a random walk with the constraint that each coordinate of the walk is at distance one from the following one. In this paper, we show that this random walk is slowed down by a variance factor with respect to the case of the classical simple random walk without constraint. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 267–283, 2015     

Vertex-reinforced random walk

Summary This paper considers a class of non-Markovian discrete-time random processes on a finite state space {1,...,d}. The transition probabilities at each time are influenced by the number of times each state has been visited and by a fixed a priori likelihood matrix,R, which is real, symmetric and nonnegative. LetS _i (n) keep track of the number of visits to statei up to timen, and form the fractional occupation vector,V(n), where . It is shown thatV(n) converges to to a set of critical points for the quadratic formH with matrixR, and that under nondegeneracy conditions onR, there is a finite set of points such that with probability one,V(n)p for somep in the set. There may be more than onep in this set for whichP(V(n)p)>0. On the other handP(V(n)p)=0 wheneverp fails in a strong enough sense to be maximum forH.This research was supported by an NSF graduate fellowship and by an NSF postdoctoral fellowship     

Reinforced random walk

Summary Leta _i,i1, be a sequence of nonnegative numbers. Difine a nearest neighbor random motion =X ₀,X ₁, ... on the integers as follows. Initially the weight of each interval (i, i+1), i an integer, equals 1. If at timen an interval (i, i+1) has been crossed exactlyk times by the motion, its weight is . Given (X ₀,X ₁, ...,X _n)=(i₀, i₁, ..., i_n), the probability thatX _n+1 isi _n–1 ori _n+1 is proportional to the weights at timen of the intervals (i _n–1,i _n) and (i _n,ii_n+1). We prove that either visits all integers infinitely often a.s. or visits a finite number of integers, eventually oscillating between two adjacent integers, a.s., and that X _n /n=0 a.s. For much more general reinforcement schemes we proveP ( visits all integers infinitely often)+P ( has finite range)=1.Supported by a National Science Foundation Grant     

A note on random walk in random scenery

We consider a random walk in random scenery {Xn=η(S₀)+?+η(Sn),n∈N}, where a centered walk {Sn,n∈N} is independent of the scenery {η(x),x∈Zd}, consisting of symmetric i.i.d. with tail distribution P(η(x)>t)∼exp(−cαtα), with 1?α<d/2. We study the probability, when averaged over both randomness, that {Xn>ny} for y>0, and n large. In this note, we show that the large deviation estimate is of order exp(−ca(ny)), with a=α/(α+1).     

The number of infinite clusters in dynamical percolation

Summary. Dynamical percolation is a Markov process on the space of subgraphs of a given graph, that has the usual percolation measure as its stationary distribution. In previous work with O. H?ggstr?m, we found conditions for existence of infinite clusters at exceptional times. Here we show that for ℤ ^d , with p>p _c , a.s. simultaneously for all times there is a unique infinite cluster, and the density of this cluster is θ(p). For dynamical percolation on a general tree Γ, we show that for p>p _c , a.s. there are infinitely many infinite clusters at all times. At the critical value p=p _c , the number of infinite clusters may vary, and exhibits surprisingly rich behaviour. For spherically symmetric trees, we find the Hausdorff dimension of the set T ^k of times where the number of infinite clusters is k, and obtain sharp capacity criteria for a given time set to intersect T ^k . The proof of this capacity criterion is based on a new kernel truncation technique. Received: 5 May 1997 / In revised form: 24 November 1997     

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.