# Markov Chain Alternate Expectation

Consider a Markov chain defined by transition matrix $P$ such that for each transition from state $i\rightarrow j$ the probability is $p_{ij}$. Now say there is an associated value for each transition $r_{ij}$ stored in matrix $R$. For example if we transition from state $1 \rightarrow 2$ we may have $r_{12}=2$.

If we are in state $S_t$ at step $t$ and $R^*_t$ is the associated transition value at step $t-1 \rightarrow t$, what is the value of

$$E \left [\sum_{t=1}^{\infty} R^*_t \mid S_0=i, S_{\infty}=j \right ]$$

where $S_{\infty}$ is an absorbing state.

Note this is very similar to calculating expected runs in a Baseball Markov model except here we are conditioning on an absorbing state (http://www.pankin.com/markov/theory.htm 'Calculation of expected runs').

My ideas: Let $R(n) = \sum_{t=1}^nR^*_t$. If we consider $P(R(k) = r\mid S_0=i, S_{k}=j)$, then for a $k=2$ example we have $$\frac{1}{P(S_2 = j | S_0 = i)}\sum_{R^{*}_{1}=0}^r\sum_{l=1}^N P(S_1=l|S_0=i)I(R_{il}=R^*_1)P(S_2=j|S_1=l)I(R_{lj}=r-R^{*}_{1})$$

Where $I(R_{lj}=r-R^*_1)$ is the indicator that the value $lj$ value in $R$ is equal to $R^*_1$.

The idea here is that we consider all length 2 chains of states starting at $i$ and ending at $j$, where the sum of their associated $R$ values is $r$.

If we can calculate these for all $k$ values, we have our answer. The problem with this is for large $k$ the computation will become very large.

Update

Consider our transition matrix as $$P=\left ( \begin{array}{cc} Q & S& \\ 0 & I& \end{array}\right)$$ where $Q,S$ are matrices and $0,I$ are the zero and identity matrices. Then $P(S_k=j| S_{k-1} \mbox{ not absorbing state },S_0 =i)$ for absorbing state $j$ can be approximated for large $k$ by normalising $Q$ into a stochastic matrix and finding the stationary distribution. This gives us a limit on the terms in our expectation and if we use the brute fore method above only for small $k$, we may be able to get a good approximation.

• $R$ is not a stochastic matrix it just holds some information. It is related to the transitions in that if we transition from $i \rightarrow j$ at step $T-1$ to $t$, the value of $R^*_t = R_{ij}$ – rwolst Dec 24 '13 at 13:38
• I encounter the same problem in essence, and I have considered the discrete Ito Integral. But due to the lack of knowledge of real analysis, I am not able to use that. Have you ever considered the discrete Ito Integral? – robit Dec 25 '15 at 4:41