A quenched invariance principle for non-elliptic random walk in i.i.d. balanced random environment

We consider a random walk on $\mathbb{Z }^d,\ d\ge 2$ , in an i.i.d. balanced random environment, that is a random walk for which the probability to jump from $x\in \mathbb{Z }^d$ to nearest neighbor $x+e$ is the same as to nearest neighbor $x-e$ . Assuming that the environment is genuinely $d$ -dimensional and balanced we show a quenched invariance principle: for $P$ almost every environment, the diffusively rescaled random walk converges to a Brownian motion with deterministic non-degenerate diffusion matrix. Within the i.i.d. setting, our result extend both Lawler’s uniformly elliptic result (Comm Math Phys, 87(1), pp 81–87, 1982/1983) and Guo and Zeitouni’s elliptic result (to appear in PTRF, 2010) to the general (non elliptic) case. Our proof is based on analytic methods and percolation arguments.     

Localization of a vertex reinforced random walk on \mathbb{Z } with sub-linear weight

We consider a vertex reinforced random walk on the integer lattice with sub-linear reinforcement. Under some assumptions on the regular variation of the weight function, we characterize whether the walk gets stuck on a finite interval. When this happens, we estimate the size of the localization set. In particular, we show that, for any odd number $N$ larger than or equal to $5$ , there exists a vertex reinforced random walk which localizes with positive probability on exactly $N$ consecutive sites.     

Exact value of the resistance exponent for four dimensional random walk trace

Let S be a simple random walk starting at the origin in ${\mathbb{Z}^{4}}$ . We consider ${{\mathcal G}=S[0,\infty)}$ to be a random subgraph of the integer lattice and assume that a resistance of unit 1 is put on each edge of the graph ${{\mathcal G}}$ . Let ${R_{{\mathcal G}}(0,S_{n})}$ be the effective resistance between the origin and S _n . We derive the exact value of the resistance exponent; more precisely, we prove that ${n^{-1}E(R_{{\mathcal G}}(0,S_{n}))\approx (\log n)^{-\frac{1}{2}}}$ . As an application, we obtain sharp heat kernel estimates for random walk on ${\mathcal G}$ at the quenched level. These results give the answer to the problem raised by Burdzy and Lawler (J Phys A Math Gen 23:L23–L28, 1990) in four dimensions.     

Ballisticity conditions for random walk in random environment

Consider a random walk in a uniformly elliptic i.i.d. random environment in dimensions d ?? 2. In 2002, Sznitman introduced for each ${\gamma\in (0, 1)}$ the ballisticity conditions (T) _?? and (T??), the latter being defined as the fulfillment of (T) _?? for all ${\gamma\in (0, 1)}$ . He proved that (T??) implies ballisticity and that for each ${\gamma\in (0.5, 1)}$ , (T) _?? is equivalent to (T??). It is conjectured that this equivalence holds for all ${\gamma\in (0, 1)}$ . Here we prove that for ${\gamma\in (\gamma_d, 1)}$ , where ?? _d is a dimension dependent constant taking values in the interval (0.366, 0.388), (T) _?? is equivalent to (T??). This is achieved by a detour along the effective criterion, the fulfillment of which we establish by a combination of techniques developed by Sznitman giving a control on the occurrence of atypical quenched exit distributions through boxes.     

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.     

A law of the iterated logarithm for random walk in random scenery with deterministic normalizers

LetX, X _i ,i≥1, be a sequence of independent and identically distributed ? ^d -valued random vectors. LetS _o=0 and \(S_n = \sum\nolimits_{i = 1}^n {X_i } \) forn≤1. Furthermore letY, Y(α), α∈? ^d , be independent and identically distributed ?-valued random variables, which are independent of theX _i . Let \(Z_n = \sum\nolimits_{i = 0}^n {Y(S_i )} \) . We will call (Z _n ) arandom walk in random scenery. In this paper, we consider the law of the iterated logarithm for random walk in random scenery where deterministic normalizers are utilized. For example, we show that if (S _n ) is simple, symmetric random walk in the plane,E[Y]=0 andE[Y ²]=1, then $$\mathop {\overline {\lim } }\limits_{n \to \infty } \frac{{Z_n }}{{\sqrt {2n\log (n)\log (\log (n))} }} = \sqrt {\frac{2}{\pi }} a.s.$$      

Random walk on a discrete Heisenberg group

