Cálculo del número esperado de visitas a un estado por parte de un DTMC

Question

Supongamos que tenemos un DTMC $X$ : $\{X_n : n = 0, 1,2,\dots\}$ una matriz de probabilidad de transición $P$ y el espacio de estado $S = \{1,2,3\}$ . Supongamos que quiero calcular la cantidad esperada de veces que visitamos el estado $3$ en $T$ periodos dado que empezamos nuestra cadena en $X_0=1$ . Supongamos también que tenemos alguna función $C$ que mapea los valores de $X$ a algún "coste". Definiremos $C$ como tal: $C(1) = 0, C(2) = 0, C(3) = 1$ . A continuación, para calcular la cantidad esperada de veces que alcanzamos el estado $3$ utilizando esta función de coste tenemos: $$E[\sum\limits_{i=1}^{T}C(X_i)|X_0=1]$$ en cuyo caso obtendríamos una respuesta de algo así como $$[P+P^2+\dots+P^T] \begin{bmatrix} C(1) \\ C(2) \\ C(3) \end{bmatrix}$$ Si no es así, ¿qué fallos hay en mi lógica y cómo sería una configuración adecuada?

Answer 1

Para un estado de destino $s$ y cualquier estado $a,$ dejar $v_a(s,T)$ sea el número esperado de visitas al estado $s$ (sin contar el estado actual) al hacer $T\ge 0$ transiciones de estado $a.$ A partir de las propiedades básicas de la expectativa y la propiedad de Markov, sabemos

1. $v_a(s,0)=0$ para todos $a.$

2. $v_a(s,T) = \sum_{r\in S} P_{ar} v_r(s,T-1)+ \mathcal{I}(r=s) .$

Esto se expresa convenientemente en notación matricial dejando que $\mathbf{v}(s,T)$ sea el vector $(v_a(s,0))_{a\in S}:$

1. $\mathbf{v}(s,0) = \mathbf{0}.$

2. $\mathbf{v}(s,T) = \mathbb{P} \mathbf{v}(s,T-1) + \mathbf{e}_s.$

$\mathbf{e}_s = (0,\ldots, 0,1,0,\ldots,0)^\prime$ tiene su propio $1$ en la posición $s.$

Por inspección, la solución (fácilmente verificada) es

$$\mathbf{v}(s,T) = \mathbb{P}\left(\mathbb{P}\left(\cdots \mathbf{e}_s\right) + \cdots\right) + \mathbf{e}_s = \left(\mathbb{P}^T + \mathbb{P}^{T-1} + \cdots + \mathbb{P} + \mathbb{I}_3\right)\mathbf{e}_s.$$

En la pregunta con $s=3$ et $a=1$ se tomaría el primero en este vector, $v_1(3,T).$

---

Para ilustrar, aquí está la fuerza bruta R código para calcular $\mathbf{v}(s,n):$

v <- e <- rep(0,dim(P)[1])
e[s] <- 1
for (i in seq_len(n)) v <- P %*% v + e

(Para secuencias largas de transiciones se querrá diagonalizar $\mathbb{P}$ y sumar la serie geométrica resultante apareciendo la diagonal--pero eso es una maquinaria estándar de las cadenas de Markov que no necesitamos discutir aquí).

Aquí está R para simular 10.000 transiciones a partir del estado a :

sim <- replicate(1e4, {
  x <- a
  count <- 0
  for (i in seq_len(n)) {
    if (x == s) count <- count + 1
    x <- sample.int(dim(P)[1], 1, prob=P[x,])
  }
  count
})
mean(sim)

Realiza estos cálculos con tu matriz de transición favorita para comparar los resultados. Si no tienes una favorita, aquí tienes un código para generar las interesantes (tienen un montón de ceros):

d <- 5 # Number of states
P <- cbind(rexp(d), matrix(ifelse(runif(d*(d-1)) <= 2/d, 0, rexp(d^2)), d))
P <- P / rowSums(P)
a <- 1 # Start state
s <- d # Target
n <- 8 # Transitions

Por ejemplo, después de fijar la semilla con set.seed(17) el resultado fue

> c(mean(sim), v[a])
[1] 2.132200 2.137539

mostrando una buena concordancia entre la frecuencia observada y el valor calculado.