Moments of escape times of random walk

Extending an idea of Spitzer [2], a way to compute the moments of the time of escape from (−N,L) by a symmetric simple random walk is exhibited. It is shown that all these moments depend polynomially onL andN. The research of this author was supported by the National Board of Higher Mathematics, Bombay, India     

Distinguishing sceneries by observing the scenery along a random walk path

LetG be an infinite connected graph with vertex setV. Ascenery onG is a map ξ :V → 0, 1 (equivalently, an assignment of zeroes and ones to the vertices ofG). LetS _{n n≥0} be a simple random walk onG, starting at some distinguished vertex v₀. Now let ξ and η be twoknown sceneries and assume that we observe one of the two sequences ξ(S _n) _n≥0 or {η(S _n)} _n≥0 but we do not know which of the two sequences is observed. Can we decide, with a zero probability of error, which of the two sequences is observed? We show that ifG = Z orG = Z², then the answer is “yes” for each fixed ξ and “almost all” η. We also give some examples of graphsG for which almost all pairs (ξ, η) are not distinguishable, and discuss some variants of this problem.     

Almost-sure central limit theorem for a Markov model of random walk in dynamical random environment

Summary We consider a model of random walk on ℤ^ν, ν≥2, in a dynamical random environment described by a field ξ={ξ _t (x): (t,x)∈ℤ^ν+1}. The random walk transition probabilities are taken as P(X _{t +1}= y|X _t = x,ξ _t =η) =P ₀( y−x)+ c(y−x;η(x)). We assume that the variables {ξ _t (x):(t,x) ∈ℤ^ν+1} are i.i.d., that both P ₀(u) and c(u;s) are finite range in u, and that the random term c(u;·) is small and with zero average. We prove that the C.L.T. holds almost-surely, with the same parameters as for P ₀, for all ν≥2. For ν≥3 there is a finite random (i.e., dependent on ξ) correction to the average of X _t , and there is a corresponding random correction of order to the C.L.T.. For ν≥5 there is a finite random correction to the covariance matrix of X _t and a corresponding correction of order to the C.L.T.. Proofs are based on some new L ^p estimates for a class of functionals of the field. Received: 4 January 1996/In revised form: 26 May 1997     

Occupation measure for random walk on the circle

We give bounds on the probability of deviation of the occupation measure of an interval on the circle for random walk.     

An iterative approximation procedure for the distribution of the maximum of a random walk

Let I(F) be the distribution function (d.f.) of the maximum of a random walk whose i.i.d. increments have the common d.f. F and a negative mean. We derive a recursive sequence of embedded random walks whose underlying d.f.'s F_k converge to the d.f. of the first ladder variable and satisfy FF₁F₂ on [0,∞) and I(F)=I(F₁)=I(F₂)=. Using these random walks we obtain improved upper bounds for the difference of I(F) and the d.f. of the maximum of the random walk after finitely many steps.     

Asymptotic normality of the size of the giant component via a random walk

In this paper we give a simple new proof of a result of Pittel and Wormald concerning the asymptotic value and (suitably rescaled) limiting distribution of the number of vertices in the giant component of G(n,p) above the scaling window of the phase transition. Nachmias and Peres used martingale arguments to study Karp?s exploration process, obtaining a simple proof of a weak form of this result. We use slightly different martingale arguments to obtain a much sharper result with little extra work.     

A subdiffusive behaviour of recurrent random walk in random environment on a regular tree

We are interested in the random walk in random environment on an infinite tree. Lyons and Pemantle (Ann. Probab. 20, 125–136, 1992) give a precise recurrence/transience criterion. Our paper focuses on the almost sure asymptotic behaviours of a recurrent random walk (X _n ) in random environment on a regular tree, which is closely related to Mandelbrot’s (C. R. Acad. Sci. Paris 278, 289–292, 1974) multiplicative cascade. We prove, under some general assumptions upon the distribution of the environment, the existence of a new exponent such that behaves asymptotically like . The value of ν is explicitly formulated in terms of the distribution of the environment.      

Convergence of a random walk method for a partial differential equation

A Cauchy problem for a one-dimensional diffusion-reaction equation is solved on a grid by a random walk method, in which the diffusion part is solved by random walk of particles, and the (nonlinear) reaction part is solved via Euler's polygonal arc method. Unlike in the literature, we do not assume monotonicity for the initial condition. It is proved that the algorithm converges and the rate of convergence is of order , where is the spatial mesh length.

     

Some sample path properties of a random walk on the cube

Some properties of the set of vertices not visited by a random walk on the cube are considered. The asymptotic distribution of the first timeQ this set is empty is derived. The distribution of the number of vertices not visited is found for times nearEQ. Next the first time all unvisited vertices are at least some distanced apart is explored. Finally the expected time taken by the path to come within a distanced of all points is calculated. These results are compared to similar results for random allocations.     

Random walk in a high density dynamic random environment

