# Weighted and Probability Graph

I have a simple markov chain with A, B and C states. For each state I have a probability and beyond that, a value. So, for each state transition I have two informations: the probability of the transisiton to another state and a value.

I need to know the average value considering that I am trying to start from node A and finish in the node C. I was thinking about to use Markov Chains but I have a value with the probability and I dont know whet kind of theory I can apply to find the average value on this path A -> C.

• I think this is better suited for mathstackexchange – Dhruv Mahajan Dec 28 '20 at 20:57

One way of solving your problem is to simulate your Markov chain and then use LLN to recover the expected value over all of the simulations. In essence, you simulate your Markov chain until it hits node C, and you do this $$n$$ times. You can then recover the total value for each simulation by summing all of the values, and then average across all simulations. I've provided some R code which might help your understanding:

P_mat <- matrix(c(0.05, 0.9,0.05,0.5,0.5,0,0,0,0), ncol = 3, nrow = 3, byrow = T)
V_mat <- matrix(c(5,2,10,3,3,0,0,0,0), ncol = 3, nrow =3, byrow = T)
init_dist <- c(1,0,0)

chainSim <- function(alpha, mat, val_mat) {
out <- numeric()
val <- numeric()

out[1] <- sample(1:3, 1, prob = alpha)
i <- 1
temp <- 0

while (temp < 3){

i <- 1+i

out[i] <- sample(1:3, 1, prob = mat[out[i - 1], ])

val[i-1] <- val_mat[out[i-1], out[i]]

ifelse(out[i]==3, temp <- 3, temp <- 0)

}
output <- list(out = out, val = val)
return(output)
}

sim <- replicate(chainSim(init_dist, mat = P_mat, val_mat = V_mat)\$val, n = 20000)

#sum all vals for each sim
sumsim <- lapply(sim, function(x) sum(x))

#mean across all sim
meanall <- mean(unlist(sumsim))
meanall


Here, "P_mat" denotes the probability transition matrix, V_mat is the value matrix for transitioning between each state, and init_dist is the initial distribution. Be-aware, that in my code "A","B","C" have been replaced with 1,2,3 respectively. The while-loop simulate the Markov chain until you hit node 3 (C), and the transitions between each state is provided in the vector "out". The values for transitioning between each state is provided in the vector "val".

I did consecutive simulations for $$n=20000$$ and landed on an average value (ie. "meanall") on approximately 158.

I have to acknowledge that Markov chains are not my area of expertise, so I cannot give you a theoretical solution to your question. However, I hope that the simulation might justify as a (temporary) solution.