Equilibrium distribution for a modified 1D random walk which has a probability of $1/3$ to return to the origin at each step

Question

Consider a one dimensional random walk starting at $0$ which obeys the rule that at each iteration there is a $1/3$ chance of taking a step to the left, a $1/3$ chance of taking a step to the right, and a $1/3$ chance of returning to the origin. After many iterations, what is the equilibrium probability distribution $p_n$ for the walker to reside at position $n$?

(This question is partially inspired by this other recent question.)

I began by simulating this process numerically. I started with a random walker at $n = 0$ and let it equilibrate for $1000$ iterations. Then I let it run for another ${10}^6$ iterations and recorded the frequency with which the walker arrived at each position $n$. (By doing this, I'm implicitly assuming ergodicity.) The resulting empirical equilibrium distribution $p_n$ is plotted below:

Looking at these results, I'm inspired to guess a solution of the form $p_n \propto \lambda^{|n|}$ for some $0<\lambda<1$. With proper normalization, so that $\sum_{n=-\infty}^{+\infty} p_n = 1$, this guess becomes: \begin{equation} p_n = \frac{1-\lambda}{1+\lambda}\lambda^{|n|} \qquad (1) \end{equation} It is clear that at equilibrium we must have \begin{equation} p_n = \frac{1}{3}\left(p_{n-1} + p_{n+1}\right) \qquad (2) \end{equation} for $n\neq 0$. This is because in order to land on $n$, the walker will have to have come from either $n-1$ or $n+1$, and it has a probability of $1/3$ of jumping from either of those onto $n$.

If we plug our guess (1) into (2), we arrive at \begin{equation} 1 = \frac{1}{3}\left(\frac{1}{\lambda} + \lambda\right), \end{equation} the relevant solution of which is $\lambda = (3-\sqrt{5})/2 \approx 0.381966$. If I plot the guess (1) with that value of $\lambda$, I find that it is a perfect match to the empirical distribution. So it would seem we have found the correct expression for the equilibrium probability distribution. My question is: How could I have derived the form $p_n \propto \lambda^{|n|}$ without guessing it?

Answer 1

You have from (2) the recurrence $p_{n+2}- 3p_{n+1}+p_{n-1}=0$ for positive $n$ and similarly $p_{n-2}- 3p_{n-1}+p_{n}=0$ for negative $n$

and the two roots of $x^2-3x+1$ are $\frac{3\pm \sqrt{5}}{2}$

so you will have $p_n = A\left(\frac{3+ \sqrt{5}}{2}\right)^{|n|} + B\left(\frac{3- \sqrt{5}}{2}\right)^{|n|}$ for some $A$ and $B$

You will need $\sum\limits_{-\infty}^\infty p_n=1$

and, as John Barber points out in a comment, $\left|\frac{3+ \sqrt{5}}{2}\right| > 1$ and $\left|\frac{3- \sqrt{5}}{2}\right| < 1$ so you will require

$A=0$ to get the sum to converge, and

$B$ to be the reciprocal of $\sum\limits_{-\infty}^\infty \left(\frac{3- \sqrt{5}}{2}\right)^{|n|}$.

Answer 2

The general solution to recurrence relations of the form $$Ap_{n+1}+Bp_{n} + Cp_{n-1} = 0$$ is $$p_n = a_1 \lambda_1^n + a_2 \lambda_2^n$$ where $a_i$ are constants and $\lambda_i$ are the roots for the auxiliary polynomial $A\lambda^2 + B \lambda + C = 0$. One can deduce this from trying the ansats $p_n = a \lambda^n$, as you had done. There is a connection that can be made between these discrete difference equations and the continuous analogue, which are differential equations of the form $$ A\frac{d^2f}{d^2x} + B \frac{df}{dx} + Cf = 0$$ for which you try the ansatz $f(x) = e^{\lambda x}$. In general the form of both these ansatzes are motivated from using the eigenfunction of their respective first order difference/differential operators, e.g. in the discrete case, solving $$A p_n + Bp_{n-1} = 0.$$ which can be done by hand.

After obtaining the general form one must make use of boundary/normalisation conditions in order to deduce the true form of $p_n$, e.g., since we must have $\sum_n p_n = 1$, we have to get rid of the $\lambda_i$ which blows up in each of the cases $n > 0$ and $n < 0$, and since our process is symmetric it is safe to assume that the stationary distribution is symmetric as well.

These heuristics allow us to deduce that $p_n \propto \lambda^n$.