Random Walk on Integers - Transience If I have a random walk on integers such that we start at state 0 and can move left or right with probability .5, my intuition says that state 0 is recurrent as $n \to \infty$.
However, from the following resource, it is proven that $P_{n} = \frac{1}{\sqrt{2\pi n}}$ so I just wanted to confirm that as $n \to \infty$ all states are indeed transient since $P_{n} \to 0$
http://www.math.uchicago.edu/~may/VIGRE/VIGRE2007/REUPapers/FINALFULL/Gupta.pdf
 A: A minor correction: the probability to return to zero in $n$ steps starting from zero is zero when $n$ is odd, and is asymptotic to $\frac{1}{\sqrt{2 \pi n}}$ when $n$ is even and large.
That said, you are correct that the simple symmetric random walk on the integers is recurrent. Your reference proves this by noting that the expected number of visits to zero is the infinite sum of the probability that $S_n=S_0$. In this case, since $p_{2n}$ is asymptotic to $\frac{C}{\sqrt{n}}$, the sum diverges by the usual p series test. So the expected number of visits is infinite. Your link then proves that it is impossible for this to happen when there is a positive probability to never return to zero, using a geometric random variable (page 6).
A: First, this is meaningless unless you tell us what you mean by $P_n$. Evidently $P_n$ is the probability that you are at the origin after $n$ steps. Second, that paper does not show that $P_n=\frac{1}{\sqrt{2\pi n}}$. It's clear that $P_n=0$ for odd $n$, and for even $n$ they get $P_n\sim \frac{1}{\sqrt{2\pi n}}$.
Anyway, $P_n\to0$ does not show that the walk is transient! In fact $\sum P_n=\infty$, which implies that it is recurrent. (See Theorem 11 in the paper you cite...)
