Be $(X_n)_{n\ge0}$ a discrete time Markov Chain with a finite space state $S$.
Suppose that the chain starts from state $i$: $X_0 = i$.
Be ${p_{ij}}^{\left ( n \right )} = \mathbb{P}(X_n=j|X_0=i)$ and $T_j=inf(n \ge 1: X_n=j)$ (first passage time to $j$).
How can I calculate the probability that, starting from state $i$, the chain reaches state $j$ in exactly 3 steps?
I thought of two possible solutions:
Solution 1: ${p_{ij}}^{\left ( 3 \right )}-{p_{ij}}^{\left ( 2 \right )}-{p_{ij}}^{\left ( 1 \right )}$
Solution 2: $\mathbb{P}_i(T_j=3) = \mathbb{P}(X_3=j,X_2\neq j,X_1\neq j|X_0=i)= \sum_{k_2 \neq j}\sum_{k_1 \neq j} \mathbb{P}(X_3=j,X_2=k_2 ,X_1=k_1|X_0=i)$
Which one is correct? What does each mean?
The second is fine. It considers all paths that avoids $j$ in step 1 and 2 as you wanted. The first doesn't correspond to the right counting of paths. There is a formula, though not very nice: $$p_{ij}^{(3)} - p_{ij}^{(2)}p_{jj} - p_{ij} p_{jj}^{(2)} + p_{ij}p_{jj}p_{jj}$$ It takes all paths and remove those hitting in 2nd or 1st step but then adds one contribution that has been subtracted twice. There are general formulae of this kind.