Random walks and probability of hitting any point

Question

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?

Answer 1

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.

Answer 2

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$.