The disconnection exponent for simple random walk

LetS(t) denote a simple random walk inZ ² with integer timet. The disconnection exponent is defined by saying the probability that the path ofS starting at 0 and ending at the circle of radiusn disconnects 0 from infinity decays like . We prove that the disconnection exponent is well-defined and equals the disconnection exponent for Brownian motion which is known to exist. Research supported by the National Science Foundation.     

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.     

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.     

Two explicit Skorokhod embeddings for simple symmetric random walk

Motivated by problems in behavioural finance, we provide two explicit constructions of a randomized stopping time which embeds a given centred distribution $\mu$ on integers into a simple symmetric random walk in a uniformly integrable manner. Our first construction has a simple Markovian structure: at each step, we stop if an independent coin with a state-dependent bias returns tails. Our second construction is a discrete analogue of the celebrated Azéma–Yor solution and requires independent coin tosses only when excursions away from maximum breach predefined levels. Further, this construction maximizes the distribution of the stopped running maximum among all uniformly integrable embeddings of $\mu$.     

The simple random walk and max‐degree walk on a directed graph

We bound total variation and L^∞ mixing times, spectral gap and magnitudes of the complex valued eigenvalues of general (nonreversible nonlazy) Markov chains with a minor expansion property. The resulting bounds for the (nonlazy) simple and max‐degree walks on a (directed) graph are of the optimal order. It follows that, within a factor of two or four, the worst case of each of these mixing time and eigenvalue quantities is a walk on a cycle with clockwise drift. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

Quenched invariance principle for simple random walk on percolation clusters

We consider the simple random walk on the (unique) infinite cluster of super-critical bond percolation in ℤ ^d with d≥2. We prove that, for almost every percolation configuration, the path distribution of the walk converges weakly to that of non-degenerate, isotropic Brownian motion. Our analysis is based on the consideration of a harmonic deformation of the infinite cluster on which the random walk becomes a square-integrable martingale. The size of the deformation, expressed by the so called corrector, is estimated by means of ergodicity arguments.     

The most visited site of Brownian motion and simple random walk

Summary Let L(t, x) be the local time at x for Brownian motion and for each t, let } 0;L(t,x) \vee L(t, - x) = \mathop {\sup }\limits_y L(t,y)\} $$ " align="middle" border="0"> , the absolute value of the most visited site for Brownian motion up to time t. In this paper we prove that ¯V(t) is transient and obtain upper and lower bounds for the rate of growth of ¯V(t). The main tools used are the Ray-Knight theorems and William's path decomposition of a diffusion. An invariance principle is used to get analogous results for simple random walks. We also obtain a law of the iterated logarithm for ¯V(t).This research was partially supported by NSF Grants MCS 83-00581 and MCS 83-03297     

The mean number of sites visited by a pinned random walk

This paper concerns the number Z _n of sites visited up to time n by a random walk S _n having zero mean and moving on the d-dimensional square lattice Z ^d . Asymptotic evaluation of the conditional expectation of Z _n given that S ₀ = 0 and S _n = x is carried out under 2 + δ moment conditions (0 ≤ δ ≤ 2) in the cases d = 2, 3. It gives an explicit form of the leading term and reasonable estimates of the remainder term (depending on δ) valid uniformly in each parabolic region of (x, n). In the case x = 0 the problem has been studied for the simple random walk and its analogue for Brownian motion; the estimates obtained here are finer than or comparable to those found in previous works. Supported in part by Monbukagakusho grand-in-aid no. 15540109.     

Uniform recursive trees: Branching structure and simple random downward walk

As models for spread of epidemics, family trees, etc., various authors have used a random tree called the uniform recursive tree. Its branching structure and the length of simple random downward walk (SRDW) on it are investigated in this paper. On the uniform recursive tree of size n, we first give the distribution law of ζn,m, the number of m-branches, whose asymptotic distribution is the Poisson distribution with parameter . We also give the joint distribution of the numbers of various branches and their covariance matrix. On Ln, the walk length of SRDW, we first give the exact expression of P(Ln=2). Finally, the asymptotic behavior of Ln is given.     

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.     

Number of distinct sites visited by a random walk with internal states

In the classical paper of Dvoretzky and Erd?s (Proceedings of the 2nd Berkeley Symposium on Mathematical Statistics and Probability, pp 353?C367, 1951), asymptotics for the expected value and the variance of the number of distinct sites visited by a Simple Symmetric Random Walk were calculated. Here, these results are generalized for Random Walks with Internal States. Moreover, both weak and strong laws of large numbers are proved. As a tool for these results, the error term of the local limit theorem in Krámli and Szász (Zeitschrift Wahrscheinlichkeitstheorie verw Gebiete 63:85?C95, 1983) is also estimated.     

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     

Asymptotics of the transition probabilities of the simple random walk on self-similar graphs

It is shown explicitly how self-similar graphs can be obtained as `blow-up' constructions of finite cell graphs . This yields a larger family of graphs than the graphs obtained by discretising continuous self-similar fractals.

For a class of symmetrically self-similar graphs we study the simple random walk on a cell graph , starting at a vertex of the boundary of . It is proved that the expected number of returns to before hitting another vertex in the boundary coincides with the resistance scaling factor.

Using techniques from complex rational iteration and singularity analysis for Green functions, we compute the asymptotic behaviour of the -step transition probabilities of the simple random walk on the whole graph. The results of Grabner and Woess for the Sierpinski graph are generalised to the class of symmetrically self-similar graphs, and at the same time the error term of the asymptotic expression is improved. Finally, we present a criterion for the occurrence of oscillating phenomena of the -step transition 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 .     

On the first passage time of a simple random walk on a tree

We consider a simple random walk on a tree. Exact expressions are obtained for the expectation and the variance of the first passage time, thereby recovering the known result that these are integers. A relationship of the mean first passage matrix with the distance matrix is established and used to derive a formula for the inverse of the mean first passage matrix.     

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.