Simple Random Walk on Integers

Question

Question concerning a simple random walk on 1D.

Why the probability of hitting $\pm 2^n$ before return to $0$ is $2^{-n}$? I have no idea how to start...

Thank's!

Answer 1

Think of it like this; On your first step you go onto 1 (say). Now the probability you hit 2 before 0 is a half (you either go left or right on your next step). Now we want to know whether we hit 4 next or 0, and we are in the middle of both, so again equal likelihood and the probability is 1/2. So both steps is a half squared and we get a quarter. This logic extended gives the answer you require...

Answer 2

Without loss of generality, suppose that the first step is to $1$ (rather than $-1$). Now you have a fair random walk with a walker at position $1$, and you're interested in the probability that it hits $N = 2^n$ before it hits $0$. You must have learnt a formula for this in class.