Page 17 & 18
## Random Walk in a Straight line
a.) Write a program to simulate a random walk in a straight line. Print out the lengths between returns to the same point (your origin) of zero.
Will the walker always eventually return to this starting point or not?
set.seed(321)
options(scipen = 999)
moves <- sample(c(1,-1), size=10000, replace = TRUE, prob = c(.5,.5))
location <- cumsum(moves)
locations <- location == 0
indexes<- as.vector(which(location==0))
zeros <- location==0
indexes <-append(rev(indexes), c(1))
distances <- abs(diff(indexes))
one<- table(distances)
one <- data.frame(one)
colnames(one)<= c("Distance From Prior Zero", "Frequency")## [1] FALSE TRUEprob_one <- data.frame(one)
colnames(prob_one)<- c('Moves_to_ Zero', 'Frequency')
prob_one$Simulated_Probability<-prob_one$Frequency/(length(moves)-1)
probability_zero <-round(sum(zeros)/length(moves),20)I simulated this walk by randomly choosing from 1 and -1 and built a list for 10,000 walk choices, then used cum-sum to see how far from zero each move left the walker (this assumes a uniform step size). From this I extracted the index of 0 values and calculated the distance between the indexes of locations with zero.
I am only showing the rows until the probability is ‘Practically Zero’
| Moves_to_ Zero | Frequency | Simulated_Probability |
|---|---|---|
| 2 | 19 | 0.0019002 |
| 3 | 1 | 0.0001000 |
| 4 | 6 | 0.0006001 |
| 6 | 1 | 0.0001000 |
| 8 | 3 | 0.0003000 |
| 14 | 1 | 0.0001000 |
| 18 | 1 | 0.0001000 |
| 22 | 3 | 0.0003000 |
| 30 | 1 | 0.0001000 |
| 80 | 1 | 0.0001000 |
| 96 | 2 | 0.0002000 |
| 122 | 1 | 0.0001000 |
| 160 | 1 | 0.0001000 |
| 332 | 1 | 0.0001000 |
| 5360 | 1 | 0.0001000 |
Probability of Zero in 10,000 Walks: 0.0043
It is probable that given enough random walks one might revisit their starting point based on random selection of a walking direction and a fixed unit walk.
How likely would a random walker be to return to their starting point if they were walking in a plane making orthogonal decisions north, south, east, west?
For this simulation I had to drop the number of random walks to 10,000 to get it to run in a reasonable time.
set.seed(321)
moves_2<- sample(c("n","s", "e", "w"), size=10000, replace = TRUE)
two_d_space <- data.frame( x = 0, y = 0, z = 0)
x = 0
y = 0
z = 0
for (i in moves_2){
if (i=="n"){
z = z + 1
}
else if (i == "s"){
z = + z - 1
}
else if (i == "e") {
x = x + 1
}
else if ( i == "w"){
x = x - 1
}
ro = c(x, y, z)
two_d_space <- rbind(two_d_space, ro)
}
two_d_space$check <- two_d_space$x + two_d_space$y + two_d_space$z
two_d_space$origin = two_d_space$check==0
returns_to_origin <- sum(two_d_space$origin)
indexes_2<- as.vector(which(two_d_space$check==0))
distances_2 <- abs(diff(indexes_2))
two<- table(distances_2)
prob_two <- data.frame(two)
colnames(prob_two)<- c('Moves_to_ Zero', 'Frequency')
prob_two$Simulated_Probability<-prob_two$Frequency/(length(moves_2)-1)
probability_zero_2 <-sum(two_d_space$origin)/nrow(two_d_space)I am only showing the rows until the probability is ‘Practically Zero’
| Moves_to_ Zero | Frequency | Simulated_Probability |
|---|---|---|
| 2 | 36 | 0.0036004 |
| 4 | 10 | 0.0010001 |
| 6 | 4 | 0.0004000 |
| 8 | 2 | 0.0002000 |
| 10 | 1 | 0.0001000 |
| 14 | 6 | 0.0006001 |
| 18 | 2 | 0.0002000 |
| 24 | 1 | 0.0001000 |
| 34 | 1 | 0.0001000 |
| 38 | 3 | 0.0003000 |
| 60 | 1 | 0.0001000 |
| 62 | 1 | 0.0001000 |
| 106 | 1 | 0.0001000 |
| 268 | 1 | 0.0001000 |
| 1048 | 1 | 0.0001000 |
| 1714 | 1 | 0.0001000 |
| 5644 | 1 | 0.0001000 |
Probability of Zero in 10,000: 0.0073993
In this case you would also likely return to your starting point, but the likelihood drops as your number of moves gets farther from your last zero position. Effectively you have about a .7% chance of randomly ending up where you started.
In this case we are trying to estimate the likihood of returning to your original starting position if you had three directions (6 choices). Again I started with 10,000 random walks
set.seed(321)
moves_3<- sample(c("n","s", "e", "w", "u", "d"), size=10000, replace = TRUE)
three_d_space <- data.frame( x = 0, y = 0, z = 0)
x = 0
y = 0
z = 0
for (i in moves_3){
if (i=="n"){
z = z + 1
}
else if (i == "s"){
z = + z - 1
}
else if (i == "e") {
x = x + 1
}
else if ( i == "w"){
x = x - 1
}
else if ( i == "u"){
y = y + 1
}
else if( i == "d") {
y = y - 1
}
ro = c(x, y, z)
three_d_space <- rbind(three_d_space, ro)
}
three_d_space$check <- three_d_space$x + three_d_space$y + three_d_space$z
three_d_space$origin = three_d_space$check==0
returns_to_origin <- sum(three_d_space$origin)
indexes_3<- as.vector(which(three_d_space$check==0))
distances_3 <- abs(diff(indexes_3))
three<- table(distances_3)
prob_three <- data.frame(three)
colnames(prob_three)<- c('Moves_to_ Zero', 'Frequency')
prob_three$Simulated_Probability<-prob_three$Frequency/(length(moves_3)-1)
probability_zero_3 <-sum(three_d_space$origin)/nrow(three_d_space)| Moves_to_ Zero | Frequency | Simulated_Probability |
|---|---|---|
| 2 | 6 | 0.0006001 |
| 4 | 3 | 0.0003000 |
| 10 | 1 | 0.0001000 |
| 48 | 1 | 0.0001000 |
Probability of Zero in 10,000 Walks: 0.0011999
In this case, there is a small, less than \(1/10th\) of a percent chance of finding the origin again. Notice that if you do not find it in the first 5-12 moves, the odds of ever returning again become slim. This supports the idea that you would likely not return to your starting point in 3-d space