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 thatX_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