# transience and recurrence of a random walk

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 ?

-
Since the random walk either steps to the left or to the right, it is impossible that $X_n\to0$. – Byron Schmuland Feb 18 '13 at 17:27
this is not correct. if $p=1/2$ then $X_n \to 0$ as $n\to\infty$. – RIchard Williams Feb 18 '13 at 17:38
No, you are wrong. If $p=1/2$ the random walk is recurrent and visits every state infinitely often. – Byron Schmuland Feb 18 '13 at 17:42
Note that the state at time $n$ ($X_n$) can be written as $\sum_{i=1}^{n}Y_i$ where $Y_i$s are independent and $P(Y_i=1)=p=1-P(Y_i=-1)$. If $p=1/2$ then using strong law of large numbers $\frac{\sum_{i=1}^{n}Y_i}{n} -> E[Y_i]=0$ as $n->\infty$. Hence $X_n -> 0$ as $n->\infty$. Where am I wrong ? – RIchard Williams Feb 18 '13 at 17:56
$X_n\neq X_n/n$ – Byron Schmuland Feb 18 '13 at 18:05

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

-
Thanks. But, I am not asking this. I am interested in the answer of my questions. – RIchard Williams Feb 18 '13 at 17:09
@prasenjit You said that you want to show $\sum_{n=1}^{\infty}p_{00}^{n} < \infty.$ I have done this for you. – Byron Schmuland Feb 18 '13 at 17:11
yes, i want to show this. But from $X_n \to \infty$ as $n\to\infty$ given that $X_0=0$. Also, I want to know whether $X_n \to 0$ as $n\to\infty$ given that $X_0=0$, imply that the random walk is recurrent. I am interested in the specific questions I have asked. – RIchard Williams Feb 18 '13 at 17:30
So you want to prove $\sum_{n=1}^{\infty}p_{00}^{n} < \infty$ without using the formula for $p_{00}^{n}$? Your questions are not very clear, I'm afraid. Good luck! – Byron Schmuland Feb 18 '13 at 17:33
yes. Till now i have proved that for $p > 1/2$, $X_n \to \infty$ as $n\to\infty$ and for $p < 1/2$, $X_n \to -\infty$ as $n\to\infty$. I want to prove that the random walk is transient from these two conditions. – RIchard Williams Feb 18 '13 at 17:43