In the question above do I have to calculate the stationary distribution? I've been learning about the ergodic theorem but I'm not sure if it's applicable here.
I know that the probability that Xn = j -> Pj where Pj is the jth entry of the stationary distribution but where does the 1/n come in?
Any help would be greatly appreciated. Thanks!
In very simple words, you start a walk from 0 and have probability $p$ to take a step forward and $1-p$ to take a step backward. It means you take an average step of $2p-1$ in the forward direction, and in $n$ steps your average position will be at $n(2p-1)$. Then ${\rm P}\left( {{{X_{\,n} } \over n} \to \left( {2p - 1} \right)\;{\rm as}\;n \to \infty } \right)$ is the "Law of large numbers".