Biased Random Walk Reaching Position 1
A particle starts at position $0$ on the integer number line. At each step, it moves right (from $i$ to $i+1$) with probability $p$ and left (from $i$ to $i-1$) with probability $1 - p$.
If $p = 3/4$, what is the probability the particle ever reaches position $1$?
For full credit, derive the answer for general $p$ and then specialize.
Hints
- Think about conditioning on the very first step. What happens if you move right immediately versus moving left?
- If the particle lands at $-1$, use translation invariance: the probability of going from $-1$ to $0$ is the same as going from $0$ to $1$. This gives you a self-referencing equation.
- You should arrive at $(1-p)\alpha^2 - \alpha + p = 0$. Solve the quadratic -- then decide which root is the physical probability.
Worked Solution
How to Think About It: This is a classic first-passage problem for a biased random walk. Before doing any algebra, think about it economically: the particle has a $3/4$ chance of stepping right and only $1/4$ chance of stepping left. It is strongly biased toward moving right. So intuitively, you would expect it to reach position $1$ with very high probability -- probably certainty. The key technique is conditioning on the first step: either you step right and you are already at $1$, or you step left to $-1$ and now you need to climb back two positions. By translation invariance of the random walk, the probability of reaching $1$ from $0$ is the same as reaching $0$ from $-1$, which lets you write a self-consistent equation.
Quick Estimate: With $p = 3/4$, the drift is $E[\text{step}] = p - (1-p) = 1/2 > 0$. The walk drifts to the right at rate $1/2$ per step. By the law of large numbers, the particle goes to $+\infty$, so it certainly passes through $1$. That strongly suggests the probability is $1$. For a symmetric walk ($p = 1/2$), we know from classical theory that the walk is recurrent -- it hits every integer with probability $1$. Since $p = 3/4$ is even more biased toward the right, the probability of reaching $1$ should remain $1$. In fact, the answer will be less than $1$ only when the walk drifts away from the target, i.e., when $p < 1/2$.
Approach: Condition on the first step and use the Markov property (translation invariance) to write a quadratic equation for the hitting probability.
Formal Solution:
Let $\alpha$ denote the probability that the particle ever reaches position $1$ starting from position $0$.
Condition on the first step:
- With probability $p$, the particle moves to position $1$. Done -- it has reached the target. Contribution: $p \cdot 1$.
- With probability $1 - p$, the particle moves to position $-1$. From $-1$, it must first reach $0$, and then reach $1$ from $0$.
By translation invariance of the random walk (the transition probabilities do not depend on position), the probability of reaching $0$ from $-1$ equals the probability of reaching $1$ from $0$, which is $\alpha$. Similarly, once back at $0$, the probability of reaching $1$ is again $\alpha$. Since these are independent by the Markov property, the probability of reaching $1$ from $-1$ is $\alpha^2$.
By the law of total probability:
$$\alpha = p + (1 - p)\alpha^2$$
Rearranging:
$$(1 - p)\alpha^2 - \alpha + p = 0$$
Applying the quadratic formula:
$$\alpha = \frac{1 \pm \sqrt{1 - 4p(1-p)}}{2(1-p)} = \frac{1 \pm \sqrt{(2p-1)^2}}{2(1-p)} = \frac{1 \pm |2p - 1|}{2(1-p)}$$
This gives two roots:
$$\alpha = 1 \quad \text{and} \quad \alpha = \frac{p}{1-p}$$
A standard result from random walk theory says we take the smallest non-negative root. So the general answer is:
$$\alpha = \min\!\left(1,\;\frac{p}{1-p}\right)$$
For $p \leq 1/2$, we get $\alpha = p/(1-p) \leq 1$. For $p > 1/2$, we get $\alpha = 1$.
Plugging in $p = 3/4$:
$$\alpha = \min\!\left(1,\;\frac{3/4}{1/4}\right) = \min(1, 3) = 1$$
Answer: The probability is $1$. The particle reaches position $1$ with certainty. More generally, the hitting probability is $\min(1,\, p/(1-p))$, which equals $1$ whenever $p \geq 1/2$.
Intuition
This problem illustrates a fundamental dichotomy in random walks: transience versus recurrence. A symmetric random walk on the integers ($p = 1/2$) is recurrent -- it returns to every state with probability $1$. When $p > 1/2$, the walk drifts to the right, so it still reaches any position to the right with certainty, but it becomes transient to the left (the probability of reaching $-1$ from $0$ is $(1-p)/p < 1$). The formula $\min(1, p/(1-p))$ neatly captures this: the walk reaches a target in its drift direction with certainty, but reaching a target against the drift becomes exponentially harder as the distance grows.
The technique of conditioning on the first step and using translation invariance to get a polynomial equation for the hitting probability is one of the most useful tricks in stochastic processes. It appears everywhere -- Gambler's Ruin, branching processes (extinction probability), queueing theory. Whenever you have a Markov chain with spatial homogeneity and need a hitting probability, this is the first tool to reach for.