Consider the random walk on $S={0, . . . , N}$, defined as follows. We are given $p, q, r >0$ with$ p+q+r= 1$. The walk increases by 1 with probability $p$, decreases by 1 with probability $q$, and stays put with probabity $r$.What is its stationary and limiting distribution?

I writed out the transition matrix.

$$ \begin{pmatrix} r & p & \cdots &⋯ &⋯&q\\ q & r & p &\cdots&\cdots&\cdots \\ 0 & q & r &p &\vdots&\vdots\\ 0 & 0 & q &r &p &⋯\\ p & 0 & 0 &0 &q & r \\ \end{pmatrix} $$

the stationary matrix satisfies $$\pi=\pi p$$ then it satisfies $$p_{i,j} \pi_i = p_{j,i} \pi_j$$ $$p\pi_1 = q\pi_2, p\pi_2 = q\pi_3, p\pi_3 = q\pi_4...$$ the stationary situation then becomes

$$ \begin{pmatrix} 1 & \frac{p}{q}\pi_1 & (\frac{p}{q})^2\pi_1 & (\frac{p}{q})^3\pi_1 &...&(\frac{p}{q})^N\pi_1\\ \end{pmatrix} $$

We can then get the distribution because it adds up to 1.

Is my method correct? Then, for the limiting distribution, I think there is no limiting distribution because it seems not to be converging to a specific state. Is it true? Thank you!

  • $\begingroup$ Given your transition matrix, do you also mean than the walk can also move from $N$ to $0$ as if $0=N+1$? $\endgroup$ – Saad Oct 8 '18 at 13:15
  • $\begingroup$ yes. the walk can get from N to 0 and from 0 to N $\endgroup$ – stedmoaoa Oct 8 '18 at 13:18

The stationary measure will be the uniform measure, which you could see by a soft argument: the transition matrix is irreducible and aperiodic, and thus has a stationary measure; furthermore, it is invariant under the map $k \mapsto k+1$, implying that each state must get the same measure.

You could also show this manually: let $\mu_j = \frac{1}{N+1}$ for each $j \in \{0,1,\ldots,N\}$. Then $$(P \mu)_j = p \mu_{j-1} + r \mu_{j} + q \mu_{j+1} = \frac{p + r + q}{N+1} = \frac{1}{N+1} = \mu_j$$

where the indices are $\mod{N+1}$.

EDIT: some further comment on the invariance thing; let $A$ be the map that cycles the states, i.e. $A (x_0 ,\ldots, x_{N})^T = (x_N,x_0,x_1,\ldots,x_{N-1})^T\,.$

Then note that $PA = P$. If you set $\mu$ to be the stationary measure of $P$ (i.e. $\mu P = \mu$), then it must be invariant under $A$: $$\mu PA = \mu P \implies \mu A = \mu\,.$$ Iteratively applying $A$ shows that $\mu$ must be uniform.

  • $\begingroup$ I do not quite understand the argument since invariant under the map. Can you be more specific? $\endgroup$ – stedmoaoa Oct 8 '18 at 13:39
  • $\begingroup$ @stedmoaoa, sure I added a bit more; you can also just look at the direct argument instead, but the soft argument is the more intuitive reason. $\endgroup$ – Marcus M Oct 8 '18 at 15:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.