Let the Markov Chain consisting of the states $0,1,2,3$ have the transition probability matrix
$$P=\begin{bmatrix}0&&0&&\frac{1}{2}&&\frac{1}{2}\\1&&0&&0&&0\\0&&1&&0&&0\\0&&1&&0&&0\end{bmatrix}$$ Determine which states are transient and which are recurrent
I know that a state $i$ is $$recurrent\space if\space\sum_{n=1}^\infty P_{ii}^n=\infty$$ $$transient\space if\space\sum_{n=1}^\infty P_{ii}^n<\infty$$
I don't know how to apply that definition in that case, however the answer say that all states must be recurrent.
If two states are communicating, then both are either transient or recurrent. In the markov chain above, all states are communicating (see theorem 3.3 in http://www.maths.qmul.ac.uk/~ig/MAS338/Recurrence.pdf). Meaning you can get from state $i$ to state $j$ in finite number of steps.
Note that there is also no absorbing state, hence all four states will be visited infinitely many times. Hence all you need to show is that one state is recurrent.
A state $i$ is recurrent if: (i) the number of visits to it is infinite (your definition) or (ii) probability of returning to $i$ starting from $i$ is 1, or (iii) mean return time is finite.
I think the easiest way to show it in this case is to pick a state and explicitly show that the mean return time is finite.
Pick state 0 for instance, the mean return time to state 0 is 2. Since state 0 communicates with every other state the whole chain must be recurrent.