# Random walks and probability of hitting any point

I'm working through Williams' Probability with Martingales book and had a question.

Suppose we have an iid increment random walk on the integers. $S_n = \sum_1^n Y_i$ where $P(Y_i = 1) = p, P(Y_i = -1) = 1-p$. On page 102, Williams proves that the random walk will almost surely hit $1$ in finite time for the symmetric case ($p= 0.5$) by constructing the Wald martingale from the random walk. My questions are as follows:

1) Could this method not hold for any positive integer in the symmetric case, that is, could we not replicate this to show that the random walk hits any $x \in \mathbb{N}$ almost surely in finite time? Or is there some other method one must employ? As I see it, it should work.

2) What if we had a biased random walk, where $p \neq 0.5$? Say, we have $p > 0.5$? Intuitively, it makes sense that the random walk will now eventually go to $+ \infty$. Formally, how would we show that we could hit any $x \in \mathbb{N}$ in almost surely finite time? Is it simply a case of establishing submartingale convergence to $+\infty$ and concluding that we must pass through every positive integer at some finite step for that to happen or is there a more careful argument to be made?

• In the second case, probability of never hitting $-1$ is non-zero! – dEmigOd May 5 '18 at 17:48

You don't even need martingales. Hint: First step analysis. Once you show that the probability of hitting $1$, starting from $0$ is almost surely finite [which William's appears to have established for you], you can show the result for any natural number (assuming iid increments which allow you to say the process is Markovian). Let me know if you need more details.
1. If you know you hit 1 a.s., then you hit any $x \in \mathbb{N}$ a.s. also, by just restarting the process after you hit 1 using the strong Markov property. Now hitting 2 is the same as hitting 1 was to begin with, so it happens a.s., and you continue by induction.
2. Pretty much any argument that worked in the symmetric case should work in the right-biased case. For example, since the symmetric case was a martingale, the right-biased case is a submartingale, so things are "only better" for showing that you will eventually move to the right in net. Similarly, if you use first step analysis and a recurrence relation to compute the probability to hit $1$ before $-k,k \in \mathbb{N}$, the same argument goes through and now the probability goes to $1$ faster as $k \to \infty$.