# Stationary distribution of random walk

Let $\mathcal{X}$ be a simple random walk with barrier at zero, state space $E = \mathbb{N}_0$ and transition matrix below with $0<q<1$.

\begin{bmatrix} 1-q & q & & & \\ 1-q & 0 & q & & \\ & 1-q & 0 & q & \\ & & 1-q & 0 & q \\ & & & \ddots & \ddots & \ddots \end{bmatrix}

How would I determine the stationary distribution for $q < \frac{1}{2}$? And why is the condition that $q < \frac{1}{2}$ necessary for $\mathcal{X}$ to have a stationary distribution?

Also, is saying that $\mathbb{P}(X_n = n |X_0 =0) = q^n >0$ and $\mathbb{P}(X_n =0 | X_0 =n) = (1-q)^n >0$ enough to show $\mathcal{X}$ is irreducible?

Update: I get $\pi_n = \left( \frac{1-q}{q} \right)\pi_{n+1}$ for all $n \in \mathbb{N}_0$, but why is the condition that $q < \frac{1}{2}$ necessary for $\mathcal{X}$ to have a stationary distribution?

-

From $\pi_n = \left( \frac{1-q}{q} \right)\pi_{n+1}$ you can get $\pi_n = \left( \frac{q}{1-q} \right)\pi_{n-1} = \left( \frac{q}{1-q} \right)^n \pi_0$.

$\sum\pi_i=\sum \left( \frac{q}{1-q} \right)^i \pi_0 = \pi_0 \sum \left( \frac{q}{1-q} \right)^i =1$

So $\pi_0$ should be >0, and the summation should converge, that is true only if $\frac{q}{1-q} < 1$, so $q$ should be less than $1/2$.

Another way to see it is note that "average of the distribution" ($\sum(i*\pi_i)$) move forward for the state $0$ (from here you can only stay here or go one step forward), and move backward for all the other state iff $q<1-q<1/2$. For a stationary distribution the state should be time-independent, so the mean of that distribution should be time-independent, so can not "move forward".

-
Thanks @carlop. I understand everything you did, except, how do you get $\left( \frac{q}{1-q} \right)^n \pi_0$? As in, how did you get that $\left( \frac{q}{1-q} \right)\pi_{n-1} = \left( \frac{q}{1-q} \right)^n \pi_0$? Thanks. – Richard Apr 28 '12 at 14:47
If you have a recurrence relation $f(n)=a*f(n-1)$, the solution are of type $f(n)=k*a^n$ (just substitute, and see that the equation hold, and note that the solution is unique given a fixed starter point). In this case, the costant $k$ should be equal to $\pi_0$. – carlop Apr 28 '12 at 15:40
Thanks @carlop, most appreciated again! I just have one more question, is there any other "famous"/"well known" recurrence relations like the one you posted above? – Richard Apr 29 '12 at 16:35
@Richard: consider take a look at wikipedia page: en.wikipedia.org/wiki/Recurrence_relation or en.wikipedia.org/wiki/Fibonacci_number. – carlop May 2 '12 at 7:51
Thanks carlop :) – Richard May 3 '12 at 14:32