a probability/ random walk brain teaser

Question

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?

Answer 1

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$

Answer 2

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}$$