Random walks on discrete cylinders and random interlacements

We explore some of the connections between the local picture left by the trace of simple random walk on a cylinder ${(\mathbb {Z} / N\mathbb {Z})^d \times \mathbb {Z}}$ , d ≥ 2, running for times of order N ^2d and the model of random interlacements recently introduced in Sznitman ( http://www.math.ethz.ch/u/sznitman/preprints). In particular, we show that for large N in the neighborhood of a point of the cylinder with vertical component of order N ^d the complement of the set of points visited by the walk up to times of order N ^2d is close in distribution to the law of the vacant set of random interlacements with a level which is determined by an independent Brownian local time. The limit behavior of the joint distribution of the local pictures in the neighborhood of finitely many points is also derived.     

On the size of a finite vacant cluster of random interlacements with small intensity

In this paper, we establish some properties of percolation for the vacant set of random interlacements, for d ?? 5 and small intensity u. The model of random interlacements was first introduced by Sznitman in (Ann Math, arXiv:0704.2560, 2010). It is known that, for small u, almost surely there is a unique infinite connected component in the vacant set left by the random interlacements at level u, see Sidoravicius and Sznitman (Commun Pure Appl Math 62(6):831?C858, 2009) and Teixeira (Ann Appl Probab 19(1):454?C466, 2009). We estimate here the distribution of the diameter and the volume of the vacant component at level u containing the origin, given that it is finite. This comes as a by-product of our main theorem, which proves a stretched exponential bound on the probability that the interlacement set separates two macroscopic connected sets in a large cube. As another application, we show that with high probability, the unique infinite connected component of the vacant set is ??ubiquitous?? in large neighborhoods of the origin.     

Percolation for the vacant set of random interlacements

We investigate random interlacements on ?^d, d ≥ 3. This model, recently introduced in [8], corresponds to a Poisson cloud on the space of doubly infinite trajectories modulo time shift tending to infinity at positive and negative infinite times. A nonnegative parameter u measures how many trajectories enter the picture. Our main interest lies in the percolative properties of the vacant set left by random interlacements at level u. We show that for all d ≥ 3 the vacant set at level u percolates when u is small. This solves an open problem of [8], where this fact has only been established when d ≥ 7. It also completes the proof of the nondegeneracy in all dimensions d ≥ 3 of the critical parameter u_* of [8]. © 2008 Wiley Periodicals, Inc.     

On the fragmentation of a torus by random walk

We consider a simple random walk on a discrete torus \input amssym $({\Bbb Z}/N{\Bbb Z})^d$ with dimension d ≥ 3 and large side length N. For a fixed constant u ≥ 0, we study the percolative properties of the vacant set, consisting of the set of vertices not visited by the random walk in its first [uN^d] steps. We prove the existence of two distinct phases of the vacant set in the following sense: If u > 0 is chosen large enough, all components of the vacant set contain no more than (log N)^λ(u) vertices with high probability as N tends to infinity. On the other hand, for small u > 0, there exists a macroscopic component of the vacant set occupying a nondegenerate fraction of the total volume N^d. In dimensions d ≥ 5, we additionally prove that this macroscopic component is unique by showing that all other components have volumes of order at most (log N)^λ(u). Our results thus solve open problems posed by Benjamini and Sznitman, who studied the small u regime in high dimension. The proofs are based on a coupling of the random walk with random interlacements on \input amssym ${\Bbb Z}^d$ . Among other techniques, the construction of this coupling employs a refined use of discrete potential theory. By itself, this coupling strengthens a result by Windisch. © 2011 Wiley Periodicals, Inc.     

Intersection local times for interlacements

We define renormalized intersection local times for random interlacements of Lévy processes in R^d$R^d$ and prove an isomorphism theorem relating renormalized intersection local times with associated Wick polynomials.     

Hitting Times,Cover Cost,and the Wiener Index of a Tree

We exhibit a close connection between hitting times of the simple random walk on a graph, the Wiener index, and related graph invariants. In the case of trees, we obtain a simple identity relating hitting times to the Wiener index. It is well known that the vertices of any graph can be put in a linear preorder so that vertices appearing earlier in the preorder are “easier to reach” by a random walk, but “more difficult to get out of.” We define various other natural preorders and study their relationships. These preorders coincide when the graph is a tree, but not necessarily otherwise. Our treatise is self‐contained, and puts some known results relating the behavior or random walk on a graph to its eigenvalues in a new perspective.     

Decoupling inequalities and interlacement percolation on <Emphasis Type="Italic">G</Emphasis>×ℤ

We study the percolative properties of random interlacements on G×ℤ, where G is a weighted graph satisfying certain sub-Gaussian estimates attached to the parameters α>1 and 2≤β≤α+1, describing the respective polynomial growths of the volume on G and of the time needed by the walk on G to move to a distance. We develop decoupling inequalities, which are a key tool in showing that the critical level u _∗ for the percolation of the vacant set of random interlacements is always finite in our set-up, and that it is positive when α≥1+β/2. We also obtain several stretched exponential controls both in the percolative and non-percolative phases of the model. Even in the case where G=ℤ ^d , d≥2, several of these results are new.     

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     

Quenched invariance principle for simple random walk on discrete point processes

We consider the simple random walk on random graphs generated by discrete point processes. This random walk moves on graphs whose vertex set is a random subset of a cubic lattice and whose edges are lines between any consecutive vertices on lines parallel to each coordinate axis. Under the assumption that the discrete point processes are finitely dependent and stationary, we prove that the quenched invariance principle holds, i.e., for almost every configuration of the point process, the path distribution of the walk converges weakly to that of a Brownian motion.     

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.     

Lévy processes with no positive jumps at an increase time

Summary We study the behaviour of a Lévy process with no positive jumps near its increase times. Specifically, we construct a local time on the set of increase times. Then, we describe the path decomposition at an increase time chosen at random according to the local time, and we evaluate the rate of escape before and after this instant.     

A lower bound on the critical parameter of interlacement percolation in high dimension

We investigate the percolative properties of the vacant set left by random interlacements on ${\mathbb{Z}^d}$ , when d is large. A non-negative parameter u controls the density of random interlacements on ${\mathbb{Z}^d}$ . It is known from Sznitman (Ann Math, 2010), and Sidoravicius and Sznitman (Comm Pure Appl Math 62(6):831?C858, 2009), that there is a non-degenerate critical value u _*, such that the vacant set at level u percolates when u < u _*, and does not percolate when u > u _*. Little is known about u _*, however, random interlacements on ${\mathbb{Z}^d}$ , for large d, ought to exhibit similarities to random interlacements on a (2d)-regular tree, where the corresponding critical parameter can be explicitly computed, see Teixeira (Electron J Probab 14:1604?C1627, 2009). We show in this article that lim inf _d ?u _*/ log d ?? 1. This lower bound is in agreement with the above mentioned heuristics.     

Fluctuations of shapes of large areas under paths of random walks

Summary We discuss statistical properties of random walks conditioned by fixing a large area under their paths. We prove the functional central limit theorem (invariance principle) for these conditional distributions. The limiting Gaussian measure coincides with the conditional probability distribution of certain timenonhomogeneous Gaussian random process obtained by an integral transformation of the white noise. From the point of view of statistical mechanics the studied problem is the problem of describing the fluctuations of the phase boundary in the one-dimensional SOS-model.     

Approximation for the Normal Inverse Gaussian Process Using Random Sums

Abstract

We approximate the normal inverse Gaussian (NIG) process with random summations. The random sum we introduce is a random walk subordinated to the first passage time of another independent random walk; the model is interpreted as an internal mechanism at small scale that generates the NIG process. The main result is a functional limit theorem of weak convergence in the Skorohod topology.     

Rare Events in Random Geometric Graphs

This work introduces and compares approaches for estimating rare-event probabilities related to the number of edges in the random geometric graph on a Poisson point process. In the one-dimensional setting, we derive closed-form expressions for a variety of conditional probabilities related to the number of edges in the random geometric graph and develop conditional Monte Carlo algorithms for estimating rare-event probabilities on this basis. We prove rigorously a reduction in variance when compared to the crude Monte Carlo estimators and illustrate the magnitude of the improvements in a simulation study. In higher dimensions, we use conditional Monte Carlo to remove the fluctuations in the estimator coming from the randomness in the Poisson number of nodes. Finally, building on conceptual insights from large-deviations theory, we illustrate that importance sampling using a Gibbsian point process can further substantially reduce the estimation variance.

     

On the local time of random walk on the 2-dimensional comb

We study the path behaviour of general random walks, and that of their local times, on the 2-dimensional comb lattice C² that is obtained from Z² by removing all horizontal edges off the x-axis. We prove strong approximation results for such random walks and also for their local times. Concentrating mainly on the latter, we establish strong and weak limit theorems, including Strassen-type laws of the iterated logarithm, Hirsch-type laws, and weak convergence results in terms of functional convergence in distribution.     

A local limit theorem for a transient chaotic walk in a frozen environment

This paper studies particle propagation in a one-dimensional inhomogeneous medium where the laws of motion are generated by chaotic and deterministic local maps. Assuming that the particle’s initial location is random and uniformly distributed, this dynamical system can be reduced to a random walk in a one-dimensional inhomogeneous environment with a forbidden direction. Our main result is a local limit theorem which explains in detail why, in the long run, the random walk’s probability mass function does not converge to a Gaussian density, although the corresponding limiting distribution over a coarser diffusive space scale is Gaussian.     

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.     

Lagging and leading coupled continuous time random walks, renewal times and their joint limits

Subordinating a random walk to a renewal process yields a continuous time random walk (CTRW), which models diffusion and anomalous diffusion. Transition densities of scaling limits of power law CTRWs have been shown to solve fractional Fokker-Planck equations. We consider limits of CTRWs which arise when both waiting times and jumps are taken from an infinitesimal triangular array. Two different limit processes are identified when waiting times precede jumps or follow jumps, respectively, together with two limit processes corresponding to the renewal times. We calculate the joint law of all four limit processes evaluated at a fixed time t.     

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.