Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 ?

share|improve this question
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 $. –  sosha 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 ? –  sosha Feb 18 '13 at 17:56
$X_n\neq X_n/n$ –  Byron Schmuland Feb 18 '13 at 18:05
show 2 more comments

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

share|improve this answer
Thanks. But, I am not asking this. I am interested in the answer of my questions. –  sosha 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. –  sosha 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. –  sosha Feb 18 '13 at 17:43
show 4 more comments

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.