############################################################
## STAT545: Random-walk returns to 0 on Z^d
##
## Notation:
## - (X_n) random walk on Z^d starting at X_0 = 0
## - T0 = inf{ n > 0 : X_n = 0 } : first return time to the origin
## - f0 = P(T0 < inf | X0 = 0)   : probability of eventual return
## - f0(T) = P(T0 < T | X0 = 0)  : probability of return before time T
##
############################################################

## Question: are random walks recurrent or transient?

# try simulating a few random walks in 1d, 2d, 3d and make a guess
source("https://ruizt.quarto.pub/stat545/scripts/rw_single_sim.R")
rw_single_sim(T = 10000, d = 3)


# simulate nsim random walks until return to zero or reach Tmax
# in dimensions d = 1, 2, 3 (takes a little while, ~60-90sec)
source('https://ruizt.quarto.pub/stat545/scripts/rw_sim_return.R')
Tmax <- 20000
nsim <- 20000
print_every <- 1000
batch <- 500
sim1 <- rw_sim_return(d = 1, Tmax = Tmax, nsim = nsim, seed = 1,
                           print_every = print_every, batch = batch)
sim2 <- rw_sim_return(d = 2, Tmax = Tmax, nsim = nsim, seed = 2,
                           print_every = print_every, batch = NULL)
sim3 <- rw_sim_return(d = 3, Tmax = Tmax, nsim = nsim, seed = 3,
                           print_every = print_every, batch = NULL)

# inspect output structure
str(sim1)

# what share of realizations return by Tmax in each dimension?
mean(is.na(sim1$t0))
mean(is.na(sim2$t0))
mean(is.na(sim3$t0))

# estimate f0(T) using ecdf(...); when T is large this approximates f0
fhat1 <- ifelse(is.na(sim1$t0), Inf, sim1$t0) |> ecdf()
fhat2 <- ifelse(is.na(sim2$t0), Inf, sim2$t0) |> ecdf()
fhat3 <- ifelse(is.na(sim3$t0), Inf, sim3$t0) |> ecdf()

# plot f0(T) against T
plot(x = log(1:Tmax), 
     y = fhat1(1:Tmax), 
     type = 'l', 
     xlab = 'T', 
     ylab = expression(f[0](T)))

# your turn: add d = 2, 3
lines(x = log(1:Tmax), 
      y = fhat2(1:Tmax),
      type = 'l')
lines(x = log(1:Tmax), 
      y = fhat3(1:Tmax), 
      type = 'l')

## Discuss: do these suggest recurrence or transience?