Absorption Probability on a Finite Random Walk
You start at position 17 on an integer line with absorbing barriers at positions 0 and 100. At each step, you move left or right with equal probability $p = \frac{1}{2}$.
What is the probability that you return to position 17 at least once before being absorbed at 0 or 100?
Hints
- Think about what happens on the very first step -- you move to 16 or 18 -- and from each of those, you need to get back to 17 before hitting a barrier.
- From position 16, the only way to get absorbed without passing through 17 again is to be absorbed at 0. From position 18, the only way is absorption at 100. This turns each case into a standard gambler's ruin problem.
- Apply the gambler's ruin formula: on $\{a, \ldots, b\}$ with symmetric steps, the probability of hitting $b$ before $a$ starting from $x$ is $(x - a)/(b - a)$.
Worked Solution
How to Think About It: This is a symmetric random walk on $\{0, 1, \ldots, 100\}$ with absorbing barriers at 0 and 100. The walker starts at 17 and we want the probability of ever revisiting 17 before absorption. On the infinite line, a symmetric 1D walk is recurrent -- it returns to every state with probability 1. But absorbing barriers change everything: the walk will eventually hit 0 or 100, and it might do so without ever coming back to 17.
Quick Estimate: The probability of being absorbed at 0 (rather than 100) from position 17 is $83/100 = 0.83$ by the classical gambler's ruin. Starting at 17, the walk must first step to 16 or 18. From either neighbor, there is some probability the walk gets absorbed before revisiting 17. The probability of NOT returning should be related to $1/\min(17, 83)$. So roughly $P(\text{return}) \approx 1 - 1/17 \approx 0.94$.
Approach: Use the connection between return probability and absorption probability via the gambler's ruin.
Formal Solution:
Let $r$ be the probability of returning to position 17 before absorption. Consider the first step: from 17, you move to 16 or 18 each with probability $1/2$.
From position 16, let $\alpha$ be the probability of reaching 17 before reaching 0. By the gambler's ruin on $\{0, \ldots, 17\}$ with a symmetric walk, $\alpha = 16/17$.
From position 18, let $\beta$ be the probability of reaching 17 before reaching 100. By the gambler's ruin on $\{17, \ldots, 100\}$ (now position 18 is 1 step from the left boundary 17, with the right boundary 100 being 82 steps away), $\beta = 82/83$.
But we need the probability of reaching 17 before being absorbed at either barrier. From position 16: - The walk could hit 17 first (success) or hit 0 first (absorbed, failure). Since 17 and 0 are the relevant boundaries when starting at 16, $P(\text{hit 17 before 0} \mid \text{start at 16}) = 16/17$. - However, the walk could also be absorbed at 100 from position 16 without revisiting 17 -- but to reach 100 from 16 you must pass through 17. So the only way to be absorbed without revisiting 17, starting from 16, is to be absorbed at 0.
Thus $P(\text{revisit 17} \mid \text{first step to 16}) = 16/17$.
Similarly, from position 18, to reach 0 you must pass through 17, so the only way to be absorbed without revisiting 17 is to be absorbed at 100. $P(\text{revisit 17} \mid \text{first step to 18}) = P(\text{hit 17 before 100} \mid \text{start at 18}) = 82/83$.
Combining:
$$r = \frac{1}{2} \cdot \frac{16}{17} + \frac{1}{2} \cdot \frac{82}{83} = \frac{1}{2}\left(\frac{16}{17} + \frac{82}{83}\right)$$
$$= \frac{1}{2}\left(\frac{16 \cdot 83 + 82 \cdot 17}{17 \cdot 83}\right) = \frac{1}{2}\left(\frac{1328 + 1394}{1411}\right) = \frac{1}{2} \cdot \frac{2722}{1411} = \frac{1361}{1411}$$
Simplifying: $\gcd(1361, 1411) = 1$ (both are prime -- $1361$ and $1411$ are indeed prime), so:
$$r = \frac{1361}{1411} \approx 0.9646$$
Answer: The probability of returning to position 17 before absorption is:
$$P(\text{return to 17}) = \frac{1}{2}\left(\frac{16}{17} + \frac{82}{83}\right) = \frac{1361}{1411} \approx 0.9646$$
Intuition
The key insight is that the absorbing barriers create a "leak" in the random walk's recurrence. On an infinite line, a symmetric walk returns to every state with probability 1. But barriers intercept the walk before it can return, and the closer you are to a barrier, the more likely it absorbs you first. From position 16, you are only 16 steps from the barrier at 0, so there is a $1/17$ chance of being absorbed before making it back one step to 17. From position 18, you are 82 steps from the barrier at 100, so only a $1/83$ chance of being absorbed on that side.
This decomposition -- first step, then gambler's ruin from each neighbor -- is a standard technique for return-time problems on finite chains. It shows up whenever you need to compute recurrence properties in the presence of absorbing states, for instance when analyzing stopping times in sequential testing or computing expected holding times in market microstructure models.