Show that the simple, symmetric random walk has no equilibrium distribution.

Question

Question. Consider the simple, symmetric random walk on the integers given by the transition probabilities $$p_{ij}=\begin{cases}\frac{1}{2} & j=i-1\ \text{or}\ j=i+1,\\ 0 & \text{otherwise} \end{cases}.$$

Show this has no equilibrium distribution.

Attempt. By definition, a countably infinite Markov chain has an equilbrium distribution w if it satisfies $$w_j=\sum_{i\in S}w_ip_{ij},\quad\sum_{i\in S}w_i=1.$$

Now, we compute the first few terms and see if we can spot a general pattern. We have $$w_0=\frac{1}{2}w_{-1}+\frac{1}{2}w_1,$$ $$w_1=\frac{1}{2}w_0+\frac{1}{2}w_2,$$ $$w_2=\frac{1}{2}w_1+\frac{1}{2}w_3,$$ or more generally $$w_n=\frac{1}{2}w_{n-1}+\frac{1}{2}w_{n+1},$$ for all $n\in S$.

This is where I get a bit stuck. First, I was thinking of solving the linear recurrence by setting $y^n:=w_n$ which gives me $$y^n=\frac{1}{2}y^{n-1}+\frac{1}{2}y^{n+1},$$ or equivalently $$1=\frac{1}{2y}+\frac{1}{2}y,$$ which reduces to $$y^2-2y+1=0\Rightarrow (y-1)(y-1)=0\Rightarrow y=1.$$ This then gives the solution $$w_n=c_1+c_2n,$$ but I fail to see what I can make of this.

Secondly, I was thinking of utilising condition, arriving to $$\frac{1}{2}\Big(...+w_{-1000}+w_{-999}+...+w_{-1}+w_0+...+w_{999}+w_{1000}+...\Big)=1,$$ which can't hold since we have an infinite sum on the left hand side. So from there, can we conclude that this has no equilibrium distribution? This seems a bit more promising; but would appreciate some verification on this nonetheless.

Thanks in advance.

Answer 1

The two problems with your approaches are

1. Even if there is an equilibrium distribution, it might not have the form $w_n = y^n$ for any $y$. So assuming that form and getting a contradiction wouldn't help.
2. There's no contradiction in an expression with an infinite sum having a finite value.

Here are some things you could try instead.

1. The maximum principle. Argue that there must be some state $i$ for which $w_i = \sup\{w_j : j \in \mathbb Z\}$. Then $w_i = \frac12 w_{i-1} + \frac12w_{i+1} \le \frac12 w_i + \frac12 w_i = w_i$. Equality holds, which means that $w_{i+1} = w_{i-1} = w_i$, and repeating this argument, we can show that all the $w_i$ are equal. This contradicts the fact that they add up to $1$.
2. If there were an equlibrium distribution $w$, then $\frac1{w_i}$ would be the expected return time from state $i$ back to state $i$. You can show that this expected return time is infinite in a number of ways, getting a contradiction.
3. Argue that the detailed balance equations $p_{i,i+1}w_i = p_{i+1,i} w_{i+1}$ must hold, as suggested in Math1000's comment above. (Maybe look at the number of transitions into and out of the set $\{i+1,i+2,i+3,\dots\}$.) Here, it implies $w_i = w_{i+1}$, which we've already seen is a contradiction.

In general, there's probably a lot of ways to prove that if there is an equilibrium distribution $w$, then all the $w_i$ are equal. If you do that, then a contradiction is not far off, since an infinite sum of equal values is either $\infty$ (if they're nonzero) or $0$ (otherwise), never $1$.