Definition
Conditioning on first step via law of total prob.,
$$ \forall i\ne j,\quad f_{ij}=P_i(T_j<\infty)=P_i(X_1=j)+\sum_{k\ne j}P_i(X_1=k)P_k(T_j<\infty) $$$$ = p_{ij}+\sum_{k\ne j}p_{ik}f_{kj} $$Key Identity / Key Result
Core: Constructing linear function system using all possible states and solve for $f_{ij}$, do not further expand $P_k(T_j<\infty)$, leave it as $f_{kj}$.
Proof:
by L.T.P.
$$ P(A)=\sum_i P(A\mid B_i)P(B_i) $$For
$$ A=\{T_j<\infty\} $$$$ B_k=\{X_1=k\}\quad \text{for }k\in S $$[UNCLEAR: line under $B_k$] First step’s state reaches state $k$.
Expanding $P(A)$ in context gives that:
$$ P_i(T_j<\infty)=\sum_{k\in S}P_i(T_j<\infty\mid X_1=k)\,P_i(X_1=k) $$By MarkovProperty the steps after 1st step only depends on $k$, so consider $k=j$ / $k\ne j$.
when $k=j$,
$$ T_j=1<\infty \Rightarrow P_i(T_j<\infty\mid X_1=j)=1 $$$k\ne j$,
$$ P_i(T_j<\infty\mid X_1=k)=P_k(T_j<\infty)=f_{kj} $$Plug in L.T.P. $\Rightarrow$
$$ f_{ij}=p_{ij}+\sum_{k\ne j}p_{ik}f_{kj} $$Using $f$ expansion in example:
$$ P= \begin{bmatrix} p_{11}&\cdots\ \vdots&p_{21}\ \vdots&&p_{31} \end{bmatrix}
\begin{bmatrix} 0&\frac12&\frac12\ \frac23&0&\frac13\ 0&0&1 \end{bmatrix}, \quad \text{goal: find } f_{13}. $$
Solution: using $f$ expansion below:
$$ \forall i\ne j,\quad f_{ij}=P_i(T_j<\infty)=P_i(X_1=j)+\sum_{k\ne j}P_i(X_1=k)P_k(T_j<\infty) $$$$ = p_{ij}+\sum_{k\ne j}p_{ik}f_{kj} $$in context: $i=1,j=3$
$$ f_{13}=P_1(X_1=3)+\sum_{k\ne 3}\big[P_1(X_1=k)P_k(T_3<\infty)\big] $$[UNCLEAR: small side note near the summation] $\downarrow$ $k=1,2$.
[UNCLEAR: working under the matrix]
$$ \frac12+P(X_1=1)P_1(T_3<\infty)+P(X_1=2)P_2(T_3<\infty) $$$$ \Rightarrow f_{13}=\frac12+\frac12 f_{23}\quad (1) $$Consider State 2:
$$ f_{23}=P_2(T_3<\infty) $$$$ f_{23}=P_2(X_1=3)+[P_2(X_1=2)f_{23})]+[P_2(X_1=1)f_{13} $$$$ \Rightarrow f_{23}=\frac13+0+\frac23(f_{13})\quad (2) $$$$ \begin{cases} f_{13}=\frac12+\frac12 f_{23}\\ f_{23}=\frac13+\frac23 f_{13} \end{cases} $$$$ \frac23 f_{23}=\frac12+\frac13 f_{23} $$$$ \frac23 f_{23}-\frac13 f_{23}=\frac12 $$$$ \frac13 f_{23}=\frac12 $$$$ f_{23}=1 $$$$ 1=\frac13+\frac23 f_{13} $$$$ \frac23=\frac23 f_{13} $$$$ f_{13}=1 $$Original Notes
