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.     

Biased Random Walk on Lamplighter Groups and Graphs

Lyons, Pemantle, and Peres⁽⁴⁾ found an example of a group on which a simple random walk has sublinear speed but an inward biased walk has linear speed. We examine a similar example by introducing a martingale that allows us to compute the exact speed of the inward biased walk. We apply the martingale techniques to the example of Lyons et al., and improve on their speed estimates for small amounts of bias. Finally, we examine the speed on a related family of graphs and construct an example on which the speed of the walk has a second phase change.     

Once edge-reinforced random walk on a tree

 We consider a nearest neighbor walk on a regular tree, with transition probabilities proportional to weights or conductances of the edges. Initially all edges have weight 1, and the weight of an edge is increased to $c > 1$ when the edge is traversed for the first time. After such a change the weight of an edge stays at $c$ forever. We show that such a walk is transient for all values of $c \ge 1$, and that the walk moves off to infinity at a linear rate. We also prove an invariance principle for the height of the walk. Received: 6 March 2001 / Revised version: 16 July 2001 / Published online: 15 March 2002     

The monotonicity of the probability of return into the source in models of branching random walks

The paper discusses two models of a branching random walk on a many-dimensional lattice with birth and death of particles at a single node being the source of branching. The random walk in the first model is assumed to be symmetric. In the second model an additional parameter is introduced which enables “artificial” intensification of the prevalence of branching or walk at the source and, as the result, violating the symmetry of the random walk. The monotonicity of the return probability into the source is proved for the second model, which is a key property in the analysis of branching random walks.     

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.     

Critical survival barrier for branching random walk

We consider a branching random walk with an absorbing barrier, where the associated one-dimensional random walk is in the domain of attraction of an α-stable law. We shall prove that there is a barrier and a critical value such that the process dies under the critical barrier, and survives above it. This generalizes previous result in the case that the associated random walk has finite variance.     

An approximation algorithm for the hamiltonian walk problem on maximal planar graphs

A hamiltonian walk of a graph is a shortest closed walk that passes through every vertex at least once, and the length is the total number of traversed edges. The hamiltonian walk problem in which one would like to find a hamiltonian walk of a given graph is NP-complete. The problem is a generalized hamiltonian cycle problem and is a special case of the traveling salesman problem. Employing the techniques of divide-and-conquer and augmentation, we present an approximation algorithm for the problem on maximal planar graphs. The algorithm finds, in O(p²) time, a closed spanning walk of a given arbitrary maximal planar graph, and the length of the obtained walk is at most $\text{3}\text{2}$(p ? 3) if the graph has p (≥ 9) vertices. Hence the worst-case bound is $\text{3}\text{2}$.     

Approximation of the expectation of the first exit time from an interval for a random walk

We obtain asymptotic expansions for the expectation of the first exit time from an expanding strip for a random walk trajectory. We suppose that the distribution of random walk jumps satisfies the Cramér condition on the existence of an exponential moment.     

Slowdown and neutral pockets for a random walk in random environment

We consider a d-dimensional random walk in random environment for which transition probabilities at each site are either neutral or present an effective drift “pointing to the right”. We obtain large deviation estimates on the probability that the walk moves in a too slow ballistic fashion, both under the annealed and quenched measures. These estimates underline the key role of large neutral pockets of the medium in the occurrence of slowdowns of the walk. Received: 12 March 1998 / Revised version: 19 February 1999     

First Hitting Times for Some Random Walks on Finite Groups

We consider a random walk on a finite group G based on a generating set that is a union of conjugacy classes. Let the nonnegative integer valued random variable T denote the first time the walk arrives at the identity element of G, if the starting point of the walk is uniformly distributed on G. Under suitable hypotheses, we show that the distribution function F of T is almost exponential, and we give an error term.     

An upper bound on the length of a Hamiltonian walk of a maximal planar graph

A Hamiltonian walk of a connected graph is a shortest closed walk that passes through every vertex at least once, and the length of a Hamiltonian walk is the total number of edges traversed by the walk. We show that every maximal planar graph with p(≥ 3) vertices has a Hamiltonian cycle or a Hamiltonian walk of length ≤ 3(p - 3)/2.     

Crossing velocities for an annealed random walk in a random potential

