Bound of the Absolute Value of a Random Walk

Question

Let $W(n)$ be a simple random walk on $\mathbb{N}$ with $W(0) = w_0$. That is, $\mathbb{P}\left[W\left(n+1\right) = W(n)+1\right)] = 1/2$ and $\mathbb{P}\left[W\left(n+1\right) = W(n)-1\right)] = 1/2$ for all $n$.

Is it true that $|W(n)| \leq |w_0| + \sqrt{n} $? If so , how do I show this?

Answer 1

This is not true for any $n>1$. Suppose $w_0\geq0$. Then we have $P(|W(n)|>|w_0|+\sqrt{n})\geq P(W(n)>w_0+n)=(1/2)^n>0.$