Search code examples
r2dcodeblocksrandom-walk

How to break a random walk at destination with R

I have to generate a random walk for a sequence of positions in 2D. The person doing the random walk starts at (0,0). At every move, she goes left, right, up or down. The random walk stops if she comes back to (0,0), or until she made a 1000 steps. *I am using the R language

I have done this so far, but I am having trouble figuring out how to stop the random walk when she reaches (0,0) again. I only get two vectors back. Any help would be very appreciated. Thank you!

step.max<-1000
destination<-rbind(c(0,0))

Random.walk <- function(n=step.max){
  steps <- matrix(c(0,0,-1,1,0,-1,1,0),nrow = 4)
  walk <- steps[sample(1:5,n,replace = TRUE)] 
  walk.1 <-rbind(walk)
  ifelse(destination,break,apply(walk.1,2,cumsum))
  }
Random.walk(n)
Solution

  • If you want to stop when you reach the origin, you will have to use a loop. Alternatively you can generate a random walk of 1000 steps very quickly and identify when the origin was reached:

    steps <- matrix(c(1, 0, -1, 0, 0, 1, 0, -1), nrow = 4, byrow=TRUE)
steps
#      [,1] [,2]
# [1,]    1    0  # Right
# [2,]   -1    0  # Left
# [3,]    0    1  # Up
# [4,]    0   -1  # Down

    Now generate a random walk with 1000 steps:

    set.seed(42)  # To create a reproducible example
rand <- sample.int(4, 1000, replace=TRUE)
moves <- steps[rand, ]         # 1000 random moves
position <- rbind(c(0, 0), apply(moves, 2, cumsum))  # Position after each move
home <- which(position[, 1] == 0 & position[, 2] == 0)  # When is position c(0, 0)?
home
# [1] 1   # We never revisit the origin in this random walk.

    Now illustrate the results:

    plot(position, type="l")
points(0, 0, cex=2, col="red")
points(position[1001, 1], position[1001, 2], cex=2, col="blue")

    Random Walk

    If you want break out of the walk when the position returns to c(0, 0), you will need a loop. Something like this:

    steps <- matrix(c(1, 0, -1, 0, 0, 1, 0, -1), nrow = 4, byrow=TRUE)
position <- rbind(c(0, 0))
move <- 0
for (move in 2:1001) {  
    step <- steps[sample.int(4, 1), ]
    position <- rbind(position,  position[move-1, ] + step)
    if (position[move, 1] == 0 & position[move, 2] == 0) break
}
cat("move=", move, "position=", position[move, ], "\n")

    The position variable will contain all of the locations visited during the walk.

    If you want to know how often the walk returns to the origin before 1000 steps, we need to create a function for the walk and then use replicate to generate multiple walks, for example 10,000:

    steps <- matrix(c(1, 0, -1, 0, 0, 1, 0, -1), nrow = 4, byrow=TRUE)
walking <- function(n) {
    rand <- sample.int(4, n, replace=TRUE)
    moves <- steps[rand, ]
    position <- rbind(c(0, 0), apply(moves, 2, cumsum))
    home <- which(position[, 1] == 0 & position[, 2] == 0)
    if (is.na(home[2])) 1000 else home[2]
}

results <- replicate(10000, walking(1000))
sum(results < 1000)/10000
# [1] 0.683

    So about 68% of the time the walk ends in less than 1000 steps. You can increase the replications. If you run this several times, the percentage varies from 67 - 68%. You can narrow the range by increasing the number of replications, but the code will take longer to run.