So maybe I'm approaching this completely in the wrong way, but i can't seem to grasp how to do this easily and I hope y'all can help. The problem itself, I think, is quite complex. Therefore I will split it in 3 parts. Part 1 I think to have solved and I would just like to check if my thought process is correct. Part 2 is an intermediate step which would possibly help in solving part 3 and would be an acceptable result if part 3 cannot be solved. However, part 3 is the true problem. So you immediately want to take a swing at that without reading over the rest, please be my guest.

Problem description

PART 1

I have a number of states (this can be a large number), as an example let's say 3: A, B and C. These can be modeled as a Markov Chain as shown below.

Aside from having the expected transition probabilities, there is another aspect, namely every state has a value as noted in square brackets. As such, we can derive the transition matrix P and the value matrix V.

$$ P =left[
begin{array}{ccc}
0&0.3&0.7\
0.1&0&0.9\
0.3&0.7&0
end{array}
right],
V = left[ begin{array}{c}
5&
1&
2
end{array}right]
$$

The first step of the problem is to get the expected values of each of these states. My approach would be to first calculate the stationary distribution of the model and subsequently multiplying those probabilities with the corresponding values. So something like this:

In order to find the stationary distribution we need to find the
eigenvalues of the transpose of the transition matrix: $$ detleft(
begin{array}{ccc} -lambda&0.3&0.7\
0.1&-lambda&0.9\
0.3&0.7&-lambda end{array} right) = 0 $$

With an eigenvalue of $ lambda = 1 $ resulting in the only all
positive eigenvector $(0.38, 0.81, 1)$, the stationary distribution
is: $$ S = frac{1}{0.38 + 0.81 + 1} cdot left(begin{array}{ccc}0.38&0.81& 1end{array}right) = left(begin{array}{ccc}0.17& 0.37& 0.46end{array}right)$$

As such, the expected values are:
$$ V circ S = left(begin{array}{ccc}0.85& 0.37& 0.91end{array}right)$$

So the first question is probably: "Is this a right approach?"

PART 2

Now that we have the basic foundation, the problem is expanded. The next problem can be easily put in words:

What is the chance of reaching state Y before reaching state Z, given a starting state X?

Is there a way that this can be calculated for any three states? Note: this does not have to be a general solution for all X, Y and Z, since X and Z will be fixed states. So instead, it should be given states X and Z, what are the chances we will still reach Y before we reach Z. Another note: any state other than Z may be revisited.

PART 3

The ultimate goal I'm trying to achieve is this:

• We are at a starting state A


• We will at some point end at Z

We are looking for a state S with the highest value, that we will reach with only a minimal number of expected steps remaining before we reach Z. So:

$ A rightarrow $ [n steps] $ rightarrow S rightarrow $ [m steps] $ rightarrow Z $

Where we try to find a minimal m with a maximal value for S

As such, my thought is that at the least, there will have to be some function that can adds a value based on the number of steps taken. Or at least a weighting function between the value of S and the number of steps between S and Z.

Part 1.

It is a right approach.

Part 2.

The trick is to make states Y and Z absorbing, i.e. redirect all the arrows that go from Y or Z to themselves. So your example (if X,Y,Z=A,B,C) will turn into this.

After that you use the standard technique to determine what is the probability to end in an absorbing state Y (or Z) if you start with the state X. Write a comment if you have a problem with understanding the formulas in the link.

Part 3.

I didn't quiet get what you want. But I believe that an essential part of it is the same. If for you coming to Z is the end of the game, you can make this state absorbing and then calculate whatever you want: expected number of steps, probabilities etc.