Suppose I have a 1 Dimensional Random Walk (on the integer line) with the following properties (initial conditions):
- At time=0 it starts at position=0
- At each time point, there is a 0.5 probability of moving +1 or -1
This Random Walk keeps going until one of the following things happens:
The Random Walk reaches position=10 (successful termination condition)
100,000 Steps are taken and position=10 is still not reached (unsuccessful termination condition)
I wrote the following R simulation to represent random simulations of this Random Walk with these conditions:
library(ggplot2)
num_simulations <- 1000
max_steps <- 100000
target <- 10
steps <- numeric(num_simulations)
trajectories <- list()
terminated <- 0
for (i in 1:num_simulations) {
position <- 0
print(i)
trajectory <- c(0)
for (step in 1:max_steps) {
position <- position + sample(c(-1, 1), 1)
trajectory <- c(trajectory, position)
if (position == target) {
steps[i] <- step
break
}
if (step == max_steps) {
terminated <- terminated + 1
}
}
trajectories[[i]] <- trajectory
}
termination_percentage <- (terminated / num_simulations) * 100
df1 <- data.frame(simulation_index = 1:num_simulations, log_steps = log(steps))
df2 <- data.frame(simulation_index = rep(1:num_simulations, sapply(trajectories, length)),
step = unlist(lapply(trajectories, seq_along)) - 1,
position = unlist(trajectories))
p1 <- ggplot(df1, aes(x = simulation_index, y = log_steps)) +
geom_point() +
geom_line() +
labs(x = "Simulation Index", y = "Log(Number of Steps)",
title = paste("Random Walk Simulations (Terminated:", termination_percentage, "%)")) +
theme_bw()
p2 <- ggplot(df2, aes(x = step, y = position, group = simulation_index)) +
geom_line(alpha = 0.1) +
labs(x = "Step", y = "Position",
title = paste("Trajectories of Random Walk Simulations (Terminated:", termination_percentage, "%)")) +
theme_bw()
As we can see, roughly 2% of all simulations (with these initial conditions) met the unsuccessful termination condition.
My Question: Given a set of initial conditions and a set of termination conditions, is it possible to derive an expression for the expected number (i.e. expected value) of simulations expected to meet the unsuccessful termination condition?
Thanks!