Random walk on $\mathbb{N}$. $\lim_{n\to\infty} S_n/n$?

Question

I have a random walk $S_n$ on the natural numbers $\mathbb{N}$ with the following transition probabilities:

$p(0,1)=1$

$p(i,i+1)=\left\{\begin{array}{lr} 5/8 , & \text{for } i=1,2\text{ mod }3\\ 3/10 ,& \text{for } i=0\text{ mod }3\\ \end{array}\right\}$

$p(i,i-1)=\left\{\begin{array}{lr} 3/8 , & \text{for } i=1,2\text{ mod }3\\ 7/10 ,& \text{for } i=0\text{ mod }3\\ \end{array}\right\}$

How can I find the a.s. $\lim_{n\to\infty} S_n/n$?

I know that in the IID case I could use the Strong Law of Large numbers. But it doesn't seems like I have independence here...any help?

Answer 1

Let $Z_1,Z_2,\dots \in \{-3,+3\}$ be the random walk restricted to $1,4,6,\dots$. Let's find the probability that $Z_i = +3$. For concreteness, suppose the random walk is at $4$, and for $2 \le j \le 6$, let $p_j$ be the probability that the random walk starting at $j$ reaches $7$ before $1$.

Then, $p_2 = \frac{5}{8}p_3, p_3 = \frac{3}{10}p_4+\frac{7}{10}p_2, p_4 = \frac{5}{8}p_5+\frac{3}{8}p_3, p_5 = \frac{5}{8}p_3+\frac{3}{8}p_4, p_6 = \frac{3}{10}+\frac{7}{10}p_5$ gives $p_4 = \frac{25}{46}$.

Now let's find the expected time travelled to go from one $1$ mod $3$ to another. For concreteness again, we focus on starting at $4$. For $2 \le j \le 6$, let $t_j$ denote the expected time to reach $1$ or $7$ if the random walk starts at $j$.

Then $t_2 = \frac{3}{8}(1)+\frac{5}{8}(1+t_3), t_3 = \frac{7}{10}(1+t_2)+\frac{3}{10}(1+t_4), t_4 = \frac{3}{8}(1+t_3)+\frac{5}{8}(1+t_5), t_5 = \frac{3}{8}(1+t_4)+\frac{5}{8}(1+t_6), t_6 = \frac{7}{10}(1+t_5)+\frac{3}{10}(1)$ gives $t_4 = \frac{709}{69}$.

Let $t = t_4$. Then, (justification at end) \begin{equation} \lim_{n \to \infty} \frac{S_n}{n} = \lim_{m \to \infty} \frac{Z_1+\dots+Z_m}{mt}\tag{*} \end{equation} almost surely (we can ignore what happens near $0$, since we care about the limit). Now we can use the law of large numbers, since the $Z_j$'s are independent. Note $\mathbb{E}[Z_j] = \frac{25}{46}(+3)+\frac{21}{46}(-3) = \frac{6}{23}$. Therefore, $\lim_{n \to \infty} \frac{S_n}{n} = \frac{18}{709} \approx .02539$ almost surely.

We now justify (*). Let $T_1,T_2,\dots$ be the time travelled between $Z_j$ and $Z_{j+1}$. We have already shown $\mathbb{E}[T_j] = \frac{709}{69}$. For $m \ge 1$, let $n_m = T_1+\dots+T_m$ be the number of steps travelled to get to $Z_m$. Then $$\frac{S_{n_m}}{n_m} = \frac{Z_1+\dots+Z_m}{T_1+\dots+T_m} = \frac{\frac{Z_1+\dots+Z_m}{m}}{\frac{T_1+\dots+T_m}{m}}$$ and the strong law of large numbers applied to $Z_j$ and $T_j$ (the $Z_j$'s are independent of each other, and the $T_j$'s are independent of each other) give that $$\lim_{m \to \infty} \frac{S_{n_m}}{n_m} = \frac{18}{709}$$ almost surely. This shows convergence along a subsequence. We deduce (full) convergence now. Take $n \in \mathbb{N}$ and $m$ so that $n_m \le n \le n_{m+1}$. Then $$\frac{S_{n_{m+1}}}{n_{m+1}}+\frac{S-S_{n_{m+1}}}{n_{m+1}} \le \frac{S_n}{n} \le \frac{S_{n_m}}{n_m}+\frac{S-S_{n_m}}{n_m},$$ together with the obvious $|S-S_{n_m}|,|S-S_{n_{m+1}}| \le 5$, shows that $S_n/n \to \frac{18}{709}$ almost surely.

Answer 2

Look at the process $R_n=\mathrm{mod}(S_n,3)$ on the state space $\{ 0,1,2 \}$. This is indeed a well defined Markov chain with a finite (row-stochastic) transition matrix

$$P=\begin{bmatrix} 0 & 3/10 & 7/10 \\ 3/8 & 0 & 5/8 \\ 5/8 & 3/8 & 0 \end{bmatrix}.$$

You need the steady state of $P$; actually you just need the steady state probability to be in $\{ 1,2 \}$ and that of $ \{ 0 \}$ but it is easy enough to just get the actual steady state distribution. That is a left eigenvector of that matrix with eigenvalue $1$, i.e. a solution to the equation

$$\begin{bmatrix} p_0 & p_1 & p_2 \end{bmatrix} \begin{bmatrix} 0 & 3/10 & 7/10 \\ 3/8 & 0 & 5/8 \\ 5/8 & 3/8 & 0 \end{bmatrix} = \begin{bmatrix} p_0 & p_1 & p_2 \end{bmatrix}$$

whose entries sum to $1$. This is just a linear algebra problem now. It turns out that $p_0=245/709,p_1=180/709,p_2=284/709$.

What does this mean about $S_n$? The point is that $E[S_{n+1}-S_n \mid R_n=0]=-2/5$ while $E[S_{n+1}-S_n \mid R_n \neq 0]=1/4$. Thus the unconditional expected value $E[S_{n+1}-S_n]$ is $(-2/5) P(R_n=0) + (1/4) P(R_n \neq 0)$.

For finite $n$ this is unresolvable without an initial condition. However, when we average over many such increments, eventually all but finitely many $R_n$ become distributed very nearly according to the stationary distribution. Thus you find that

$$\lim_{n \to \infty} S_n/n = (-2/5)(245/709) + (1/4)(464/709)=\frac{18}{709}.$$

There is a fair amount of additional theory required to completely fill the gaps in rigor here. In particular, you might ask why should $\lim_{n \to \infty} S_n/n = \lim_{n \to \infty} E[S_{n+1}-S_n]$ when the increments are dependent? But in the end it does actually work out this way.