Probability of visiting state k at least once during first n steps in finite state Markov Chain

Question

Assuming a Markov Chain of $M$ states, and assuming starting from state $X_0$, I was wondering if there is a method to calculate the probability of visiting state $X_k$ at least once during first n steps. Any help would be greatly appreciated!

I don't think there is a closed form expression for this, but I hope I am wrong. So far I was trying to estimate it using simulations.

Answer 1

These probabilities can be estimated using the following algorithm:

1. Initialise counter = 0

2. For N iterations (with N large):

   • simulate the Markov chain over n steps
   • if state k was visited, increment counter by 1

3. Estimate desired probability by counter / N (i.e., the proportion of the simulated realisations for which state k was visited)

I'm including R code to do this below, for a 5-state Markov chain with a transition probability matrix that I chose. In the code, I'm keeping track of the "counters" for all states.

# Number of states
M <- 5

# Transition probability matrix
tpm <- matrix(c(0.5, 0.1, 0.1,   0,   0,
                0  ,   0, 0.5, 0.2, 0.3,
                0  , 0.1, 0.9,   0,   0,
                0.1, 0.2,   0, 0.3, 0.5,
                0  ,   0,   0, 0.2, 0.8),
              nrow = M, byrow = TRUE)

# Length of realisation
n <- 10
# Initial state
X0 <- 2

# Iterate over many simulations
n_rep <- 1e4
counts <- rep(0, M)
for(rep in 1:n_rep) {
    # Simulate Markov chain
    X <- rep(X0, n)
    for(i in 2:n) {
        X[i] <- sample(1:M, size = 1, prob = tpm[X[i-1],])
    }
    # Check which states have been visited
    visited_states <- unique(X)
    counts[visited_states] <- counts[visited_states] + 1
}

# Proportion of simulations where each state was visited
prop <- counts / n_rep

In this example, we find:

> prop
[1] 0.0880 1.0000 0.6064 0.5470 0.5817

For example, there is approximately a probability 0.088 of visiting state 1 if we start from state 2 (variable X0) and run the chain for 10 steps (variable n). As expected, the probability of visiting state 2 is 1, because that's where we start.