Simple random walk reaching one value before terminating Setup: I have a Simple Random Walk (SRW) that starts in 1 and will terminate whenever it reaches 0. The probability of increasing and decreasing by $1$ is $\frac 1 2$ each.
Question: I'm trying to figure out the probability for the event that the SRW reaches a value $K\in\mathbb N$ before it terminates i.e. reaches 0. In my paper it says that the probability is given by $(1-\frac 1 K).$
Background: I came across this problem while reading a paper about Brownian Motion that is in some way reduced to a Simple Random Walk (I belive the details are unnecessary for this question, if you disagree please ask for further information).
At first, I thought that this question is quite helpful, however it does not include that termination aspect with which I am struggling.
 A: I think I have just got some sort of answer thanks to this question.
So, let's say $S_n=1 + \sum_{k=0}^n X_k$ where $(X_k)k$ are i.i.d. random variables with $\mathbb P (X_k = 1) = \frac 1 2 = 1 - \mathbb P (X_k = -1).$
Then, set $S_T = \inf\{ n\in\mathbb N :S_n \in \{0,K\} \}$ and calculate
$$
\mathbb E[S_T] = 0 \ \mathbb P (S_T = 0) + K\ \mathbb P (S_T = K) = K (1 - \mathbb P (S_T = 0)) = K(1-\mathbb P(T_0 < T_K)),
$$
where
$$
T_0 = \inf\{n: S_n = 0\},\ T_K = \inf\{ n:S_n = K \}.
$$
With the Optional Stopping Theorem, you get $\mathbb E[S_T]= \mathbb E[S_0] = 1$, and thus
$$
K(1-\mathbb P(T_0 <T_K)) = 1,
$$
which then leads to $\mathbb P(T_0 <T_K) = 1-\frac 1 K.$
A: It can be done using elementary calculations (without using optional stpping theorem) as well. Here is a sketch:
Write $X_n$ as your MC. You want to compute $\mathbb{P}(\text{MC visits }K \text{ before visiting 0}|X_0=1)$. Write $l_i=\mathbb{P}(\text{MC visits }K \text{ before visiting 0}|X_0=i)$. Now do a one step conditioning
$$
l_1=\mathbb{P}(\text{MC visits }K \text{ before visiting 0}|X_0=1)\\ = \mathbb{P}(\text{MC visits }K \text{ before visiting 0}|X_1=2,X_0=1)\mathbb{P}(X_1=2|X_0=1) \\
+\mathbb{P}(\text{MC visits }K \text{ before visiting 0}|X_1=0,X_0=1)\mathbb{P}(X_1=0|X_0=1).
$$
Therefore you get
$$
\mathbb{P}(\text{MC visits }K \text{ before visiting 0}|X_0=1) =\frac{1}{2} \mathbb{P}(\text{MC visits }K \text{ before visiting 0}|X_1=2,X_0=1) \\
=\frac{1}{2} \mathbb{P}(\text{MC visits }K \text{ before visiting 0}|X_0=2) =l_2
$$
Now using the similar argument you get for $i\geq 2$,
$$
l_{i}= 0.5l_{i-1}+ 0.5l_{i+1},
$$
simplify and get
$$
l_{i}-l_{i-1}= l_{i+1}-l_{i},
$$
Then use telescopic sum etc.
A: Let $A_k$ be the event "reaching $k$ before reaching $0$". We will show $P(A_k) =\frac{1}{k}$.
Clearly, $P(A_1)=1$.
Next, $P(A_{k+1} ) = P(A_{k+1} | A_k) P(A_k)$.
The conditional probability on the RHS is equal to starting from $k$ and getting to $k+1$ before getting to $0$.
If we reverse the picture and look from $k+1$ to the left,  the conditional probability is the same as starting from $(k+1)-k=1$ and getting to $(k+1)-(k+1)=0$ before getting to $(k+1)-0=k+1$. That is, $1-P(A_{k+1})$. In other words,
$$P(A_{k+1}) = (1-P(A_{k+1})) P(A_k)$$
We solve by induction, assuming $P(A_k)=\frac 1k$. Then
$P(A_{k+1}) = (1-P(A_{k+1}))/k$, or
$P(A_{k+1})(1+\frac1k)=\frac 1k \Rightarrow P(A_{k+1})= \frac{1}{k+1}$.
