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

Click For Summary

Discussion Overview

The discussion revolves around the calculation of the expected return time of a state in a Markov Chain, specifically focusing on the equation for ##m_{12}## and its derivation. Participants explore the implications of the formula and the reasoning behind certain terms in the equations, including the role of transition probabilities.

Discussion Character

  • Technical explanation
  • Debate/contested
  • Mathematical reasoning

Main Points Raised

  • One participant questions the equation ##m_{12} = 1 + p_{11} m_{12}## and seeks clarification on its derivation.
  • Another participant explains that the time step of 1 must be included, along with the probability ##p_{11}## multiplied by the mean time to reach state 2 from state 1, which is ##m_{12}##.
  • There is confusion about why 1 was not added in the case of ##m_{11}##, with participants discussing the implications of staying at state 1.
  • Some participants assert that the equation for ##m_{12}## is correct as stated, while others suggest alternative formulations, such as ##m_{12} = 1 + p_{11} m_{21}##.
  • A later reply emphasizes that there may be multiple valid methods to compute the expected return times, suggesting a check for consistency between different approaches.
  • One participant expresses gratitude for the clarification provided by another participant, indicating that the explanation helped conclude the discussion.
  • The meaning of the formula $$m_{i,j} = 1 + \sum_{k \neq j} p_{i,k} m_{k,j}$$ is discussed, highlighting the necessity of the first step and the expected values from other states.

Areas of Agreement / Disagreement

Participants express differing views on the formulation of the equations and the reasoning behind them. There is no consensus on the best approach to derive ##m_{12}##, and multiple competing interpretations of the equations remain present.

Contextual Notes

Participants have not resolved the assumptions underlying the equations or the specific conditions under which different formulations may apply. The discussion reflects a variety of interpretations and approaches to the problem.

user366312
Gold Member
Messages
88
Reaction score
3
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:
Physics news on Phys.org
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}##.
 
Orodruin said:
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
 
user366312 said:
Why didn't he add 1 in case of m11m11m_{11}?
He did.

user366312 said:
Why is m12m12m_{12} on the both side of the equation
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.
 
Orodruin said:
He did.

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

Orodruin said:
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.
 
user366312 said:
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:
  • Like
Likes   Reactions: jim mcnamara
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.
 

Similar threads

  • · Replies 7 ·
Replies
7
Views
2K
  • · Replies 3 ·
Replies
3
Views
2K
  • · Replies 12 ·
Replies
12
Views
2K
  • · Replies 8 ·
Replies
8
Views
2K
Replies
9
Views
2K
  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 1 ·
Replies
1
Views
3K
  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 13 ·
Replies
13
Views
4K
  • · Replies 1 ·
Replies
1
Views
1K