We use the estimate of paths in Z ² enclosing a null algebraic area to compute correction terms on the random walk on certain discrete Heisenberg groups. We obtain that the probability to return at the origin of the simple random walk on this group is $\frac{1}{4n^{2}}+O(\frac{1}{n^{3}})$ .     

Simple random walk on the uniform infinite planar quadrangulation: subdiffusivity via pioneer points

We study the pioneer points of the simple random walk on the uniform infinite planar quadrangulation (UIPQ) using an adaptation of the peeling procedure of Angel (Geom Funct Anal 13:935–974, 2003) to the quadrangulation case. Our main result is that, up to polylogarithmic factors, n ³ pioneer points have been discovered before the walk exits the ball of radius n in the UIPQ. As a result we verify the KPZ relation Knizhnik et al. (Modern Phys Lett A 3:819–826, 1988) in the particular case of the pioneer exponent and prove that the walk is subdiffusive with exponent less than 1/3. Along the way, new geometric controls on the UIPQ are established.     

Monotonicity for excited random walk in high dimensions

We prove that the drift θ(d, β) for excited random walk in dimension d is monotone in the excitement parameter ${\beta \in [0,1]}$ , when d is sufficiently large. We give an explicit criterion for monotonicity involving random walk Green’s functions, and use rigorous numerical upper bounds provided by Hara (Private communication, 2007) to verify the criterion for d ≥ 9.     

A Monotonicity Result for the Range of a Perturbed Random Walk

We consider a discrete time simple symmetric random walk on \(\mathbb{Z }^d,\,d\ge 1,\) where the path of the walk is perturbed by inserting deterministic jumps. We show that for any time \(n\in \mathbb{N }\) and any deterministic jumps that we insert, the expected number of sites visited by the perturbed random walk up to time \(n\) is always larger than or equal to that for the unperturbed walk. This intriguing problem arises from the study of a particle among a Poisson system of moving traps with sub-diffusive trap motion. In particular, our result implies a variant of the Pascal principle, which asserts that among all deterministic trajectories the particle can follow, the constant trajectory maximizes the particle’s survival probability up to any time \(t>0.\)      

Mixing of the upper triangular matrix walk

We study a natural random walk over the upper triangular matrices, with entries in the field ${\mathbb{Z}_2}$ , generated by steps which add row i + 1 to row i. We show that the mixing time of the lazy random walk is O(n ²) which is optimal up to constants. Our proof makes key use of the linear structure of the group and extends to walks on the upper triangular matrices over the fields ${\mathbb{Z}_q}$ for q prime.     

Normal approximation for a random elliptic equation

We consider solutions of an elliptic partial differential equation in \(\mathbb{R }^d\) with a stationary, random conductivity coefficient that is also periodic with period \(L\) . Boundary conditions on a square domain of width \(L\) are arranged so that the solution has a macroscopic unit gradient. We then consider the average flux that results from this imposed boundary condition. It is known that in the limit \(L \rightarrow \infty \) , this quantity converges to a deterministic constant, almost surely. Our main result is that the law of this random variable is very close to that of a normal random variable, if the domain size \(L\) is large. We quantify this approximation by an error estimate in total variation. The error estimate relies on a second order Poincaré inequality developed recently by Chatterjee.     

Martin boundary of a reflected random walk on a half-space

The complete representation of the Martin compactification for reflected random walks on a half-space ${\mathbb{Z}^d\times\mathbb{N}}$ is obtained. It is shown that the full Martin compactification is in general not homeomorphic to the “radial” compactification obtained by Ney and Spitzer for the homogeneous random walks in ${\mathbb{Z}^d}$ : convergence of a sequence of points ${z_n\in\mathbb{Z}^{d-1}\times\mathbb{N}}$ to a point of on the Martin boundary does not imply convergence of the sequence z _n /|z _n | on the unit sphere S ^d . Our approach relies on the large deviation properties of the scaled processes and uses Pascal’s method combined with the ratio limit theorem. The existence of non-radial limits is related to non-linear optimal large deviation trajectories.     

The loop-erased random walk and the uniform spanning tree on the four-dimensional discrete torus

