Some arithmetic properties of short random walk integrals

We study the moments of the distance traveled by a walk in the plane with unit steps in random directions. While this historically interesting random walk is well understood from a modern probabilistic point of view, our own interest is in determining explicit closed forms for the moment functions and their arithmetic values at integers when only a small number of steps is taken. As a consequence of a more general evaluation, a closed form is obtained for the average distance traveled in three steps. This evaluation, as well as its proof, rely on explicit combinatorial properties, such as recurrence equations of the even moments (which are lifted to functional equations). The corresponding general combinatorial and analytic features are collected and made explicit in the case of 3 and 4 steps. Explicit hypergeometric expressions are given for the moments of a 3-step and 4-step walk and a general conjecture for even length walks is made.     

SOME LIMIT PROPERTIES OF LOCAL TIME FOR RANDOM WALK

Let X,X1,X2 be i. i. d. random variables with EX^2＋δ〈∞ （for some δ〉0）. Consider a one dimensional random walk S={Sn}n≥0, starting from S0 =0. Let ζ＊ （n）=supx∈zζ（x,n）,ζ（x,n） =#{0≤k≤n：[Sk]=x}. A strong approximation of ζ（n） by the local time for Wiener process is presented and the limsup type and liminf-type laws of iterated logarithm of the maximum local time ζ＊（n） are obtained. Furthermore,the precise asymptoties in the law of iterated logarithm of ζ＊（n） is proved.     

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.     

贪婪格点路径的一些性质

设{Xv:v∈Zd}是一族独立同分布的随机变量序列,对Zd上的任意一路径π,定义S(π)=∑v∈πXv,记Mn=maxπ∈Π0(n)S(π),Π0(n)表示从原点出发大小为n的自不相交的路径的全体.论文讨论Mn的性质,得到了类似完全收敛性的结果,即对任意的ε>0,∑∞n=11nPMnn-M>ε<∞.另外还讨论了Xv允许取负值的情形,得到类似的结果,从而推广了Gandolfi和Kesten所研究的贪婪格点路径模型.     

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     

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     

Spectral properties of evolutionary operators in branching random walk models

We introduce a model of continuous-time branching random walk on a finite-dimensional integer lattice with finitely many branching sources of three types and study the spectral properties of the operator describing the evolution of the mean numbers of particles both at an arbitrary source and on the entire lattice. For the leading positive eigenvalue of the operator, we obtain existence conditions determining exponential growth in the number of particles in this model.     

Some properties of random evolutions

We study asymptotic properties of matrix-valued random evolutions and consider an example of evolutions of this type.Deceased.Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 47, No. 10, pp. 1333–1337, October, 1995.     

Interpolating between random walk and rotor walk

We introduce a family of stochastic processes on the integers, depending on a parameter and interpolating between the deterministic rotor walk () and the simple random walk (). This p‐rotor walk is not a Markov chain but it has a local Markov property: for each the sequence of successive exits from is a Markov chain. The main result of this paper identifies the scaling limit of the p‐rotor walk with two‐sided i.i.d. initial rotors. The limiting process takes the form , where is a doubly perturbed Brownian motion, that is, it satisfies the implicit equation (1) for all . Here is a standard Brownian motion and are constants depending on the marginals of the initial rotors on and respectively. Chaumont and Doney have shown that Equation 1 has a pathwise unique solution , and that the solution is almost surely continuous and adapted to the natural filtration of the Brownian motion. Moreover, and . This last result, together with the main result of this paper, implies that the p‐rotor walk is recurrent for any two‐sided i.i.d. initial rotors and any .     

A non-integral-dimensional random walk

We present a space-homogeneous, time-inhomogeneous random walk that behaves as if it were a simple random walk ind dimensions, whered is not necessarily an integer. Analogues of the Local Central Limit Theorem, Zero-One Laws, distance, angle, asymptotics on the Green's function and the hitting probability, recurrence and transience, and results about the intersection behavior of the random walk paths are obtained.     

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.     

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     

Some properties of random number generators

Translated from Problemy Ustoichivosti Stokhasticheskikh Modelei, Trudy Seminara, pp. 36–40, 1987.     

Range of cube-indexed random walk

For given finite, connected, bipartite graphG=(V,E) with distinguishedν ₀ ∈V, set {fx189-1} Our main result says there is a fixedb so that whenG is a Hamming cube ({0, 1} ⁿ with the usual adjacency), andf is chosen uniformly fromF, the probability thatf takes more thanb values is at most e^?Ω(n). this settles in a very strong way a conjecture of I. Benjamini, O. Häggström and E. Mossel [2]. The proof is based on entropy considerations and a new log-concavity result.     

Some properties of multiparameter random fields

We study some properties of multiparameter random fields, namely, the problems of absolute continuity of measures and averaging in the multiparameter case. For a special stochastic system, we present inequalities of large deviations.Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 47, No. 12, pp. 1609–1621, December, 1995.