On the average of a random walk

Let {S_n, n ϵ N)} be a simple random walk and denote by A_n its time average: A_n = (S₁+ …+S_n)/n. We give an integral test for the lower bound on A_n, thus giving an affirmative answer to a conjecture of P. Erdös (private communication) that A_n will return to a fixed region around the origin infinitely often with probability 1 in 1 dimension whereas in 2 or more dimensions it will return only finitely many times.     

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.      

On convergent probability of a random walk

This note introduces an interesting random walk on a straight path with cards of random numbers. The method of recurrent relations is used to obtain the convergent probability of the random walk with different initial positions.     

On the range of random walk

Let {S _n , n=0, 1, 2, …} be a random walk (S _n being thenth partial sum of a sequence of independent, identically distributed, random variables) with values inE _d , thed-dimensional integer lattice. Letf _n =Prob {S ₁ ≠ 0, …,S _n −1 ≠ 0,S _n =0 |S ₀=0}. The random walk is said to be transient if and strongly transient if . LetR _n =cardinality of the set {S ₀,S ₁, …,S _n }. It is shown that for a strongly transient random walk with p<1, the distribution of [R _n −np]/σ √n converges to the normal distribution with mean 0 and variance 1 asn tends to infinity, where σ is an appropriate positive constant. The other main result concerns the “capacity” of {S ₀, …,S _n }. For a finite setA inE _d , let C(A=Σ _x∈A ) Prob {S _n ∉A, n≧1 |S ₀=x} be the capacity ofA. A strong law forC{S ₀, …,S _n } is proved for a transient random walk, and some related questions are also considered. This research was partially supported by the National Science Foundation.     

On the centre of mass of a random walk

For a random walk $S_n$ on ${\mathbb{R}}^d$ we study the asymptotic behaviour of the associated centre of mass process $G_n=n^{?1}{\sum }_{i=1}^n{S}_i$. For lattice distributions we give conditions for a local limit theorem to hold. We prove that if the increments of the walk have zero mean and finite second moment, $G_n$ is recurrent if $d=1$ and transient if $d\ge 2$. In the transient case we show that $G_n$ has a diffusive rate of escape. These results extend work of Grill, who considered simple symmetric random walk. We also give a class of random walks with symmetric heavy-tailed increments for which $G_n$ is transient in $d=1$.     

On not storing the path of a random walk

We describe a novel form of Monte Carlo method with which to study self-avoiding random walks; we do not (in any sense) store the path of the walk being considered. As we show, the problem is related to that of devising a random-number generator which can produce itsnth number on request, without running through its sequence up to this point.     

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.     

On the set visited once by a random walk

Summary In this paper we prove the following statement. Given a random walk ,n=1, 2, ... where ₁, ₂ ... are i.i.d. random variables, let (n) denote the number of points visited exactly once by this random walk up to timen. We show that there exists some constantC, 0 <C < , such that with probability 1. The proof applies some arguments analogous to the techniques of the large deviation theory.Research supported by the Hungarian National Foundation for Scientific Research, Grant N^o # 819/1     

On the sojourn time of a random walk in a strip

We obtain asymptotic representations for the triple transforms of the joint distribution of the sojourn time of a random walk in a strip (as well as in a half-plane) in n steps and of the location at time n under the condition of unboundedly moving-off boundaries of the sets. The Cramér type conditions are imposed on the distribution of jumps.     

On the disconnection of a discrete cylinder by a random walk

We investigate the large N behavior of the time the simple random walk on the discrete cylinder needs to disconnect the discrete cylinder. We show that when d≥2, this time is roughly of order N ^{2 d} and comparable to the cover time of the slice , but substantially larger than the cover timer of the base by the projection of the walk. Further we show that by the time disconnection occurs, a massive ``clogging' typically takes place in the truncated cylinders of height . These mechanisms are in contrast with what happens when d=1.     

Asymptotic expansion of a semi-Markov random evolution

We determine the regular and singular components of the asymptotic expansion of a semi-Markov random evolution and show the regularity of boundary conditions. In addition, we propose an algorithm for finding initial conditions for t = 0 in explicit form using the boundary conditions for the singular component of the expansion. __________ Translated from Ukrains’kyi Matematychnyi Zhurnal, Vol. 58, No. 9, pp. 1234–1248, September, 2006.     

On the mean square displacement of a random walk on a graph

We study a relation between Ollivier’s Ricci curvature and the mean square displacement of a random walk on a graph. Also we obtain explicit formulas for the mean square displacement of random walks on regular polyhedra.     

On the support of the simple branching random walk

Connectivity of the support of the simple branching random walk is established in certain asymmetric cases, extending a previous result of Grill.     

Distribution of the lower boundary functional of the step process of semi-Markov random walk with delaying screen at zero

On the basis of a given sequence of independent identically distributed pairs of random variables, we construct the step process of semi-Markov random walk that is later delayed by a screen at zero. For this process, we obtain the Laplace transform of the distribution of the time of the first hit of the level zero. __________ Translated from Ukrains’kyi Matematychnyi Zhurnal, Vol. 59, No. 7, pp. 912–919, July, 2007.