Probability of returning to a given state after n transitions-Markov chains

Question

Let us denote $f_j^{(n)}$ denote the probability of the first return to state $j $after n transitions. Let $p_{jj}^{(n)}$ be the probability of returning to the state $j$ after $n$ transitions when started from state $j$. My notes contain the following formula $$p_{jj}^{(n)}=\sum\limits_{m=1}^{n}f_j^{(m)}p_{jj}^{(n-m)}$$ Does anyone know how to prove this? I just cannot seem to find a way too do so. Any assistance will be much appreciated. Thanks in advance

Answer 1

Let $R_j$ denote the first return time to $j$, then (strong) Markov property at time $R_j$ yields$$P(X_n=j\mid X_0=j)=\sum_{m=1}^nP(R_j=m\mid X_0=j)P(X_{n-m}=j\mid X_0=j).$$ Nota: It might be time for you to get a good textbook since the proof above is in all those on the subject. You might try Markov chains by James Norris, available on the web.

Answer 2

Consider a trajectory of $n$ transitions, ending in state $j$. Either transition $n$ is the first return to state $j$, which has by definition has probability $f_j^{(n)} = f_j^{(n)} p_{jj}^{(0)}$, or there was a return at some earlier transition(s), the first of which we can label transition $m$.

If first return was at $m \neq n$ (which itself has probability then the probability $f_j^{(m)}$), then the probability of being in state $j$ after $n-m$ more steps,by the definition of $p_{jj}^{(k)}$, is $p_{jj}^{(n-m)}$. So the probability of the event of first return at transition $m$ and end up at $m$ is $f_j^{(m)}p_{jj}^{(n-m)}$.

The total probability is over sum of all possible first "pre-return at transition $m$" probabilities , plus the probability of the first return at transition $n$: $$ \sum_{m=1}^{n-1} f_j^{(m)} p_{jj}^{(n-m)} + f_j^{(n)} p_{jj}^{(0)} = \sum_{m=1}^{n} f_j^{(m)} p_{jj}^{(n-m)} $$ QED