The goal of this note is to prove a law of large numbers for the empirical speed of a green particle that performs a random walk on top of a field of red particles which themselves perform independent simple random walks on Z^d${\mathbb{Z}}^d$, d≥1$d\ge 1$. The red particles jump at rate 1 and are in a Poisson equilibrium with density μ$\mu$. The green particle also jumps at rate 1, but uses different transition kernels p^′$p^{\prime }$ and p^″$p^{″}$ depending on whether it sees a red particle or not. It is shown that, in the limit as μ→∞$\mu \to \infty$, the speed of the green particle tends to the average jump under p^′$p^{\prime }$. This result is far from surprising, but it is non-trivial to prove. The proof that is given in this note is based on techniques that were developed in Kesten and Sidoravicius (2005) to deal with spread-of-infection models. The main difficulty is that, due to particle conservation, space–time correlations in the field of red particles decay slowly. This places the problem in a class of random walks in dynamic random environments for which scaling laws are hard to obtain.     

Moments and distribution of the local time of a two-dimensional random walk

Let ?(n,x)$?(n,x)$ be the local time of a random walk on Z²${\mathbb{Z}}^2$. We prove a strong law of large numbers for the quantity _Ln(α)=_∑x∈Z2?(n,x)^α$L_n\left(\alpha \right)={\sum }_{x\in {\mathbb{Z}}^2}?{(n,x)}^{\alpha }$ for all α≥0$\alpha \ge 0$. We use this result to describe the distribution of the local time of a typical point in the range of the random walk.     

Upper limits of Sinai’s walk in random scenery

We consider Sinai’s walk in i.i.d. random scenery and focus our attention on a conjecture of Révész concerning the upper limits of Sinai’s walk in random scenery when the scenery is bounded from above. A close study of the competition between the concentration property for Sinai’s walk and negative values for the scenery enables us to prove that the conjecture is true if the scenery has “thin” negative tails and is false otherwise.     

Scaling exponents of random walks in random sceneries

We compute the exact asymptotic normalizations of random walks in random sceneries, for various null recurrent random walks to the nearest neighbours, and for i.i.d., centered and square integrable random sceneries. In each case, the standard deviation grows like n with . Here, the value of the exponent is determined by the sole geometry of the underlying graph, as opposed to previous examples, where this value reflected mainly the integrability properties of the steps of the walk, or of the scenery. For discrete Bessel processes of dimension d[0;2[, the exponent is . For the simple walk on some specific graphs, whose volume grows like n^d for d[1;2[, the exponent is =1−d/4. We build a null recurrent walk, for which without logarithmic correction. Last, for the simple walk on a critical Galton–Watson tree, conditioned by its nonextinction, the annealed exponent is . In that setting and when the scenery is i.i.d. by levels, the same result holds with .     

Random walk on the random connection model

We study the behavior of the random walk in a continuum independent long-range percolation model, in which two given vertices $x$ and $y$ are connected with probability that asymptotically behaves like ${|x?y|}^{?\alpha }$ with $\alpha >d$, where $d$ denotes the dimension of the underlying Euclidean space. More precisely, focus is on the random connection model in which the vertex set is given by the realization of a homogeneous Poisson point process. We show that this random graph exhibits similar properties as classical discrete long-range percolation models studied by Berger (2002) with regard to recurrence and transience of the random walk. Moreover, we address a question which is related to a conjecture by Heydenreich, Hulshof and Jorritsma (2017) for this graph.     

Large deviations for hitting times of a random walk in random environment on a strip

We consider a random walk in random environment on a strip, which is transient to the right. The random environment is stationary and ergodic. By the constructed enlarged random environment which was first introduced by Goldsheid （2008）, we obtain the large deviations conditioned on the environment （in the quenched case） for the hitting times of the random walk.     

Scaling limit theorem for transient random walk in random environment

We construct a sequence of transient random walks in random environments and prove that by proper scaling, it converges to a diffusion process with drifted Brownian potential. To this end, we prove a counterpart of convergence for transient random walk in non-random environment, which is interesting itself.     

Extremum of a time-inhomogeneous branching random walk

Consider a time-inhomogeneous branching random walk, generated by the point process L_n which composed by two independent parts: ‘branching’offspring X_n with the mean \mathrm{1}+{B(\mathrm{1}+n)}^{-\beta } for \beta \in (\mathrm{0},\mathrm{1}) and ‘displacement’ {{\displaystyle \xi }}_n with a drift {A(\mathrm{1}+n)}^{-\mathrm{2}\alpha } for \alpha \in (\mathrm{0},\mathrm{1}/\mathrm{2}), where the ‘branching’ process is supercritical for B>0 but ‘asymptotically critical’ and the drift of the ‘displacement’ {{\displaystyle \xi }}_n is strictly positive or negative for \left|A\right|\rangle \mathrm{0} but ‘asymptotically’ goes to zero as time goes to infinity. We find that the limit behavior of the minimal (or maximal) position of the branching random walk is sensitive to the ‘asymptotical’ parameter \beta and \alpha.     

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