Let x and y be points chosen uniformly at random from ${\mathbb {Z}_n^4}$ , the four-dimensional discrete torus with side length n. We show that the length of the loop-erased random walk from x to y is of order n ²(log n)^1/6, resolving a conjecture of Benjamini and Kozma. We also show that the scaling limit of the uniform spanning tree on ${\mathbb {Z}_n^4}$ is the Brownian continuum random tree of Aldous. Our proofs use the techniques developed by Peres and Revelle, who studied the scaling limits of the uniform spanning tree on a large class of finite graphs that includes the d-dimensional discrete torus for d ≥ 5, in combination with results of Lawler concerning intersections of four-dimensional random walks.     

Ellipticity criteria for ballistic behavior of random walks in random environment

We introduce ellipticity criteria for random walks in i.i.d. random environments under which we can extend the ballisticity conditions of Sznitman and the polynomial effective criteria of Berger, Drewitz and Ramírez originally defined for uniformly elliptic random walks. We prove under them the equivalence of Sznitman’s \((T')\) condition with the polynomial effective criterion \((P)_M\) , for \(M\) large enough. We furthermore give ellipticity criteria under which a random walk satisfying the polynomial effective criterion, is ballistic, satisfies the annealed central limit theorem or the quenched central limit theorem.     

On total progeny of multitype Galton-Watson process and the first passage time of random walk on lattice

In this paper,we form a method to calculate the probability generating function of the total progeny of multitype branching process.As examples,we calculate probability generating function of the total progeny of the multitype branching processes within random walk which could stay at its position and(2-1) random walk.Consequently,we could give the probability generating functions and the distributions of the first passage time of corresponding random walks.Especially,for recurrent random walk which could stay at its position with probability 0 r 1,we show that the tail probability of the first passage time decays as 2/(π(1-r)~(1/2)) n~(1/1)= when n →∞.     

Large deviations of the first passage time for a random walk with semiexponentially distributed jumps

Suppose that ξ, ξ(1), ξ(2), ... are independent identically distributed random variables such that ?ξ is semiexponential; i.e., $P( - \xi \geqslant t) = e^{ - t^\beta L(t)} $ is a slowly varying function as t → ∞ possessing some smoothness properties. Let E ξ = 0, D ξ = 1, and S(k) = ξ(1) + ? + ξ(k). Given d > 0, define the first upcrossing time η ₊(u) = inf{k ≥ 1: S(k) + kd > u} at nonnegative level u ≥ 0 of the walk S(k) + kd with positive drift d > 0. We prove that, under general conditions, the following relation is valid for $u = (n) \in \left[ {0, dn - N_n \sqrt n } \right]$ : 0.1 $P(\eta + (u) > n) \sim \frac{{E\eta + (u)}}{n}P(S(n) \leqslant x) as n \to \infty $ , where x = u ? nd < 0 and an arbitrary fixed sequence N _n not exceeding $d\sqrt n $ tends to ∞. The conditions under which we prove (0.1) coincide exactly with the conditions under which the asymptotic behavior of the probability P(S(n) ≤ x) for $x \leqslant - \sqrt n $ was found in [1] (for $x \in \left[ { - \sqrt n ,0} \right]$ it follows from the central limit theorem).     

Almost sure convergence for stochastically biased random walks on trees

We are interested in the biased random walk on a supercritical Galton?CWatson tree in the sense of Lyons (Ann. Probab. 18:931?C958, 1990) and Lyons, Pemantle and Peres (Probab. Theory Relat. Fields 106:249?C264, 1996), and study a phenomenon of slow movement. In order to observe such a slow movement, the bias needs to be random; the resulting random walk is then a tree-valued random walk in random environment. We investigate the recurrent case, and prove, under suitable general integrability assumptions, that upon the system??s non-extinction, the maximal displacement of the walk in the first n steps, divided by (log n)³, converges almost surely to a known positive constant.     

Total progeny in killed branching random walk

We consider a branching random walk for which the maximum position of a particle in the n??th generation, R _n , has zero speed on the linear scale: R _n /n ?? 0 as n ?? ??. We further remove (??kill??) any particle whose displacement is negative, together with its entire descendence. The size Z of the set of un-killed particles is almost surely finite (Gantert and Müller in Markov Process. Relat. Fields 12:805?C814, 2006; Hu and Shi in Ann. Probab. 37(2):742?C789, 2009). In this paper, we confirm a conjecture of Aldous (Algorithmica 22:388?C412, 1998; and Power laws and killed branching random walks) that E [Z]?<??? while ${{\mathbf E}\left[Z\,{\rm log}\, Z\right]=\infty}$ . The proofs rely on precise large deviations estimates and ballot theorem-style results for the sample paths of random walks.