3.3.1 How to find \(f_{ij}^{\left ( n\right ) }\)

This is the probability it will take \(n\) steps to first reach state \(j\) from state \(i\). In Below \(C\left ( J\right ) \) means the closed set which contains the state \(j\) and \(T\) means the transient set

\(i\in C(J)\), \(j\in C(J)\)	use formula (1) below
\(i\in C(J)\), \(j\notin C(J)\)	\(f_{ij}^{\left ( n\right ) }=0\)
\(i\in T\), \(j\) Absorbing state	Calculate \(A^{m}=Q^{m}R\)  where \(m=n-1\) then the \(i,j\) entry of \(A^{m}\) gives \(f_{ij}^{\left ( n\right ) }\)
\(i\in T\), \(j\in T\)	Normally we are interested in finding expected number of visits to \(j\) before absorbing. i.e \(E\left ( V_{ij}\right ) \). see below. Otherwise use (1)

We can use \(p_{ij}^{\left ( n\right ) }\) . Notice the subtle difference between \(f_{ij}^{\left ( n\right ) }\) and \(p_{ij}^{\left ( n\right ) }\).

\(f_{ij}^{\left ( n\right ) }\) gives the probability of needing \(n\) steps to first reach \(j\) from \(i\), while \(p_{ij}^{\left ( n\right ) }\) gives the probability of being in state \(j\) after \(n\) steps leaving \(i\). So with \(p_{ij}^{\left ( n\right ) }\) could have reached state \(j\) before \(n\) steps, but left state \(j\) and moved around, then came back, as long as after \(n\) steps exactly MC will be in state \(j\). With \(f_{ij}^{\left ( n\right ) }\,\,\)this is not allowed. The chain must reach state \(j\) the very first time in \(n\) steps from leaving \(i\). So in a sense, \(f_{ij}^{\left ( n\right ) }\) is a more strict probability.  Using the recursive formula

\begin{equation} p_{ij}^{\left ( n\right ) }=f_{ij}^{\left ( n\right ) }+f_{ij}^{\left ( n-1\right ) }p_{jj}^{\left ( 1\right ) }+f_{ij}^{\left ( n-2\right ) }p_{jj}^{\left ( 2\right ) }+\cdots +f_{ij}^{\left ( 1\right ) }p_{jj}^{\left ( n-1\right ) } \tag {1}\end{equation}

We can calculate \(f_{ij}^{\left ( n\right ) }\). We see that \(f_{ij}^{\left ( 1\right ) }=p_{ij}^{\left ( 1\right ) }\) and so \(f_{ij}^{\left ( 2\right ) }=p_{ij}^{\left ( 2\right ) }-f_{ij}^{\left ( 1\right ) }p_{jj}^{\left ( 1\right ) }\) and also

\begin{align*} f_{ij}^{\left ( 3\right ) } & =p_{ij}^{\left ( 3\right ) }-f_{ij}^{\left ( 2\right ) }p_{jj}^{\left ( 1\right ) }-f_{ij}^{\left ( 1\right ) }p_{jj}^{\left ( 2\right ) }\\ & =p_{ij}^{\left ( 3\right ) }-\left ( p_{ij}^{\left ( 2\right ) }-f_{ij}^{\left ( 1\right ) }p_{jj}^{\left ( 1\right ) }\right ) p_{jj}^{\left ( 1\right ) }-f_{ij}^{\left ( 1\right ) }p_{jj}^{\left ( 2\right ) }\\ & =p_{ij}^{\left ( 3\right ) }-\left ( p_{ij}^{\left ( 2\right ) }p_{jj}^{\left ( 1\right ) }-p_{ij}^{\left ( 1\right ) }\left [ p_{jj}^{\left ( 1\right ) }\right ] ^{2}\right ) -p_{ij}^{\left ( 1\right ) }p_{jj}^{\left ( 2\right ) }\\ & =p_{ij}^{\left ( 3\right ) }-p_{ij}^{\left ( 2\right ) }p_{jj}^{\left ( 1\right ) }+p_{ij}^{\left ( 1\right ) }\left [ p_{jj}^{\left ( 1\right ) }\right ] ^{2}-p_{ij}^{\left ( 1\right ) }p_{jj}^{\left ( 2\right ) }\end{align*}

and

