Revisits for transient random walk

For a random walk on the integers define R_n as the number of (distinct) states visited in the first n steps and Z_n as the number of states visited in the first n steps which are never revisited. Here we deal with transient walks. The increments of Z_n form a stationary process and various central limit results and an iterated logarithm result are obtained for Z_n from known results on stationary processes. Furthermore, the limit behaviour of R_n is closely related to that of Z_n; this relationship is elucidated and corresponding limit results for R_n are then read off from those for Z_n.     

On the sequence of Bayesian estimates of normal random walk process

Let (μ_t)^∞_t=0 be a k-variate (k?1) normal random walk process with successive increments being independently distributed as normal N(δ, R), and μ₀ being distributed as normal N(0, V₀). Let X_t have normal distribution N(μ_t, Σ) when μ_t is given, t = 1, 2,….Then the conditional distribution of μ_t given X₁, X₂,…, X_t is shown to be normal N(U_t, V_t) where U_t's and V_t's satisfy some recursive relations. It is found that there exists a positive definite matrix V and a constant θ, 0 < θ < 1, such that, for all t?1,

$\text{|R}\text{1}\text{2}\text{(V}{}^{\mathrm{?1}}{}_{\mathrm{t}}\text{?V}{}^{\mathrm{?1}}\text{R}\text{1}\text{2}\text{|<θ}{}^{\mathrm{t}}\text{|R}\text{1}\text{2}\text{(V}{}^{\mathrm{?1}}{}_0\text{?V}{}^{\mathrm{?1}}\text{)R}\text{1}\text{2}\text{|}$

where the norm |·| means that |A| is the largest eigenvalue of a positive definite matrix A. Thus, V_t approaches to V as t approaches to infinity. Under the quadratic loss, the Bayesian estimate of μ_t is U_t and the process {U_t}^∞_t=₀, U₀=0, is proved to have independent successive increments with normal N(θ, V_t?V_t+1+R) distribution. In particular, when V₀ =V then V_t = V for all t and {U_t}^∞_t=0 is the same as {μ_t}^∞_t=0 except that U₀ = 0 and μ₀ is random.     

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.     

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     

Two-boundary problems for a random walk

We solve main two-boundary problems for a random walk. The generating function of the joint distribution of the first exit time of a random walk from an interval and the value of the overshoot of the random walk over the boundary at exit time is determined. We also determine the generating function of the joint distribution of the first entrance time of a random walk to an interval and the value of the random walk at this time. The distributions of the supremum, infimum, and value of a random walk and the number of upward and downward crossings of an interval by a random walk are determined on a geometrically distributed time interval. We give examples of application of obtained results to a random walk with one-sided exponentially distributed jumps. __________ Translated from Ukrains’kyi Matematychnyi Zhurnal, Vol. 59, No. 11, pp. 1485–1509, November, 2007.     

一类随机环境下随机游动的常返性

就一类平稳环境θ下随机流动{Xn}n∈z 建立相应的Markov-双链{ηn}n∈z ={(xn,Tnθ)}n∈z ,并给出在该平稳环境θ下{xn}n∈z 为常返链的条件.     

A tauberian theorem for random walk

LetX ₁,X ₂,... be independent random variables, all with the same distribution symmetric about 0; $$S_n = \sum\limits_{i = 1}^n {X_i } $$ It is shown that if for some fixed intervalI, constant 1<a≦2 and slowly varying functionM one has $$\sum\limits_{k = 1}^n {P\{ S_k \in I\} \sim \frac{{n^{1 - 1/\alpha } }}{{M(n)}}} (n \to \infty )$$ then theX _i belong to the domain of attraction of a symmetric stable law.     

Moderate deviations for a random walk in random scenery

We investigate the cumulative scenery process associated with random walks in independent, identically distributed random sceneries under the assumption that the scenery variables satisfy Cramér’s condition. We prove moderate deviation principles in dimensions d≥2$d\ge 2$, covering all those regimes where rate and speed do not depend on the actual distribution of the scenery. For the case d≥4$d\ge 4$ we even obtain precise asymptotics for the probability of a moderate deviation, extending a classical central limit theorem of Kesten and Spitzer. For d≥3$d\ge 3$, an important ingredient in the proofs are new concentration inequalities for self-intersection local times of random walks, which are of independent interest, whilst for d=2$d=2$ we use a recent moderate deviation result for self-intersection local times, which is due to Bass, Chen and Rosen.     

Specifying absorption probabilities for the simple random walk

In the theory of the simple random walk an important problem is the determination of absorption probabilities. This paper considers the inverse problem in which for specified absorption probabilities, feasible regions are determined for the set of possible initial probability vectors which could generate such probabilities.     

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 .     

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.     

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.     

Strong approximation for the general Kesten-Spitzer random walk in independent random scenery

This paper is to prove that, if a one-dimensional random wa lkcan be approximated by a Brownian motion, then the related random walk in a g eneral independent scenery can be approximated by a Brownian motion in Brownian scenery.