Markov chain chance one state is reached before another

[kasperrepsak]

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. Let's call y the same chance but instead leaving from 2. Let's 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.

 

[Ray Vickson]

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. Let's call y the same chance but instead leaving from 2. Let's 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?

 

[kasperrepsak]

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 don't understand why P'f=f must be true. And I don't understand why those states are made absorbing.

Edit: I don't understand why its necessary to multiply with such a vector either.

 

[Ray Vickson]

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 don't understand why P'f=f must be true. And I don't understand why those states are made absorbing.

Edit: I don't 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.

 

[kasperrepsak]

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]

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)$.

 

[kasperrepsak]

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 shouldn't it come in the third place of the vector instead of the second?

 

[kasperrepsak]

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]

I'm sorry but as I know sometimes replies are overlooked I'm sending another reply with the hope you will respond.

If you are asking me to check whether a given pair of numbers is the solution of a given pair of two simple linear equations in two unknowns, then I refuse to answer. You can check it yourself---and you always should, as a matter of habit, in such cases. Just plug in the numbers to see if they work. If they don't work, somebody has made an error---typographical or otherwise---and you need to re-solve those equations.

 

[kasperrepsak]

If you are asking me to check whether a given pair of numbers is the solution of a given pair of two simple linear equations in two unknowns, then I refuse to answer. You can check it yourself---and you always should, as a matter of habit, in such cases. Just plug in the numbers to see if they work. If they don't work, somebody has made an error---typographical or otherwise---and you need to re-solve those equations.

Well the pair is a solution to that matrix vector multiplication. But I'm pretty sure the teacher made a mistake in putting the chance x on the second place of the vector, since the way u explained it it should be on the third place. This is because x is the chance leaving from state 3. I just wanted to make sure I understood that correctly.