Probability that a random walk reaches an arbitrary value in a given number of steps

Question

I have a simple random walk over $\mathbb{Z}$:

$X_{i+1} = X_i - 1$ (probability $p$) or $X_i + 1$ (probability $1-p$)
and $X_0=0$

I want to find the probability of reaching an arbitrary negative value $-k$ in $n$ steps or less

I am not sure how to approach the problem, given that most of the examples I find are about the probability of reaching $-k$ in any number of steps (eg cliff-falling problems)

If I call $P(k,n)$ the probability of reaching $-k$ in $n$ steps or less, I think the following recursion holds (edit: it does not!):

$P(k+1,n+1)=P(k+1,n) + (1-P(k+1,n)) \times P(k,n) \times p$
with $P(k,k)=p^k \;\forall k>=0$ and $P(0,n)=1 \;\forall n>=0$

But I am not sure how to solve this, and not sure this is the right approach. Any help (with the recursion or with finding another approach) would be appreciated.

Answer 1

Let's start by determining the probability of reaching -k in exactly n steps.

Consider an Example: $-k = -10$. As $X_i$ is odd iff $i$ is odd, the probability is zero if n is odd or $n<10$. Now assume for instance $n=20$. In order to reach $-10$, we have to walk to the left $15$ times ($-1$ case) and $5$ times to the right ($+1$ case).

As the order of these steps is not irrelevant, we obtain that the probability in this case is smaller than \begin{align} \binom{20}{5}p^{15}(1-p)^{5}. \end{align}

Edit: The comment is, of course, correct - we have to avoid reaching $-10$ too early. So we have to figure out how many walks are "forbidden"...

Answer 2

Thanks for your suggestions!

Indeed I can write the probability of reaching -k in exactly n steps: it is $P(X_n = -k) \times \frac{k}{n} $ according to theorem 0.7 of http://cgm.cs.mcgill.ca/~breed/MATH671/lecture2corrected.pdf

And thus I can sum to find the probability $p_{final}$ of reaching -k in n or less steps: $\sum_{i=k,k+2,...n} P(X_i = -k) \times \frac{k}{i}$

Since we know that $P(X_n = -k) = {n \choose \frac{n+k}{2}} \times p^\frac{n+k}{2} \times (1-p)^\frac{n-k}{2}$,
I get $p_{final} = \sum_{j=0,2,...n-k} {k+j \choose \frac{j}{2}} \times (p(1-p))^\frac{j}{2} \times \frac{k}{j+k} \times p^k$ after simplification.

I do not know how to simplify further, if possible?