Simple Random Walk Absorbing Barriers

Question

I read upon Gambler’s Ruin problem and encountered this interesting question. Consider a simple random walk on $\{0, 1, \ldots, N\}$ with absorbing barriers at $0$ and $N$. What is the probability $u_k$ that the walk is absorbed at $N$ if it begins at a point $k$, $0 \leq k \leq N$?

If the question doesn't indicate anything, does it mean this is symmetric? If so, would it be $u_k=\left(\frac{1}{2}\right)^{(N-k)}$?

Answer 1

Yes the probability of going left and right are the same and equal to $\frac{1}{2}$, but the probability of reaching $0$ is not equal to $(1/2)^{N-k}$. What you calculated is the probability of reaching $0$ in $k$ turns. If it is a symmetric random walk problem with two absorbing barriers then the probability of reaching $0$ is $1-\frac{k}{N}$. If you are interested in derivation I can do it.

Answer 2

Your question is equivalent to asking: what is the probability that the walk starts at k and visits N before visiting 0?

---

This question can be approached, for example, using difference equations. To this end, denote by $X_t$ the value of the process at time t and $T_x$ the number of steps to hit x for the first time. We are looking for the probability $\mathbb{P}(T_0 > T_N \ \vert X_0 = k) = \mathbb{P}_k(T_0 > T_N) = u_k$.

Firstly, we can condition on the first step that the process makes:
$\mathbb{P}_k(T_0 > T_N) = \mathbb{P}_k(T_0 > T_N \ \vert \ X_1 = k+1)\mathbb{P}(X_1 = k+1) + \mathbb{P}_k(T_0 > T_N \ \vert \ X_1 = k-1)\mathbb{P}(X_1 = k-1)$

Note that in our example $\mathbb{P}(X_1 = k-1) = \mathbb{P}(X_1 = k+1) = \frac{1}{2}$. Moreover, we can use the Markov property to write: $\mathbb{P}_k(T_0 > T_N \ \vert \ X_1 = k+1) = \mathbb{P}_{k+1}(T_0 > T_N) = u_{k+1}$. Using those observations we can rewrite the first line as the following recursion: \begin{align} u_k = \frac{1}{2}u_{k+1} + \frac{1}{2}u_{k-1} \end{align}

The initial conditions are: $u_N = 1$ and $u_0 = 0$. The characteristic equation for this recursion is: $\lambda = \frac{1}{2}\lambda^2 + \frac{1}{2}$, which gives the double root $\lambda = 1$. Therefore the general solution is given by \begin{align} u_k = A+Bk \end{align} Using the initial conditions we get $A = 0$ and $B = \frac{1}{N}$, which gives $u_{k} = \frac{k}{N}$.

A note about your solution
Firstly, a sense check comes into play: if we assume $k=0$ does the probability equal zero? In your case it is a NO, so the answer cannot be correct.

What went wrong? As Tigran pointed out, your calculation assumes that the walk goes straight into N, i.e. the walk reaches N in $N-k$ steps. However, you should remember that at any time before the walk is absorbed it may also turn left and go towards zero.