# Markov chain chance one state is reached before another

Hey could someone explain why this is true? I am trying to understand how to solve such a problem but I don't understand the solution.

Problem:
Given a Markov chain $\left\{X_{n}: n\in\ \mathbb{N}\right\}$ with four states 1,2,3,4 and transition matrix
$P = \begin{pmatrix} 0 & \frac{1}{2}& \frac{1}{2} & 0 \\ 0 & 0 & \frac{1}{2} & \frac{1}{2}\\ \frac{1}{2} & 0 & 0 & \frac{1}{2} \\ \frac{1}{2} & \frac{1}{2} & 0 & 0 \end{pmatrix}$
We leave from state 3. What is the chance that state 1 will be reached before state 4?

Solution:
Lets call this chance x. Lets call y the same chance but instead leaving from 2. Lets call:
$f = \begin{pmatrix} 1 \\ x \\ y \\ 0 \end{pmatrix}$
Then f satisfies P'f = f with P' the transition matrix derived from P by making state 1 and 4 absorbing states i.e.,

$\begin{pmatrix} 1 & 0& 0 & 0 \\ 0 & 0 & \frac{1}{2} & \frac{1}{2}\\ \frac{1}{2} & 0 & 0 & \frac{1}{2} \\ 0 & 0 & 0 & 1\end{pmatrix}*\begin{pmatrix} 1 \\ x \\ y \\ 0 \end{pmatrix}= \begin{pmatrix} 1 \\ x \\ y \\ 0 \end{pmatrix}$
Solving gives y = 1/2, x = 1/4.

Last edited:

Related Calculus and Beyond Homework Help News on Phys.org
Ray Vickson
Homework Helper
Dearly Missed
Hey could someone explain why this is true? I am trying to understand how to solve such a problem but I don't understand the solution.

Problem:
Given a Markov chain $\left\{X_{n}: n\in\ \mathbb{N}\right\}$ with four states 1,2,3,4 and transition matrix
$P = \begin{pmatrix} 0 & \frac{1}{2}& \frac{1}{2} & 0 \\ 0 & 0 & \frac{1}{2} & \frac{1}{2}\\ \frac{1}{2} & 0 & 0 & \frac{1}{2} \\ \frac{1}{2} & \frac{1}{2} & 0 & 0 \end{pmatrix}$
We leave from state 3. What is the chance that state 1 will be reached before state 4?

Solution:
Lets call this chance x. Lets call y the same chance but instead leaving from 2. Lets call:
$f = \begin{pmatrix} 1 \\ x \\ y \\ 0 \end{pmatrix}$
Then f satisfies P'f = f with P' the transition matrix derived from P by making state 1 and 4 absorbing states i.e.,

$\begin{pmatrix} 1 & 0& 0 & 0 \\ 0 & 0 & \frac{1}{2} & \frac{1}{2}\\ \frac{1}{2} & 0 & 0 & \frac{1}{2} \\ 0 & 0 & 1 & 1\end{pmatrix}*\begin{pmatrix} 1 \\ x \\ y \\ 0 \end{pmatrix}= \begin{pmatrix} 1 \\ x \\ y \\ 0 \end{pmatrix}$
Solving gives y = 1/2, x = 1/4.
You need to be more specific: what part do you not understand?

What you presented above is pretty standard, and is almost always part of the course material regarding Markov chains.

Also: for context: are you using a textbook and/or course notes? Do these sources not have such material in them?

If you could direct me to a place where this is explained I would be grateful. The material my teacher provided doesn't address this problem or atleast not directly, so I find it hard to understand this solution from the theory provided. I dont understand why P'f=f must be true. And I dont understand why those states are made absorbing.

Edit: I dont understand why its necessary to multiply with such a vector either.

Last edited:
Ray Vickson
Homework Helper
Dearly Missed
If you could direct me to a place where this is explained I would be grateful. The material my teacher provided doesn't address this problem or atleast not directly, so I find it hard to understand this solution from the theory provided. I dont understand why P'f=f must be true. And I dont understand why those states are made absorbing.

