How can I compute expected return time of a state in a Markov Chain?

  • Thread starter user366312
  • Start date

user366312

Gold Member
66
2
Problem Statement


I was watching a YouTube video regarding the calculation of expected return time of a Markov Chain.
I haven't understood the calculation of ##m_{12}##.

How could he write ##m_{12}=1+p_{11}m_{12}##? I have given a screenshot of the video.



241819
 
Last edited by a moderator:

Orodruin

Staff Emeritus
Science Advisor
Homework Helper
Insights Author
Gold Member
2018 Award
15,624
5,645
In all cases, you need to take a time step - that is the 1. With probability ##p_{11}##, you will not leave node 1. So you need to add that probability multiplied by the mean time to get to 2 from 1, which is ##m_{12}##.
 

user366312

Gold Member
66
2
In all cases, you need to take a time step - that is the 1. With probability ##p_{11}##, you will not leave node 1. So you need to add that probability multiplied by the mean time to get to 2 from 1, which is ##m_{12}##.
Why didn't he add 1 in case of ##m_{11}##?

Why is ##m_{12}## on the both side of the equation
 

Orodruin

Staff Emeritus
Science Advisor
Homework Helper
Insights Author
Gold Member
2018 Award
15,624
5,645

user366312

Gold Member
66
2
I don't see it. Coz, he calculated ##m_{11} = \frac{1}{\frac{2}{3}}##

Because if you stay at 1, then the expected time to get to 2 will be the expected time to get to 2 from 1.
So, then he should write: ##m_{12} = 1 + p_{11}m_{21}## . But he didn't write that.
 

Ray Vickson

Science Advisor
Homework Helper
Dearly Missed
10,705
1,719
I don't see it. Coz, he calculated ##m_{11} = \frac{1}{\frac{2}{3}}##



So, then he should write: ##m_{12} = 1 + p_{11}m_{21}## . But he didn't write that.
Well, it is good he did not write that, because it is wrong.

Just look at the equations
$$m_{ij} = 1 + \sum_{k \neq j} p_{ik} m_{kj}.$$
You have all the ##p_{ij}## given right in the problem, so just going ahead and writing out the equations for the ##m_{ij}## is elementary. You seem to be over-thinking the problem, or in some other way, confusing yourself.

You should realize that there may be more than one way to compute some of the ##m_{ij}##. Using ##m_{11} = 1 + p_{12} m_{21}## is one way (after you have calculated ##m_{21}##), but using ##m_{11} = 1/\pi_1## is another. A useful calculation check is to see whether you get the same value both ways---if you did everything right, you should.
 
Last edited:

user366312

Gold Member
66
2
Thank you @Ray Vickson! That concludes the answer very well.
 
The meaning of the

$$ m_{i,j} = 1+ \sum_{k\neq j} p_{i,k} m_{k,j} $$
formula.

The expected number of steps to get someone from i to j:

One step is definitely a must.

However, besides, if you did not reach j in the first step, but you get into a different k, then look at how many steps you can expect from k to j and you take this expected value with the weight what probability you first step into k.
 

Want to reply to this thread?

"How can I compute expected return time of a state in a Markov Chain?" You must log in or register to reply here.

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving
Top