Degree Type


Date of Award


Degree Name

Doctor of Philosophy




Applied Mathematics

First Advisor

Alexander Roiterchtein


Excited random walks (ERW) or random walks in a cookie environment is a modification of the nearest neighbor simple random walk such that in several first visits to each site of the integer lattice, the walk’s jump kernel gives a preference to a certain direction and assigns equal probabilities to the remaining directions. If the current location of the random walk has been already visited more than a certain number of times, then the walk moves to one of its nearest neighbors with equal probabilities. The model was introduced by Benjamini and Wilson and extended by Martin Zerner. In the cookies jargon, upon first several visits to every site of the lattice, the walker consumes a cookie providing them a boost toward a distinguished direction in the next step. The excited random walk is a popular mainstream model of theoretical probability. An interesting application of this model to the motion of DNA molecular motors has been discovered by Antal and Krapivsky (Phys. Review E, 2007), see also the article of Mark Buchanan Attack of the cyberspider in Nature Physics, 2009.

Many basic asymptotic properties of excited random walk have their counterparts for random walk in random environment (RWRE). The major difference between two processes is that while the random (cookie) environment is dynamic and rapidly changes with time the environments considered in the RWRE process are stationary both in space and in time. The similarity between the asymptotic behaviors of these two classes of random walks can be ex- plained using the fact that certain functionals (for instance, exit times and exit probabilities) of the local time (or occupation time, also referred to as the number of previous visits to a current location) process converge after a proper rescaling to diffusion processes with time- independent coefficients. Thus phenomenon, discovered by Kosygina and Mountford, can be exploited for a heuristic explanation of the analogy between the role of the local drift of ERW (bias created by the cookie environment) and a random potential which governs the behavior of RWRE.

In this thesis we consider an excited random walk on Z with the jump kernel that depends not only on the number of cookies present at the current location of the walker, but also on direction from which the current location is entered. Random walks with the jump kernel that depends not only on the current location and possibly the history of the random walk at this location but also on the direction where the current location is visited from are usually referred to as persistent random walks. We therefore refer to our model as an persistent random walk in a cookie environment (PRWCE).

We prove recurrence and transience criteria and derive a necessary and sufficient condition for the asymptotic speed of the walk to be strictly positive. The law of large number in the transient case is complement by a central limit theorem for the position of the random walk. Surprisingly, it turns out that a transient PRWCE even in one dimension does not necessarily satisfy the usual 0 − 1 for the direction of the escape. More precisely, due to irreversibility of an associated with the cookie environment Markov process that governs the random motion, it is possible that a transient PRWCE on integers will escape to both negative and positive directions with non-zero probabilities. This is in the strike contrast to the usual ERW and to the one-dimensional persistent random walk in random environment where the associated Markov process (decisions of the walker modelled by a coin-tossing procedure) turns out to be a reversible Markov chain.

The investigation of the asymptotic behavior of a recurrent PRWCE and to a large extent of the transient walk in the case when the 0 − 1 law is violated remain a subject of the future investigation. Two additional interesting problems that are discussed in the thesis and remain unsolved are stable (non-Gaussian) limit theorems and the asymptotic behavior of the maximum local time. For all these open problems we state conjectures regarding the expected behavior of the random walk and indicate plausible strategies for proving this conjectures.

Our proof technique rely on a suitable extension of a Ray-Knight type theorem obtained for usual excited random walks in dimension one by Kosygina and Zerner. The theorem establishes a relation between asymptotic behavior of the random walk and basic properties of certain branching-type processes. Informally speaking, the duality between branching processes and nearest-neighbor random walks describes excursions of a random walk as a branching structure: each jump from a site n − 1 to n creates an opportunity for jumps from n to n = 1 (children in the language of branching). The correspondence between occupation times of random walks and branching processes carries over to processes in random environment and supplies a powerful technique for investigation of the asymptotic behavior of, for instance, random walk in random environments and excited random walks on Z.

As it was shown by Kosygina and Mountford, stable limit laws for excited random walks in dimension one are essentially equivalent to certain scaling properties of the branching processes associated with the Ray-Knight interpretation of the local times. Proving these scaling properties for the PRWCE is a subject of the ongoing investigation and remains beyond the scope of the thesis.

Copyright Owner

Zachary David Voller



File Format


File Size

49 pages

Included in

Mathematics Commons