在 R 中给定转移矩阵绘制马尔可夫链
Draw markov chain given transition matrix in R
设trans_m
为一阶马尔可夫链的n
乘n
转移矩阵。在我的问题中,n
很大,比如 10,000,而矩阵 trans_m
是由 Matrix
包构造的稀疏矩阵。否则,trans_m
的大小会很大。我的目标是在给定初始状态向量 s1
和此转换矩阵 trans_m
的情况下模拟一系列马尔可夫链。考虑以下具体示例。
n <- 5000 # there are 5,000 states in this case.
trans_m <- Matrix(0, nr = n, nc = n, sparse = TRUE)
K <- 5 # the maximal number of states that could be reached.
for(i in 1:n){
states_reachable <- sample(1:n, size = K) # randomly pick K states that can be reached with equal probability.
trans_m[i, states_reachable] <- 1/K
}
s1 <- sample(1:n, size = 1000, replace = TRUE) # generate 1000 inital states
draw_next <- function(s) {
.s <- sample(1:n, size = 1, prob = trans_m[s, ]) # given the current state s, draw the next state .s
.s
}
sapply(s1, draw_next)
给定初始状态向量 s1
如上所述,我使用 sapply(s1, draw_next)
绘制下一个状态。 n
越大,sapply
变慢。有没有更好的办法?
按行重复索引可能会很慢,因此处理转换矩阵的转置和使用列索引并从内部函数中提取索引会更快:
R> trans_m_t <- t(trans_m)
R>
R> require(microbenchmark)
R> microbenchmark(
+ apply(trans_m_t[,s1], 2,sample, x=n, size=1, replace=F)
+ ,
+ sapply(s1, draw_next)
+ )
Unit: milliseconds
expr min
apply(trans_m_t[, s1], 2, sample, x = n, size = 1, replace = F) 111.828814
sapply(s1, draw_next) 499.255402
lq mean median uq max neval
193.1139810 190.4379185 194.6563380 196.4273105 270.418189 100
503.7398805 512.0849013 506.9467125 516.6082480 586.762573 100
由于您已经在使用稀疏矩阵,您或许能够
通过直接在三胞胎上工作可以获得更好的性能。使用更高级别的矩阵运算符可以触发重新压缩。
设trans_m
为一阶马尔可夫链的n
乘n
转移矩阵。在我的问题中,n
很大,比如 10,000,而矩阵 trans_m
是由 Matrix
包构造的稀疏矩阵。否则,trans_m
的大小会很大。我的目标是在给定初始状态向量 s1
和此转换矩阵 trans_m
的情况下模拟一系列马尔可夫链。考虑以下具体示例。
n <- 5000 # there are 5,000 states in this case.
trans_m <- Matrix(0, nr = n, nc = n, sparse = TRUE)
K <- 5 # the maximal number of states that could be reached.
for(i in 1:n){
states_reachable <- sample(1:n, size = K) # randomly pick K states that can be reached with equal probability.
trans_m[i, states_reachable] <- 1/K
}
s1 <- sample(1:n, size = 1000, replace = TRUE) # generate 1000 inital states
draw_next <- function(s) {
.s <- sample(1:n, size = 1, prob = trans_m[s, ]) # given the current state s, draw the next state .s
.s
}
sapply(s1, draw_next)
给定初始状态向量 s1
如上所述,我使用 sapply(s1, draw_next)
绘制下一个状态。 n
越大,sapply
变慢。有没有更好的办法?
按行重复索引可能会很慢,因此处理转换矩阵的转置和使用列索引并从内部函数中提取索引会更快:
R> trans_m_t <- t(trans_m)
R>
R> require(microbenchmark)
R> microbenchmark(
+ apply(trans_m_t[,s1], 2,sample, x=n, size=1, replace=F)
+ ,
+ sapply(s1, draw_next)
+ )
Unit: milliseconds
expr min
apply(trans_m_t[, s1], 2, sample, x = n, size = 1, replace = F) 111.828814
sapply(s1, draw_next) 499.255402
lq mean median uq max neval
193.1139810 190.4379185 194.6563380 196.4273105 270.418189 100
503.7398805 512.0849013 506.9467125 516.6082480 586.762573 100
由于您已经在使用稀疏矩阵,您或许能够 通过直接在三胞胎上工作可以获得更好的性能。使用更高级别的矩阵运算符可以触发重新压缩。