1

Consider the attached Markov Chain. I need to calculate the E[number of visits to State 2 | the system starts from 2 and gets absorbed to State 1]. More generally, I am interested in calculating the expected time to absorption given that the system is finally absorbed to a specific recurrent state. I can simulate the system, but does anyone have ideas on how I can calculate that analytically? Thanks!

enter image description here

Salivan
  • 397

3 Answers3

2

Here, I am generalizing NCH's answer to this question. Consider a Markov Chain with the state space $\Omega$. I use $A$ to denote the set of absorbing states and $A^c$ to denote the set of transient states ($A\cup A^c = \Omega $). I am interested in calculating $E(V_{ij}|B_{ib})$, where the random variable $V_{ij}$ is the number of visits to State $j \in A^c$, given that the system starts from State $i \in A$, and $B_{ib}$ denotes the event for absorption at State $b \in A$ given that the system starts from State $i \in A$. We know:

$$ \Pr(V_{ij}=k|B_{ib}) = \frac{\Pr(V_{ij}=k,B_{ib}) }{\Pr(B_{ib})}. $$ The probability $\Pr(B_{ib})$ can be calculated as shown in this Wikipedia article (Subsection Absorbing Probabilities).

Let's use $T_{ij}$ to denote the event of visiting State $j$, starting from State $i$, before any absorption (not just absorption at $b$). Then $V_{ij}=k \cap B_{ib}$ includes: one time moving from $i$ to $j$, $k-1$ time moving from $j$ to $j$, and moving from $j$ to $b$ in the end without visiting $j$. That is: $$ \Pr(V_{ij}=k,B_{ib}) = \Pr(T_{ij}) \Pr(T_{jj})^{k-1} [\Pr(B_{jb})(1-\Pr(T_{jj}))] . $$ To calculate $\Pr(T_{ij})$, I will use the result in Transient Probabilities subsection of this Wikipedia article. So: $$ \begin{align} E(V_{ij}|B_{ib}) &= \sum_{k=0}^\infty k \Pr(V_{ij}=k|B_{ib}) \\ &= \sum_{k=0}^\infty k \frac{\Pr(T_{ij}) \Pr(T_{jj})^{k-1} [\Pr(B_{jb})(1-\Pr(T_{jj}))]}{\Pr(B_{ib})} \\ &= \frac{\Pr(T_{ij}) [\Pr(B_{jb})(1-\Pr(T_{jj}))]}{\Pr(B_{ib})} \sum_{k=0}^\infty k \Pr(T_{jj})^{k-1} \\ &= \frac{\Pr(T_{ij}) [\Pr(B_{jb})(1-\Pr(T_{jj}))]}{\Pr(B_{ib}) (1-\Pr(T_{jj}))^2} \\ & = \frac{\Pr(T_{ij}) \Pr(B_{jb})}{\Pr(B_{ib}) (1-\Pr(T_{jj}))}, \forall i \ne j \in A, b\in A^c. \end{align} $$

If $i = j$: $$ E(V_{ii}|B_{ib}) = \frac{1}{1-\Pr(T_{ii})}, \forall i \in A, b\in A^c. $$

amWhy
  • 209,954
Salivan
  • 397
1

Let us find the conditional distribution for the number $N$ of visits to state $2$ given absorption at state $1$ occurs for chain starting with state $2$. Denote by $A$ the following event $$ A=\{\exists n: X_n=1\}=\{\text{absorption at state $1$ occurs}\} $$ where $X_n, n\ge 0$ is the MC. We need to find $$ P_2(N=k | A) = \dfrac{P_2(N=k, A)}{P_2(A)} $$ where index $2$ indicates that chain is starting from state $2$. To calculate absorption probability $P_2(A)$ write and solve relations. Let $P_4(A)$ be an absorption probability at $1$ for chain starting at $4$. To absorb at state $1$ starting at $2$ one can either move to $1$ w.p. $0.25$ and stay here, or move to $4$ w.p. $0.75$ and then absorb at $1$ w.p. $P_4(A)$. To absorb at state $1$ starting at $4$ one should move to $2$ w.p. $0.4$ and then absorb at $1$ w.p. $P_2(A)$. Therefore $$P_2(A)=0.75P_4(A)+0.25,\quad P_4(A)=0.4P_2(A).$$ Solving this relations get $$P_2(A)=\dfrac{0.25}{1-0.75\cdot0.4}.$$

Next find $P_2(N=k,\ A)$. The chain is initially at $2$. To have exactly $k$ visits at $2$ and than absorb at $1$ one need to have $k-1$ times when chain goes to $4$ and returns back, and then moves to $1$: $$ P_2(N=k, A) = 0.25\cdot(0.75\cdot0.4)^{k-1}. $$

Finally, $$ P_2(N=k | A) = \dfrac{P_2(N=k, A)}{P_2(A)} = (0.75\cdot0.4)^{k-1}(1-0.75\cdot0.4). $$ This is geometric distribution with mean $\dfrac{1}{1-0.75\cdot0.4}.$

NCh
  • 13,807
  • 4
  • 17
  • 33
0

Given that the system is absorbed in state 1 and that it starts in state 2, you can throw out state 3 as it can never be visited. This means the transition from 4 to 2 occurs with probability 1 in this conditioned environment. Let $C_k(x)$ be the probability of hitting $X_k=x$, given that the system absorbs at 1 after some finite time . Then:

$$C_{k}(1)=0.25\cdot C_{k-1}(2)$$ $$C_{k}(2)=C_{k-1}(4).$$ $$C_{k}(4)=0.75\cdot C_{k-1}(2).$$

You can easily solve this by looking at the last two equations, and noticing the parity requires $C_k(2)$ to be zero when $k$ is odd, to get $C_{k}(2)=0.75^{k-1}$ when $k$ is even and 0 otherwise. This gives $C_k(1)=0.25\cdot 0.75^{k-2}$ when $k$ is odd and 0 otherwise. Now just sum for odd indices to get your expectation:

$$\sum_{k=0}^\infty (2k-1)C_{2k-1}.$$

Can you finish it from here?

Alex R.
  • 32,771
  • Note that it is not enough to just prune a state, conditioning prunes paths, so that it may be less likely to visit stages that tend to send you toward the state you can no longer visit. Not sure this issue is a problem here in particular though. – Ian Mar 08 '17 at 04:09
  • Thanks, Alex, for taking the time and your comment. But Ian is right. Increasing the transition probability from State 4 to State 1 to 1 will increase the frequency of visits to State 1 and therefore the number of visits will be inflated. I confirmed that with my simulation model. – Salivan Mar 08 '17 at 16:14
  • @AlexR. Yes, 3 cannot be visited, that's correct. My point is that the conditioning does more than simply remove 3 from the state space and renormalize the transition probabilities. In particular, in this system the chain will want to spend proportionally less time in state 4 than this "naive" modification would spend, because many of the paths that visit state 4 eventually go to state 3. However I didn't check your answer in enough detail to be 100% certain as to whether you took this into account. – Ian Mar 08 '17 at 18:26
  • @AlexR. If you still don't follow (I can tell that my wording here is a bit unclear), think about this: the conditional $p_{42}$ is of course $1$, but also, as the unconditional $p_{43} \to 1^-$, the conditional $p_{24}$ must go to zero. – Ian Mar 08 '17 at 18:32