Expected Number of Transitions for a Markov Chain to Reach a Certain State I am trying to find out the number of times a die needs to be rolled before observing a 4 followed by a 6. I would like to model this problem using a discrete time Markov chain with 3 states:

*

*State 1: Start

*State 2: Rolling a 4

*State 3: Rolling a 6 Immediately after Rolling a 4 (Absorbing State)

I recognize that :

*

*State 1 has a 5/6 probability of going to State 1, and State 1 has a 1/6 probability of going to State 2

*State 2 has a 4/6 probability of going to State 1, State 2 has a 4/6 probability of going to State 2 and State 2 has a 1/6 probability of going to State 3

*State 3 has a probability of 1 of going to State 3

Using the R programming language. I wrote a small simulation to demonstrate which state the Markov chain is likely to be in after each step:
    library(expm)
library(ggplot2)
library(reshape2)

 mat1.data <- c(5/6, 1/6, 0, 4/6, 1/6, 1/6, 0,0,1)
 mat <- matrix(mat1.data,nrow=3,ncol=3,byrow=TRUE)

V1<- c(1,0,0)

 results <- list()
for (i in 1:100)

{

iteration = i

my_vec_i =  V1%*% (mat %^% i)

vec_1_i = my_vec_i[1]
vec_2_i = my_vec_i[2]
vec_3_i = my_vec_i[3]

results_tmp = data.frame(iteration,vec_1_i, vec_2_i, vec_3_i)

results[[i]] <- results_tmp

}

results_df <- do.call(rbind.data.frame, results)

colnames(results_df )[2] <- 'State_1'
colnames(results_df )[3] <- 'State_2'
colnames(results_df )[4] <- 'State_3'

mdf <- reshape2::melt(results_df, id.var = "iteration")
ggplot(mdf, aes(x = iteration, y = value, colour = variable)) + 
    geom_point() + 
    geom_line()

I plotted the graph below:

My Question: Its clear to see that as the number of iterations ("steps") go on, we are more and more likely to a roll a 4 followed by a 6 – but is there some way we can determine the "average number of times we need to roll a die before observing a 4 followed by a 6"?
I tried to set up a Markov chain to try and find "number of rolls" needed before observing a 4 followed by a 6, but I can't seem to figure this out. Can someone please show me how to mathematically determine the average number of rolls needed before observing a 4 followed by a 6?

You can also do an exact calculation. Let $K(x,y)$ be the transition probability for going from point $x$ to point $y$ in some Markov chain. For points $a,b$, let $\tau_{a,b}$ be the expected time to go from $a$ to $b$, with $\tau_{a,a}=0$ by convention. We then have the following recurrence relationships for $a \neq b$:
$\tau_{a,b} = 1 + \sum_{c} K(a,c) \tau_{c,b}$ by looking at what happens after one step.
If your Markov chain has $n$ states, this gives you a collection of $\frac{n(n-1)}{2}$ equations in the same number of unknowns. You can solve using the usual linear algebra approach.
