Suppose we have a DTMC $X$ : $\{X_n : n = 0, 1,2,\dots\}$, a transition probability matrix $P$, and state space $S = \{1,2,3\}$. Suppose I want to calculate the expected amount of times we visit state $3$ in $T$ periods given that we start our chain at $X_0=1$. Let's also assume we have some function $C$ that maps values of $X$ to some "cost". We will define $C$ as such: $C(1) = 0, C(2) = 0, C(3) = 1$. Then to calculate expected amount of times we reach state $3$, using this cost funtion we have: $$E[\sum\limits_{i=1}^{T}C(X_i)|X_0=1]$$ in which case we would get an answer of something like: $$[P+P^2+\dots+P^T] \begin{bmatrix} C(1) \\ C(2) \\ C(3) \end{bmatrix}$$ If this is not the case, what flaws are in my logic and what would a proper setup look like?

  • $\begingroup$ I don't follow your equations: the first (expectation) doesn't even reference state $3$ while the second one multiplies a $3\times 3$ matrix by a $T$-vector, which is not possible unless $T=3$ or $T=1.$ $\endgroup$ – whuber Mar 2 at 22:22
  • $\begingroup$ good point, I can fix the second one at least $\endgroup$ – hkj447 Mar 2 at 22:23
  • $\begingroup$ I made some structural changes to the problem @whuber, let me know if this helps at all. $\endgroup$ – hkj447 Mar 2 at 22:39

For a target state $s$ and any state $a,$ let $v_a(s,T)$ be the expected number of visits to state $s$ (not counting the current state) upon making $T\ge 0$ transitions from state $a.$ From basic properties of expectation and the Markov property, we know

  1. $v_a(s,0)=0$ for all $a.$

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

This is conveniently expressed in matrix notation by letting $\mathbf{v}(s,T)$ be the 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$ has its unique $1$ at position $s.$

By inspection, the solution (easily verified) is

$$\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.$$

In the question with $s=3$ and $a=1$ you would take the first entry in this vector, $v_1(3,T).$

To illustrate, here is brute-force R code to compute $\mathbf{v}(s,n):$

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

(For long sequences of transitions you would want to diagonalize $\mathbb{P}$ and sum the resulting geometric series appearing the diagonal--but that's standard Markov Chain machinery which we needn't discuss here.)

Here is R code to simulate 10,000 transitions starting at state 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,])

Run these calculations with your favorite transition matrix to compare the results. If you don't have a favorite, here is code to generate interesting ones (they have a bunch of zeros in them):

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

For instance, after setting the seed with set.seed(17), the output was

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

showing good agreement between the observed frequency and computed value.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.