Edit: I dont understand why its necessary to multiply with such a vector either.
When you don't understand something, it is a good idea to work it out from first principles. Let's do that.

Define ##f_i(n)## to be the probability that, starting from state i we reach state 1 for the first time at time n and do not reach state 4 before time n; let ##f_i = \sum_{n=1}^{\infty} f_i(n)##; this is the probability we reach state 1 before reaching state 4, starting from state i.

Note that
$$f_i(n) = P\{X_1 \neq 1,4, \: X_2 \neq 1,4,\: \ldots, X_{n-1} \neq 1,4, \: X_n = 4 |X_0=i\}$$
Conditioning on ##X_1## we have
$$f_i(n) = \sum_{j \neq 1,4} p_{ij} P\{X_2 \neq 1,4, \: \ldots, X_{n-1} \neq 1,4,\: X_n = 1 |X_1 = j, X_0 = i \} \\ = \sum_{j \neq 1,4} p_{ij} f_j(n-1).$$
Also: ##f_i(1) = p_{i1}##. Summing over n we get
$$f_i = f_i(1) + \sum_{n=2}^{\infty} f_i(n)\\ = p_{ij} + \sum_{j \neq 1,4} p_{ij} \sum_{n=2}^{\infty} f_j(n-1) = p_{i1} + \sum_{j \neq 1,4} p_{ij} f_j .$$

In other words:
$$f_2 = p_{21} + p_{22} f_2 + p_{23} f_3 \\ f_3 = p_{31} + p_{32} f_2 + p_{33} f_3.$$
Note that this is a simple 2x2 linear system that we can solve easily.

Of course, since (in this example, but not all examples) we either reach state 1 before state 4 or reach state 4 before state 1, the probability that, starting from state i we reach 4 before 1 is just ## 1 - f_i##.

Note that if we set ##f_1 = 1## and ##f_4 = 0## we can write the equations above as
$$f_1 = 1 f_1 + 0 f_2 + 0 f_3 + 0 f_4 \\ f_2 = p_{21} f_1 + p_{22}f_2 + p_{23} f_3 + p_{24}f_4\\ f_3 = p_{31} f_1 + p_{32}f_2 + p_{33}f_3 + p_{34} f_4 \\ f_4 = 0 f_1 + 0 f_2 + 0 f_3 + 1 f_4$$
This is just the set of equations ##f = \tilde{P} f## for a modified Markov chain with transition matrix
$$\tilde{P} = \pmatrix{1 &0&0&0\\p_{21}&p_{22} & p_{23} & p_{24}\\ p_{31} & p_{32} & p_{33} & p_{34} \\ 0 & 0 & 0 & 1}$$
and with
$$f = \pmatrix{1 \\f_2 \\f_3 \\0}$$

As I said: work it out in detail from first principles.

• 1 person
Thank you very much for taking your time and explaining this neatly and thoroughly. I'm sure this will be helpful to many others too as I haven't found an explanation of this particular problem trough Google.

Ray Vickson
Homework Helper
Dearly Missed
Thank you very much for taking your time and explaining this neatly and thoroughly. I'm sure this will be helpful to many others too as I haven't found an explanation of this particular problem trough Google.
There was a typo in my post, which I corrected in an "edit" and which was seemingly accepted, but was later not implemented. I should have written ##X_n = 1## instead of ##X_n = 4## n the definition of ##f_i(n)##.

There was a typo in my post, which I corrected in an "edit" and which was seemingly accepted, but was later not implemented. I should have written ##X_n = 1## instead of ##X_n = 4## n the definition of ##f_i(n)##.
Yes I realized that. What about the solution? Doesn't it also contain a mistake? If x is the chance leaving from state 3 shouldnt it come in the third place of the vector instead of the second?

There was a typo in my post, which I corrected in an "edit" and which was seemingly accepted, but was later not implemented. I should have written ##X_n = 1## instead of ##X_n = 4## n the definition of ##f_i(n)##.
I'm sorry but as I know sometimes replies are overlooked I'm sending another reply with the hope you will respond.

Ray Vickson