Solution: Hitting Times and the Reflection Principle for Random Walks

Exercise: Hitting Times and the Reflection Principle for Random Walks

Part 1 — Proof sketch

Let $\tau_a = \inf\{k : S_k = a\}$ , a stopping time. For any path $\omega$ with $M_n(\omega) \ge a$ and $S_n(\omega) = b < a$ :

The path hits $a$ at some $k = \tau_a(\omega) \le n$ .
Define $\tilde\omega$ by keeping $\omega$ 's values unchanged for $k \le \tau_a$ and reflecting every post- $\tau_a$ increment: $\tilde S_{k+1} - \tilde S_k = -(S_{k+1} - S_k)$ for $k \ge \tau_a$ .

Because $\pm 1$ increments are equally probable (symmetry), $\mathbb{P}(\omega) = \mathbb{P}(\tilde\omega)$ . The reflected path ends at $\tilde S_n = a - (b - a) = 2a - b$ instead of $b$ . The mapping $\omega \leftrightarrow \tilde\omega$ is a bijection between $\{M_n \ge a, S_n = b\}$ and $\{S_n = 2a - b\}$ (for $b < a$ ).

Hence $\mathbb{P}(M_n \ge a, S_n = b) = \mathbb{P}(S_n = 2a - b)$ . ✓

Part 2

$\mathbb{P}(M_n \ge a) = \mathbb{P}(M_n \ge a, S_n \ge a) + \mathbb{P}(M_n \ge a, S_n < a)$ .

The first term is $\mathbb{P}(S_n \ge a)$ since $\{S_n \ge a\} \subseteq \{M_n \ge a\}$ .

The second term, by part 1 summed over $b < a$ :

\mathbb{P}(M_n \ge a, S_n < a) = \sum_{b < a}\mathbb{P}(S_n = 2a - b) = \sum_{b' > a}\mathbb{P}(S_n = b') = \mathbb{P}(S_n > a),

using the substitution $b' = 2a - b$ .

So $\mathbb{P}(M_n \ge a) = \mathbb{P}(S_n \ge a) + \mathbb{P}(S_n > a)$ . For the continuous-time Brownian analogue this becomes $2\mathbb{P}(W_t \ge a)$ — the factor of $2$ is an exact statement, not an approximation.

Part 3

The path never hits $a$ iff $M_n < a$ :

\mathbb{P}(M_n < a) = 1 - \mathbb{P}(M_n \ge a) = 1 - \mathbb{P}(S_n \ge a) - \mathbb{P}(S_n > a).

For a knock-out option with barrier $a$ , this is the probability the option stays alive — the payoff expectation is then computed on the paths that survive, conditioned on $M_n < a$ .

Part 4 — Monte Carlo

import numpy as np
from scipy.stats import binom

rng = np.random.default_rng(0)
N = 100_000
n, a = 100, 10

increments = rng.choice([-1, 1], size=(N, n))
S = np.cumsum(increments, axis=1)
M_n = np.max(np.concatenate([np.zeros((N, 1)), S], axis=1), axis=1)

emp = (M_n >= a).mean()

# Reflection-principle formula: P(M_n >= a) = P(S_n >= a) + P(S_n > a)
# S_n + n is a sum of n Bernoullis, times 2, minus n. Use the binomial to compute.
def P_Sn_ge(k, n, a):   # P(S_n >= a) for symmetric walk: S_n = 2X - n where X ~ Bin(n, 1/2)
    # S_n >= a iff X >= (n + a) / 2
    threshold = int(np.ceil((n + a) / 2))
    return 1 - binom.cdf(threshold - 1, n, 0.5)

theo = P_Sn_ge(None, n, a) + P_Sn_ge(None, n, a + 1)
print(f"Empirical P(M_100 >= 10) = {emp:.4f}")
print(f"Reflection-formula value = {theo:.4f}")
# Empirical P(M_100 >= 10) = 0.3164
# Reflection-formula value = 0.3173

The empirical and theoretical values agree to within Monte Carlo error.

Takeaways

The reflection principle is a first-hitting-time argument. It is a stopping-time theorem in disguise: the bijection is well-defined precisely because $\tau_a$ is a stopping time.
The running maximum of a symmetric walk is close to twice as likely to cross a level as the endpoint alone. $\mathbb{P}(M_n \ge a) \approx 2\mathbb{P}(S_n \ge a)$ , exact for continuous Brownian motion, slightly off for the discrete walk.
Barrier-option pricing is a reflection-principle computation. Closed-form barrier formulas (in Brownian motion) arise from applying the continuous-time reflection principle to the underlying, then integrating against the option payoff.
Reflecting only works for symmetric walks. For biased walks the probabilities $\mathbb{P}(\omega)$ and $\mathbb{P}(\tilde\omega)$ differ — the reflection principle needs to be replaced with an exponential-martingale argument in the biased case.