# Recurrent random walk

Let $S_n=S_0+\sum_{i=0}^n{X_i}$ be a random walk with increment distribution $p$ and n-th step distribution $p_n(x)=\mathbb{P}[S_n=x\mid S_0=0]$. We say that a random walk is recurrent if $\mathbb{P}[S_n=0\ i.o.]=1$. Assume that we are in dimension 1, then we want to check that $S_n$ is recurrent. We define $N:=\sum_{n\geq0}{1_{\{S_n=0\}}}$. Then $\mathbb{E}[N]=\sum_{n\geq 0}{\mathbb{P}[S_n=0]}=\sum_{n\geq0}{p_n(0)}$. Say that we know that $\mathbb{E}[N]=\infty$.

Then we want to conclude that the walk is recurrent, i.e. that $\mathbb{P}[\limsup_{n\rightarrow\infty}S_n=0]=1$. I would like to use Borel-Cantelli to conclude this but I need the independence of the events, which I do not think I can assume. Is this the correct way?

I guess you meant to write $\mathbf{E}[S_n]=0$ because if $\mathbf{E}[N]=0$ this would mean that the probability of returning to zero is zero and the walk would be transient.
For recurrence you have to show that $\mathbf{E}[N]$ (as you defined) is infinite. Here is a link to a solution
• Oh yes...I wrote it wrong thank you. I was meaning $\mathbb{E}[N]=\infty$ and not $0$. Thank you. I took a look to your solution but the problem is that they use another definition for recurrent. My point is really how to go from the fact that $\mathbb{E}[N]=\infty$ to $\mathbb{P}[S_n=0\ i.o.]=1$ – sky90 Dec 2 '15 at 4:34
I think I got the answer. The key point is that $N$ has a geometrical distribution. Assuming that $p=p_n(x,0)$ for $x\in\mathbb{Z}^d$, is the probability that the random walk always return to $0$, we get that $\mathbb{P}[Y=k]=p^{k-1}(1-p)$ for $k\geq1$, and so $\mathbb{E}[Y]=\sum_{k\geq1}{k\mathbb{P}[Y=k]}=\frac{1}{1-p}$.