M.Sc Thesis
M.Sc Student Lev-Ari Anat Random Walks in Cookie Environment Department of Mathematics Professor Ross Pinsky

Abstract

In this work we consider two generalizations of a simple random walk on the integers. In the first one, we take a transient random walk with the following transition probabilities: there is a constant K such that at the i-th visit to a point x, for i≤K, the probability for the process to jump right is ω(x,i)≤1/2 and to jump left is 1-ω(x,i). After the K-th visit to x, the probabilities to jump left and right change to 1/2. The sequence

ω={{ω(x,i) }i=1,...,K}xZ is called a one-sided cookie environment with a uniformly bounded number of cookies per site. We give a new and simpler proof that if ω(x,i)=p≥1/2 for all integer number x, i=1,...,K, and p>1/2+1/K, then it is also ballistic, i.e. liminfn→∞Xn/n>0 a.s.. The transient random walk will visit each site finitely many times a.s. and eventually escape to infinity leaving a trail of leftover cookies. Those leftovers cookies make a new cookie environment, which we call the leftovers environment, and we can place a new random walk on it. We show that if ω={{ω(x,i) }i=1,...,K}xZ is an i.i.d. sequence, the second process is transient if and only if the first one is ballistic.

In the second generalization, we consider a transient random walk with the following transition probabilities: at each point x the probability to jump right is ω(x)=p≥1/2 as long as the process keeps jumping right from x. The first time it jumps left from x the transition probabilities change for 1/2 to each direction. We show that the leftovers environment is stationary and ergodic, give a necessary and sufficient condition for the second random walk to be transient or to be recurrent, and give a sufficient condition for the random walk to be ballistic.