Consider a simple symmetric random walk $(S_n)_{n \geq 0}$ with $S_0 = 0$ on $\mathbb{Z}.$ We add the killing probability: At each step, with probability $\alpha$, the random walk is killed and the process stops. With probability $1-\alpha$, the random walk continues. Let $$\tau_1 = \min \{n : S_n = 1\}.$$ Set $\tau_1 = \infty$ if the process is killed before the first time it reaches $1.$ I want to find $\mathbb{P}(\tau_1 < \infty).$ To me, this is the probability that the random walk reaches $1$ before it is killed. I am struggling with this problem (I am doing practice qualifying exams and this was a question on an earlier exam, so obviously, no solution is provided).

My first thought was to calculate $$\sum_{n=0}^{\infty}\mathbb{P}(S_n = 1) (1- \alpha)^{2n+1}.$$ However, I now know this is completely wrong. I know that you can only get to $1$ in an odd number of steps but $\mathbb{P}(S_n=1)$ includes the times that the random walk goes above $1$ and then gets back to $1$ in $n$ steps, which I do not want. So, I am completely stuck. Does anyone have any ideas?


  • $\begingroup$ You seem to want $\sum_{n=0}^{\infty}\mathbb{P}(R_{2n+1} ) (1- \alpha)^{2n+1}$ where $R_n$ is the event that in an ordinary random walk you reach $1$ for the first time at step $n$. Here $\mathbb{P}(R_{2n+1} )$ is related to Catalan numbers but I suspect you are expected to find it yourself $\endgroup$
    – Henry
    Jun 29, 2022 at 0:01
  • 1
    $\begingroup$ The most natural approach I can think of to solve this is to set up a recurrence relation telling you the probability of reaching 1 starting at any given non-positive number, and then use the value at 0. $\endgroup$
    – Fishbane
    Jun 29, 2022 at 0:05
  • $\begingroup$ @Fishbane I was thinking of this. If you have any more details I’d love to see them. Thanks. $\endgroup$
    – user545426
    Jun 29, 2022 at 0:29
  • 1
    $\begingroup$ @MathIsLife12 I won't write out the full derivation as it a too long for a comment and it is pretty standard, however there is one thing worth paying attention to. There is a fairly obvious reccurence to use, however it is a second order reccurence relation so it seems like it would be of no help as we only know one value. However when dealing with reccurence relations for probabilities it is important to remember that all values need to be in the range [0,1]. We can use this to eliminate one degree of freedom and then conclude by using boundary conditions. Hope that helps. $\endgroup$
    – Fishbane
    Jun 29, 2022 at 0:42

1 Answer 1


Let $p_k=P_{k}(\tau_1<\infty)$, where the subscript $k$ indicates the starting point. I assume the killing happens with probability $\alpha=1-\beta$ at each step before the walking. Then $p_0=\beta(1/2+p_{-1}/2)$. On the other hand, by independence of the walk from $-1$ until reaching $0$ and from $0$ until reaching $1$, we have $p_{-1}=p_0^2$. Thus $$p_0=\beta(1+p_0^2)/2\,.$$ The solutions of this equation for $p_0$ are $$\frac{1\pm\sqrt{1-\beta^2}}{\beta}\,,$$ and only one of these is in $[0,1]$, so $$p_0=\frac{1-\sqrt{1-\beta^2}}{\beta}=\frac{\beta}{1+\sqrt{1-\beta^2}}\,. $$


You must log in to answer this question.