1-D Random Walk Analysis on Transient/Recurrent 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$?
 A: *

*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.
$$


*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.