\begin{align*} f_{ij}^{\left ( 4\right ) } & =p_{ij}^{\left ( 4\right ) }-f_{ij}^{\left ( 3\right ) }p_{jj}^{\left ( 1\right ) }-f_{ij}^{\left ( 2\right ) }p_{jj}^{\left ( 2\right ) }-f_{ij}^{\left ( 1\right ) }p_{jj}^{\left ( 3\right ) }\\ & =p_{ij}^{\left ( 4\right ) }-\left ( p_{ij}^{\left ( 3\right ) }-p_{ij}^{\left ( 2\right ) }p_{jj}^{\left ( 1\right ) }+p_{ij}^{\left ( 1\right ) }\left [ p_{jj}^{\left ( 1\right ) }\right ] ^{2}-p_{ij}^{\left ( 1\right ) }p_{jj}^{\left ( 2\right ) }\right ) p_{jj}^{\left ( 1\right ) }-\left ( p_{ij}^{\left ( 2\right ) }-f_{ij}^{\left ( 1\right ) }p_{jj}^{\left ( 1\right ) }\right ) p_{jj}^{\left ( 2\right ) }-f_{ij}^{\left ( 1\right ) }p_{jj}^{\left ( 3\right ) }\\ & =p_{ij}^{\left ( 4\right ) }-\left ( p_{ij}^{\left ( 3\right ) }p_{jj}^{\left ( 1\right ) }-p_{ij}^{\left ( 2\right ) }\left [ p_{jj}^{\left ( 1\right ) }\right ] ^{2}+p_{ij}^{\left ( 1\right ) }\left [ p_{jj}^{\left ( 1\right ) }\right ] ^{3}-p_{ij}^{\left ( 1\right ) }p_{jj}^{\left ( 1\right ) }p_{jj}^{\left ( 2\right ) }\right ) -\left ( p_{ij}^{\left ( 2\right ) }p_{jj}^{\left ( 2\right ) }-p_{ij}^{\left ( 1\right ) }p_{jj}^{\left ( 1\right ) }p_{jj}^{\left ( 2\right ) }\right ) -p_{ij}^{\left ( 1\right ) }p_{jj}^{\left ( 3\right ) }\\ & =p_{ij}^{\left ( 4\right ) }-p_{ij}^{\left ( 3\right ) }p_{jj}^{\left ( 1\right ) }+p_{ij}^{\left ( 2\right ) }\left [ p_{jj}^{\left ( 1\right ) }\right ] ^{2}-p_{ij}^{\left ( 1\right ) }\left [ p_{jj}^{\left ( 1\right ) }\right ] ^{3}+p_{ij}^{\left ( 1\right ) }p_{jj}^{\left ( 1\right ) }p_{jj}^{\left ( 2\right ) }-p_{ij}^{\left ( 2\right ) }p_{jj}^{\left ( 2\right ) }+p_{ij}^{\left ( 1\right ) }p_{jj}^{\left ( 1\right ) }p_{jj}^{\left ( 2\right ) }-p_{ij}^{\left ( 1\right ) }p_{jj}^{\left ( 3\right ) }\\ & =p_{ij}^{\left ( 4\right ) }-p_{ij}^{\left ( 3\right ) }p_{jj}^{\left ( 1\right ) }-p_{ij}^{\left ( 2\right ) }p_{jj}^{\left ( 2\right ) }+p_{ij}^{\left ( 2\right ) }\left [ p_{jj}^{\left ( 1\right ) }\right ] ^{2}-p_{ij}^{\left ( 1\right ) }\left [ p_{jj}^{\left ( 1\right ) }\right ] ^{3}+2p_{ij}^{\left ( 1\right ) }p_{jj}^{\left ( 1\right ) }p_{jj}^{\left ( 2\right ) }-p_{ij}^{\left ( 1\right ) }p_{jj}^{\left ( 3\right ) }\end{align*}

etc...

Hence knowing just the \(P\) matrix, we can always obtain values of the \(f_{ij}\) for any powers

However, using the following formula, from lecture notes 6.2 is easier

\[ A^{\left ( n\right ) }=Q^{n}R \]

the \(i,j\) entry of \(A^{\left ( n\right ) }\) gives the probability of taking \(n+1\) steps to first reaching \(j\) when starting from transient state \(i\) \(.\) So use this formula. Just note this formula works only when \(i\) is transient.

question: If \(i\) is NOT transient, and we asked to find what is the prob. it will take \(n\) steps to first reach state \(j\) from state \(i\). Then use (1). right?