how to calculate this sum $f_{ij}=\sum\limits_{i=0}^\infty f^{(n)}_{ij}$

Question

My final goal is to calculate this sum for a given Markov chain $f_{ij}=\sum\limits_{i=0}^\infty f^{(n)}_{ij}$ we have the Markov chain graph and we have that $f^{(n)}_{ij}=\sum\limits_{k<>j}P_{ik}f^{(n-1)}_{kj}$ , so i was able to calculate

$f^{(5)}_{ij}=(1/2)^5$

$f^{(6)}_{ij}=(1/2)^6*2=(1/2)^5$

$f^{(7)}_{ij}=(1/2)^7*3=(1/2)^6+(1/2)^7$

$f^{(8)}_{ij}=(1/2)^8*6=(1/2)^6+(1/2)^7$

$f^{(9)}_{ij}=(1/2)^9*11=(1/2)^6+(1/2)^8+(1/2)^9$

$f^{(10)}_{ij}=(1/2)^{10}*22=(1/2)^6+(1/2)^8+(1/2)^9$

What I really need is the general expression $f^{(n)}_{ij}$ so I could calculate the sum above and I think that I'm supposed to deduce it from the terms I could calculate, but I couldn't deduce the general expression no matter how i tried, even though it has a pattern, so is it not possible to deduce one?

Ps: I was able to calculate $f^{(1)}_{ij}=f^{(2)}_{ij}=f^{(4)}_{ij}=0$ and $f^{(3)}_{ij}=(1/2)^3$ as well, but they don't have the same pattern so I didn't mention them above.

I don't even know if this question is appropriate for this site but I have really reached a dead end so I would appreciate any kind of help.

The graph in the picture below shows the transition probabilities. State $i$ is $2$ and state $j$ is $6$.

Answer 1

Calculating $f_{26}$ by computing $f_{26}^{(n)}$ for all $n$ is pretty much a hopeless task. There are just too many different ways to get from $2$ to $6$ in a large number of steps, so the expression gets arbitrarily complicated.

In this case, $6$ is an absorbing state and $f_{26}$ counts the probability that we'll ever end up in state $6$. The key thing is to notice that:

• The only absorbing states are $5$ and $6$.
• Every time we're in state $3$, we're equally likely to end up at state $5$ or state $6$. (But we can also wander off to $1$ or $2$).
• From states $1$, $2$, or $4$, we always get to state $3$ eventually.

So we are guaranteed to eventually end up in states $5$ or $6$. The only way to do so is through state $3$, and states $5$ and $6$ are equally likely destinations from state $3$. Therefore $f_{26} = f_{25} = \frac12$.

---

Alternatively, from the equation $$f^{(n)}_{ij}=\sum\limits_{k \ne j}P_{ik}f^{(n-1)}_{kj},$$ rather than compute each $f^{(n)}_{ij}$ separately, we can sum over all $n$ to get $$ f_{ij} = \sum_{k \ne j} P_{ik} f_{kj} $$ which, together with $f_{56} = 0$ and $f_{66} = 1$, should determine $f_{16}, f_{26}, f_{36}, f_{46}$.