a probability/ random walk brain teaser A random walk $S_n = X_1+\cdots+X_n$ with independent and identically distributed steps $X_i$'s.
Assume $X_i$ is uniform distributed on integer values $\{1,2,3,\cdots, L\}$, i.e $P(X_i = l) = \frac{1}{L}$ for $l\in\{1,2,3,\cdots, L\}$.
Now consider the path $S_n, n\in\mathbb{N}$, i.e each path will take infinite steps and approach to $+\infty$. Let $p_m = P(\text{the path of the random walk path reaches integer m})$
Does $\lim_{m\rightarrow\infty} p_m$ exist? If it does, then what's the value of it?
 A: It does exist and the limit is $\frac 2{L+1}$.  The informal proof is that on each step you average $\frac {L+1}2$ increase in coordinate.  A more formal proof would be to formulate a Markov chain where $p_m$ is the average of $p_{m-1}$ through $p{m-L}$ because you get to $m$ with probability $\frac 1L$ from any of those.  The starting condition is $p_0=1, p_{\lt 0}=0$
A: This is an elaboration of Ross's answer.  We can write $$\begin{bmatrix}p_{m+1}\\p_{m}\\\vdots\\\vdots\\p_{m+2-L}\end{bmatrix}=\begin{bmatrix}
\frac1L&\frac1L&\frac1L&\dots&\frac1L\\
1&0&0&\dots&0\\
0&1&0&\dots&0\\
\vdots&\vdots&\ddots&\vdots&\vdots\\
0&0&\dots&1&0
\end{bmatrix}
\begin{bmatrix}p_{m}\\p_{m-1}\\\vdots\\\vdots\\p_{m+2-L}\end{bmatrix}$$
Let $P$ be the $L\times L$ matrix in the above equation.  Then we are interested in $$\lim_{n\to\infty}P^nV$$ where $V$ is the initial vector, with a $1$ in the first row, and $0$ in all the other rows.
Now, $P$ is the transition matrix of an $L$-state Markov chain.  If the chain is in state $1$, it chooses the next state uniformly at random.  If it is in state $k>1$ it moves to state $k-1$.
It's not hard to guess the stationary probabilities.  Let $q_k$ be the stationary probability that the chain is in state $k$, for $k=1,\dots,L$.  The chain is in state $L-1$ if either it just jumped to that state or it jumped to state $L$ at the previous step.  Thus, $q_{L-1}=2q_L$.  Similarly, $q_{L-2}=3q_L$, and so on.  We have $$1=\sum_{k=1}^Lq_k=\sum_{k=1}^Lkq_L\implies q_L=\frac2{L(L+1)}$$ One can easily verify that these are indeed the stationary probabilities.  Then, $$\lim_{n\to\infty}P^n=\begin{bmatrix}
q_1&q_2&\dots&q_L\\
q_1&q_2&\dots&q_L\\
\vdots&\vdots&\dots&\vdots\\
q_1&q_2&\dots&q_L\\
\end{bmatrix}$$ and each entry of $\lim_{n\to\infty}P^nV$ is $$q_1=Lq_L=\frac2{L+1}$$
