I have a random walk $\{X_n\}$ where each transition causes moving one step to the right (with probability $p$) and one step to the left (with probability $1-p$). Now $X_n \to \infty$ as $n\to\infty$ given that $X_0=0$. I need to prove that the random walk is transient. I can understand it intuitively. But, I want to prove it formally by showing $$\sum_{n=1}^{\infty}p_{00}^{n} < \infty.$$
Another question: If $X_n \to 0$ as $n\to\infty $ given that $X_0=0$, does that imply that the random walk is recurrent. I don't think so. Am I wrong ?
Best Answer
$$p_{00}^{2n}={2n\choose n}p^n(1-p)^n= {1\over 4^n}{2n\choose n}\times [4p(1-p)]^n\leq [4p(1-p)]^n.$$ The sum of the right hand side is a convergent geometric series if $p\neq 1/2$.
Added: I think I understand your problem better now. I hope this is what you want; let me know if anything is unclear.
You want to know how $X_n\to\infty$ implies $\sum_n p^n_{00}<\infty$.
To make a direct connection between the sum and the random walk, let $N=\sum_{n=0}^\infty 1_{(X_n=0)}$ denote the total number of visits to state $0$. Then $\sum_n p^n_{00}=E(N)\leq\infty$.
Now define the return time to zero as $T:=\inf(n>0: X_n=0)$. By the strong Markov property, the random variable $N$ is geometric with probability of success $P(T=\infty)$. If $P(T=\infty)=0$, then $P(N=\infty)=1$ which contradicts $X_n\to\infty$. Therefore, we have $P(T=\infty)>0$ and $E(N)={1\over P(T=\infty)}<\infty$, which shows that the random walk is transient.
Further calculations would give the explicit formula $E(N)=1/(1-2p)$.