Persistence probability for simple random walk

Question

Consider a discrete-time symmetric simple random walk in $\mathbb{Z}$ starting from the origin. How does the probability that the simple random walk stays positive up to time $n \in \mathbb{N}$ decays with $n$? How can I estimate this probability?

Answer 1

Let $S_n$ be the position of the random walk after $n$ steps. By the reflection principle and the Ballot theorem, it follows that $$ P(S_1 S_2 \cdots S_n \neq 0) = \frac{1}{n} E |S_n|. $$ Now (see for example here) we have $$ E |S_n| \sim \sqrt{\frac{2n}{\pi}}, $$ so the probability you are wondering about decays as $O(n^{-1/2})$.