We define a first hitting time of simple random walk 1D by $$\tau _z=\min\{n:S_n=z\}.$$ I read a paper which write
...a classical result for random walks in $d=1$ with zero mean adn finite variance,namely $\mathbb{P}(\tau_z>n)=O\left(\frac{1}{\sqrt{n}}\right)$ for all $z\neq0$ with $\tau_z$ the first hitting time of z...
I already know that $$\mathbb{P}(\tau_z=n)=\frac{|z|}{n}\mathbb{P}(S_n=z)=\frac{|z|}{n}\frac{1}{2^n}\binom{n}{\frac{n+z}{2}}.$$
So I cumsum the formula above from $n$ to $\infty$ but can't figure it out.
How to get this classical result: $$\mathbb{P}(\tau_z>n)=O\left(\frac{1}{\sqrt{n}}\right).$$
Thanks for answering.