100步随机游走过点10概率

randomwalkover.md

100步随机游走过程中, 经过点10的概率精确值为:

求和式中的项为所谓的「首达概率」.

代码

randWalkOver1 <- function(n, start, stop, p = 0.5, stepf = 1, stepb = 1) {
    out <- 0
    x <- start
    for (i in 1:n) {
        x <- x + sample(c(stepf, -stepb), 1, prob = c(p, 1 - p))
        if (x >= stop) { out <- 1; break }
    }
    out
}

# by 大珞珞
randWalkOver2 <- function(n, stop) {
    sim <- sample(c(1, -1), size = n, prob = c(0.5, 0.5), replace = TRUE)
    ifelse(any(cumsum(sim) >= stop), 1, 0)
}

randWalkOverAccurate <- function(n, stop) {
    sum(sapply(seq(stop, n, 2), function(n) {
        stop / (n * 2 ^ n) * choose(n, (n + stop) / 2)
    }))
}

sapply(seq(8), function(i) {
    mean(sapply(seq(1e4), function(i) { randWalkOver2(100, 10) }))
})

randWalkOverAccurate(100, 10)

cat("===========================================================\n")

sapply(seq(8), function(i) {
    mean(sapply(seq(1e4), function(i) { randWalkOver2(1000, 20) }))
})

randWalkOverAccurate(1000, 20)

输出

[1] 0.3219 0.3222 0.3204 0.3153 0.3135 0.3169 0.3238 0.3225
[1] 0.3197273
===========================================================
[1] 0.5332 0.5224 0.5252 0.5222 0.5308 0.5229 0.5268 0.5231
[1] 0.5273164

参考

• First passage time of a 1D simple random walk in a discrete time infinite markov chain [closed]
• An Elementary Proof of the Hitting Time Theorem
• Lecture 2: Random Walks 1, Reflection and Reversal