Simple random walk reaching one value before terminating

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

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