We consider a random walk in an i.i.d. non-negative potential on the d-dimensional integer lattice. The walk starts at the origin and is conditioned to hit a remote location y on the lattice. We prove that the expected time under the annealed path measure needed by the random walk to reach y grows only linearly in the distance from y to the origin. In dimension 1 we show the existence of the asymptotic positive speed.     

Level crossing probabilities II: Polygonal recurrence of multidimensional random walks

In part I we proved for an arbitrary one-dimensional random walk with independent increments that the probability of crossing a level at a given time n is O(n−1/2). In higher dimensions we call a random walk ‘polygonally recurrent’ if there is a bounded set, hit by infinitely many of the straight lines between two consecutive sites a.s. The above estimate implies that three-dimensional random walks with independent components are polygonally transient. Similarly a directionally reinforced random walk on Z³ in the sense of Mauldin, Monticino and von Weizsäcker [R.D. Mauldin, M. Monticino, H. von Weizsäcker, Directionally reinforced random walks, Adv. Math. 117 (1996) 239-252] is transient. On the other hand, we construct an example of a transient but polygonally recurrent random walk with independent components on Z².     

Weak convergence of integral functionals of random walks weakly convergent to fractional Brownian motion

We consider a random walk that converges weakly to a fractional Brownian motion with Hurst index H > 1/2. We construct an integral-type functional of this random walk and prove that it converges weakly to an integral constructed on the basis of the fractional Brownian motion. __________ Translated from Ukrains’kyi Matematychnyi Zhurnal, Vol. 59, No. 8, pp. 1040–1046, August, 2007.     

Reconstructing a random scenery observed with random errors along a random walk path

 We show that an i.i.d. uniformly colored scenery on ℤ observed along a random walk path with bounded jumps can still be reconstructed if there are some errors in the observations. We assume the random walk is recurrent and can reach every point with positive probability. At time k, the random walker observes the color at her present location with probability 1−δ and an error Y _k with probability δ. The errors Y _k , k≥0, are assumed to be stationary and ergodic and independent of scenery and random walk. If the number of colors is strictly larger than the number of possible jumps for the random walk and δ is sufficiently small, then almost all sceneries can be almost surely reconstructed up to translations and reflections. Received: 3 February 2002 / Revised version: 15 January 2003 Published online: 28 March 2003 Mathematics Subject Classification (2000): 60K37, 60G50 Key words or phrases:Scenery reconstruction – Random walk – Coin tossing problems     

The survival of branching annihilating random walk

Summary Branching annihilating random walk is an interacting particle system on . As time evolves, particles execute random walks and branch, and disappear when they meet other particles. It is shown here that starting from a finite number of particles, the system will survive with positive probability if the random walk rate is low enough relative to the branching rate, but will die out with probability one if the random walk rate is high. Since the branching annihilating random walk is non-attractive, standard techniques usually employed for interacting particle systems are not applicable. Instead, a modification of a contour argument by Gray and Griffeath is used.     

Random Walks on Trees and an Inequality of Means

We define trees generated by bi-infinite sequences, calculate their walk-invariant distribution and the speed of a biased random walk. We compare a simple random walk on a tree generated by a bi-infinite sequence with a simple random walk on an augmented Galton-Watson tree. We find that comparable simple random walks require the augmented Galton-Watson tree to be larger than the corresponding tree generated by a bi-infinite sequence. This is due to an inequality for random variables with values in [1, [ involving harmonic, geometric and arithmetic mean.     

Slow movement of a random walk on the range of a random walk in the presence of an external field

In this article, a localisation result is proved for the biased random walk on the range of a simple random walk in high dimensions ( $d\ge 5$ ). This demonstrates that, unlike in the supercritical percolation setting, a slowdown effect occurs as soon as a non-trivial bias is introduced. The proof applies a decomposition of the underlying simple random walk path at its cut-times to relate the associated biased random walk to a one-dimensional random walk in a random environment in Sinai’s regime. Via this approach, a corresponding aging result is also proved.     

Random walks in random environment: What a single trajectory tells

We present a procedure that determines the law of a random walk in an iid random environment as a function of a single “typical” trajectory. We indicate when the trajectory characterizes the law of the environment, and we say how this law can be determined. We then show how independent trajectories having the distribution of the original walk can be generated as functions of the single observed trajectory.