Reinforced random walk

In this worksheet, we will consider a natural random walk process, that is not Markovian.

The reinforced random walk on the integers is defined as follows: if you are \(i \in \mathbb{Z}\), then you can only go to \(i+1\) or \(i-1\), and you move to \(i+1\) with probability \(v(i+1)/[v(i-1) + v(i+1)]\), where \(v(j)\) is the total number of times an integer \(j\) has already been visited. Initially, we take \(v=1\) everywhere.

It is a theorem of Tarres (2004) that the walk will eventually get stuck on five vertices. In this worksheet we will try to write some code to illustrate this fact.

Solutions

We will store the number of visits to positive integers in the vectors vpos, store the visits to negative integers in vneg, and the visits to zero as vzero. We will start the walk at the origin.

step <-function(i,l,r){
  nextstep = i-1
  p = r/(l+r)
  if (rbinom(1,1,p) == 1){nextstep <- i+1}
  nextstep
}

steps<- function(N){
  vpos =NULL
  vneg =NULL
  vzero =1
  path = 0
  wr = 1
  wl =1
  k=0
  while(k <N){
    current= path[length(path)]
    if (current+1 >0 && length(vpos) >= current+1){
      wr = vpos[current+1]
    }
    if (current+1 ==0){
      wr = vzero
    }
    if (current+1 <0){
      wr = vneg[abs(current+1)]
    }
  
     if (current-1 <0 && length(vneg) >= abs(current-1)){
      wl = vneg[abs(current-1)]
    }
    if (current-1 ==0){
      wl = vzero
    } 
    if (current-1 >0){
      wl = vpos[current-1]
    } 
    
    
nextspot = step(current, wl,wr)
an = abs(nextspot)
  path <- c(path, nextspot)
  if (nextspot==0){vzero<- vzero+1}
  if (nextspot <0 && an <= length(vneg)){vneg[an] <- vneg[an] +1  }
  if (nextspot <0 && an > length(vneg)){vneg <-c(vneg, 2)  }
  if (nextspot >0 && an <= length(vpos)){vpos[an] <- vpos[an] +1  }
  if (nextspot >0 && an > length(vpos)){vpos <-c(vpos, 2)  }
  wl=1
  wr=1
  k <-k+1
  }  
list(path, vneg, vzero, vpos)
}
steps(2000)

