1-D Random Walk Analysis on Transient/Recurrent

Question

If we consider the 1-d random walk $(X_n)_{n \in N}$ on the set of all integers with transition probability that $p_{ij} = p$ if $j = i + 1$ and $p_{ij} = 1-p$ if $j = i - 1$, how can we obtain the $p_{00}^{(2n+1)}$ and $p_{00}^{(2n)}$. I think we may assume $p_{00}^{(2n)}$ as the number of ways to move $n$ times forward and $n$ times backward. Also, how can I show whether the state 0 is transient/recurrent depending on the value of $p$?

Answer 1

1. Obviously, $p_{00}^{(2n+1)} = 0$, for any $n \in N$.
   Since this is a 1-d random walk, we know that $X_{2n} \sim Binomial (2n, p)$. It can be showed: taking a particular ordered sequence of $n$ forward steps and $n$ backward steps is $p^n(1-p)^n$, thus we can obtain $$ p_{00}^{(2n)} = \frac{(n+n)!}{n!n!}p^n(1-p)^n = \frac{(2n)!}{n!(2n-n)!}p^n(1-p)^n. $$

2. By Stirling's formula, $$ p_{00}^{(2n)} = \frac{(2n)!}{n!(2n-n)!}p^n(1-p)^n = \frac{[4p(1-p)]^n}{\sqrt{n \pi}}, $$ we let $$ a_n = \frac{[4p(1-p)]^n}{\sqrt{n \pi}}, $$ and then we can use the ratio test for $a_n$. $$ \lim_{n \to \infty} |\frac{a_{n+1}}{a_n}| = 4p(1-p), $$ since $p \in [0,1]$ and $4p(1-p) \in [0,1]$. This indicates that the convergence of test depends on the value of $p$.

1). Consider $p = \frac{1}{2}$, we can obtain $$ a_n \sim \frac{1}{\sqrt{2 \pi n}} $$ Since $a_n \sim \frac{c}{\sqrt{n}}$, where $c = \frac{1}{\sqrt{2 \pi}}$, then we can get $$ \sum a_n = \sum p_{00}^{(2n)} = + \infty, $$ which indicates the state $0$ is positive recurrent.

2). Consider $p \neq \frac{1}{2}$, the ratio test shows that $\sum p_{00}^{(2n)}$ is convergent. By Cauchy criterion, $$ \lim_{n \to \infty} p_{00}^{(2n)} = 0, $$ which implies the state $0$ is transient.