The following shows one of the questions we were given in lectures a while back:
We have been given the following solutions to this question:
I'm rather confused by these. Take, for example, the probability function $f_{11}^{n}$. In the solutions, it says that this is equal to $$ f_{11}^{n} = \begin{cases} 0.5 \quad \text{ if } n=2 \\ 0.5 \quad \text{ if } n=3 \\ 0 \quad \text{ otherwise} \end{cases} $$ This implies that the probability of the process returning to state 1 in (for example) 4 moves is $0$. However, I can see that this probability is actually $0.25$, as it is given by the path $1 \rightarrow 3 \rightarrow 1 \rightarrow 3 \rightarrow 1$.
What am I missing here?
It is the first visit.
$$f_{ij}^{(n)} = P(X_n = j,\: X_k \not = j, \: k=1,2,\ldots,n-1 \mid X_0 = i)$$
You can make two first revisits to $1$ by
$n=2: \:\:1 \rightarrow 3 \rightarrow 1$
$n=3: \:\:1 \rightarrow 3 \rightarrow 2 \rightarrow 1$
$$f_{ij}^{(n)} = \sum_{k \not = j} p_{ik} f_{kj}^{(n-1)} $$