## [[1]]
##    [1] 0 1 2 3 2 3 4 3 4 3 2 1 0 1 0 1 2 1 0 1 2 3 2 1 2 1 0 1 0 1 0 1 0 1 0 1 0
##   [38] 1 2 1 0 1 2 1 2 3 2 1 2 1 0 1 0 1 0 1 2 1 2 1 2 1 2 3 2 1 2 3 2 1 0 1 0 1
##   [75] 2 1 0 1 2 3 2 1 2 1 2 1 0 1 2 1 2 1 2 1 0 1 2 1 0 1 0 1 2 1 0 1 2 1 0 1 2
##  [112] 1 0 1 2 1 2 1 0 1 2 1 2 1 2 1 2 1 2 1 0 1 0 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1
##  [149] 2 1 2 3 2 1 0 1 0 1 2 1 2 1 2 1 2 1 0 1 2 1 0 1 2 1 2 1 0 1 2 1 0 1 2 1 0
##  [186] 1 2 3 4 3 2 1 2 1 2 1 0 1 0 1 2 1 0 1 0 1 0 1 0 1 2 3 2 3 2 1 0 1 2 1 2 1
##  [223] 0 1 0 1 2 1 2 1 2 1 2 1 0 1 0 1 0 1 0 1 2 1 0 1 2 1 0 1 0 1 2 1 2 1 0 1 0
##  [260] 1 2 1 2 1 2 1 2 1 2 1 2 1 0 1 2 1 0 1 2 1 0 1 0 1 2 1 0 1 2 1 2 1 2 1 0 1
##  [297] 0 1 0 1 2 1 0 1 2 1 0 1 0 1 2 1 2 1 2 1 0 1 2 1 2 1 2 1 2 1 2 1 0 1 2 1 0
##  [334] 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 0 1 2 1 0 1 2 1 2 1 0 1 0 1 0 1 2 1 2 1
##  [371] 2 1 2 1 2 1 0 1 2 1 2 1 0 1 2 1 2 1 0 1 2 1 0 1 0 1 2 1 2 1 2 1 2 1 0 1 2
##  [408] 1 2 1 0 1 0 1 2 1 2 1 2 1 0 1 0 1 2 1 2 1 0 1 2 1 0 1 0 1 2 1 0 1 0 1 0 1
##  [445] 2 1 2 1 2 1 2 1 2 3 2 3 2 1 0 1 2 1 2 1 2 1 2 1 2 1 0 1 0 1 2 1 0 1 2 1 0
##  [482] 1 2 1 0 1 0 1 2 1 2 1 0 1 0 1 0 1 2 3 2 1 2 1 2 1 2 1 2 1 0 1 0 1 2 1 2 1
##  [519] 2 1 0 1 2 1 2 1 2 1 0 1 0 1 0 1 2 1 2 1 2 1 0 1 0 1 0 1 2 1 0 1 2 1 2 1 0
##  [556] 1 2 1 2 1 0 1 2 1 2 1 2 1 2 1 2 1 0 1 2 1 2 1 2 1 2 1 2 1 2 1 0 1 2 1 2 1
##  [593] 2 1 2 1 0 1 0 1 2 1 2 1 0 1 2 1 0 1 0 1 2 1 2 1 0 1 2 1 0 1 2 1 2 1 2 1 2
##  [630] 1 2 1 0 1 2 1 0 1 0 1 2 3 2 1 2 1 2 1 0 1 0 1 2 1 0 1 2 1 0 1 0 1 2 1 0 1
##  [667] 0 1 2 1 2 1 2 1 2 1 0 1 2 1 0 1 2 1 0 1 0 1 0 1 2 1 2 1 2 3 2 1 2 1 2 1 2
##  [704] 1 2 1 2 1 0 1 2 1 0 1 2 1 2 1 0 1 0 1 2 1 2 1 2 1 2 1 2 1 2 1 0 1 0 1 2 1
##  [741] 2 1 2 1 2 1 2 1 2 1 2 1 2 1 0 1 0 1 0 1 2 1 2 3 2 1 0 1 0 1 2 1 2 1 2 1 0
##  [778] 1 2 1 0 1 2 1 2 1 2 1 2 1 0 1 2 1 0 1 2 1 2 1 2 1 2 3 2 1 0 1 2 1 0 1 2 1
##  [815] 2 1 2 1 0 1 2 1 0 1 2 3 2 1 2 1 2 1 2 1 0 1 2 1 2 1 2 1 0 1 2 1 2 1 2 1 2
##  [852] 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 0 1 2 1 2 1 2 1 0 1 2 1 2 1 2 1 0 1 2 1 2 1
##  [889] 2 1 2 1 2 1 2 1 2 3 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 3 2 1 0 1 2 1 0 1 2 1 0
##  [926] 1 2 1 2 1 2 1 0 1 2 1 0 1 0 1 0 1 2 1 2 1 0 1 2 1 0 1 2 1 2 1 2 1 0 1 0 1
##  [963] 2 1 2 1 0 1 2 1 2 1 2 1 0 1 0 1 0 1 2 1 2 1 2 1 0 1 0 1 0 1 2 1 0 1 2 1 2
## [1000] 1 2 1 2 1 0 1 2 1 2 1 2 1 0 1 2 1 2 1 2 1 0 1 0 1 0 1 2 1 2 1 2 1 2 1 2 1
## [1037] 2 1 0 1 2 1 0 1 0 1 0 1 2 1 2 3 2 1 2 1 0 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 0
## [1074] 1 2 1 0 1 2 1 0 1 2 1 0 1 2 1 0 1 0 1 0 1 0 1 2 1 2 1 2 1 2 1 2 1 0 1 2 1
## [1111] 0 1 0 1 2 1 2 1 2 3 2 1 2 1 0 1 2 1 0 1 0 1 2 1 0 1 2 1 2 1 0 1 2 1 2 1 2
## [1148] 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 0 1 2 1 2 1 0 1 2 1 2 1 2 1 2 1 0 1 2 1
## [1185] 2 1 2 1 2 1 0 1 0 1 0 1 2 1 2 1 2 1 0 1 0 1 2 3 2 1 2 1 2 1 2 1 2 1 2 3 2
## [1222] 1 0 1 0 1 2 1 0 1 2 1 2 1 0 1 2 1 2 1 2 1 2 1 0 1 2 1 0 1 2 1 2 1 2 1 0 1
## [1259] 0 1 0 1 0 1 2 1 2 1 0 1 0 1 2 1 2 1 2 3 2 1 0 1 2 1 2 1 2 1 0 1 0 1 2 1 2
## [1296] 1 2 1 0 1 2 1 0 1 0 1 2 1 2 1 0 1 0 1 0 1 2 1 0 1 0 1 2 1 2 1 0 1 2 1 2 1
## [1333] 2 1 2 1 2 1 0 1 2 1 2 1 2 1 2 1 2 1 2 1 0 1 2 1 2 1 0 1 2 1 2 1 2 1 0 1 2
## [1370] 1 2 1 0 1 2 1 0 1 2 1 0 1 2 1 0 1 2 1 2 3 2 1 0 1 2 1 2 1 2 1 2 1 2 1 0 1
## [1407] 2 1 2 1 0 1 2 1 2 1 0 1 2 1 0 1 2 1 0 1 0 1 2 1 0 1 2 1 2 1 2 1 2 1 2 1 2
## [1444] 1 0 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 0 1 2 1 2 1 0 1 0 1 2 1 2 1
## [1481] 2 1 0 1 0 1 2 1 2 1 0 1 0 1 0 1 2 3 2 1 0 1 2 1 2 1 2 1 2 1 2 1 0 1 2 1 2
## [1518] 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 0 1 0 1 2 1 0 1 0 1 0 1 2 1 2 1 2 1 2 1 2 1
## [1555] 2 1 2 1 0 1 2 1 0 1 2 1 2 1 2 1 0 1 2 1 2 1 2 1 0 1 2 1 2 1 2 1 2 1 0 1 2
## [1592] 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 0 1 2 1 0 1 0 1 2 1 2 1 2 3 2 1 2 1 2 1 2 1
## [1629] 2 1 0 1 0 1 2 1 2 1 2 1 2 1 0 1 2 1 2 1 2 1 2 1 0 1 2 1 2 1 0 1 0 1 2 1 0
## [1666] 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 0 1 0 1 2 1 0 1 2 1 2 1 0 1 2 1 0 1 2 1 2 1
## [1703] 0 1 2 1 2 1 2 1 0 1 2 1 0 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 0 1 2 1 2
## [1740] 1 2 1 2 1 2 1 2 1 0 1 2 1 2 1 2 1 0 1 2 1 0 1 0 1 0 1 0 1 2 1 2 1 2 1 2 1
## [1777] 0 1 0 1 2 1 0 1 0 1 0 1 0 1 2 1 2 1 0 1 2 1 2 1 2 1 0 1 0 1 2 1 2 1 0 1 2
## [1814] 1 0 1 2 1 2 1 2 3 2 1 2 1 2 1 2 1 2 1 0 1 0 1 2 1 2 1 2 1 2 1 2 1 2 1 0 1
## [1851] 0 1 2 1 2 1 2 1 0 1 2 1 0 1 2 1 2 1 0 1 2 1 0 1 2 1 2 1 2 1 2 1 0 1 0 1 2
## [1888] 3 2 1 2 1 0 1 2 1 2 1 2 1 0 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 0 1 2 1 0 1 2 1
## [1925] 2 1 2 1 2 1 0 1 2 1 2 1 2 1 0 1 2 1 0 1 0 1 2 1 2 1 2 1 2 1 2 3 2 1 2 1 0
## [1962] 1 2 1 0 1 2 1 2 1 0 1 2 1 0 1 0 1 2 1 0 1 2 1 2 1 2 1 2 1 2 1 0 1 2 1 2 3
## [1999] 2 1 0
## 
## [[2]]
## NULL
## 
## [[3]]
## [1] 333
## 
## [[4]]
## [1] 965 666  37   4

Endnotes

• Version: 31 October 2022
• Rmd Source