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)}$?
Best Answer
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.