Bounding the Expected Hitting Time of a Biased Random Walk
Summary
The document asks whether a nearest-neighbor random walk with upward step probability greater than one half has finite expected time to reach a positive level. Its proposed approach seeks a uniform chance of hitting the target within a fixed number of steps, which would yield a geometric tail bound. The accepted response instead uses the centered walk as a martingale and applies optional stopping to the hitting time truncated at a fixed horizon. Since the walk cannot exceed the target before it first reaches it, this gives a uniform bound on the expected truncated time; monotone convergence then gives a finite expected hitting time.
A second response provides a useful boundary contrast: when downward steps are more likely, the walk may fail to hit even level one with positive probability, making the unconditional expected hitting time infinite. That example does not contradict the stated upward-biased assumption. The argument is a probability-theory result rather than a trading method, and its conclusion depends on positive drift and the stated walk dynamics.
Key ideas
- Centering the walk by its positive drift produces a martingale.
- Optional stopping applies to the bounded, truncated hitting time.
- The walk's position before reaching the target is bounded above by that target.
- Monotone convergence transfers bounds on truncated hitting times to the full expected time.
- With negative drift, the target may never be reached, so the expected time can be infinite.
Tags
Full text
# Asymmetric Random Walk / Prove that $E[T:= \inf\{n: X_n = b\}] < \infty$
# Asymmetric Random Walk / Prove that $E[T:= \inf\{n: X_n = b\}] < \infty$
Given random variables $Y_1, Y_2, ... \stackrel{iid}{\sim} P(Y_i = 1) = p = 1 - q = 1 - P(Y_i = -1)$ where $p > q$ in a filtered probability space $(\Omega, \mathscr F, \{\mathscr F_n\}_{n \in \mathbb N}, \mathbb P)$ where $\mathscr F_n = \mathscr F_n^Y$,
define $X = (X_n)_{n \ge 0}$ where $X_0 = 0$ and $X_n = \sum_{i=1}^{n} Y_i$.
It can be shown that the stochastic process $M = (M_n)_{n \ge 0}$ where $M_n = X_n - n(p-q)$ is a $(\{\mathscr F_n\}_{n \in \mathbb N}, \mathbb P)$-martingale.
Let $b$ be a positive integer and $T:= \inf\{n: X_n = b\}$.
It can be shown that $T$ is a $\{\mathscr F_n\}_{n \in \mathbb N}$-stopping time.
Prove that $E[T] < \infty$.
One proposition to use is 'What always stands a reasonable chance of happening will (almost surely) happen - sooner rather than later' or here (proof here)
So let us show either that $\exists N \in \mathbb N, \epsilon > 0$ s.t. $\forall n \in \mathbb N$,
$$P(T \le n + N | \mathscr F_n) > \epsilon$$
or the weaker condition that $\exists N \in \mathbb N, \epsilon > 0$ s.t. $\forall n \in \mathbb N$,
$$P(T > kN) \le (1 - \epsilon)^k$$
I tried the first one:
$$P(T \le \infty | \mathscr F_n) = E(1_{T \le \infty} | \mathscr F_n) = \sum_{i=1}^{n} 1_{T=i} + \sum_{i=n+1}^{\infty} E[1_{T=i} | \mathscr F_n]$$
Hence, we must find and integer N and a positive number $\epsilon$ s.t.
$$P(T \le n + N | \mathscr F_n) = E(1_{T \le n + N} | \mathscr F_n) = \sum_{i=1}^{n} 1_{T=i} + \sum_{i=n+1}^{n+N} E[1_{T=i} | \mathscr F_n] > \epsilon$$
where $\forall i > n$,
$$E[1_{T=i} | \mathscr F_n] = P(T=i | \mathscr F_n)$$
$$= P(X_i = b, X_1 \ne b, X_2 \ne b, ..., X_n \ne b, ..., X_{i-1} \ne b | \mathscr F_n)$$
$$= \prod_{j=1}^{n} 1_{X_j \ne b} E[1_{X_i = b} \prod_{j=n+1}^{i-1} 1_{X_j \ne b} | \mathscr F_n]$$
That's all I got. How can I approach this problem?
## Answer by BCLC (score 1, accepted)
https://quant.stackexchange.com/a/22345
$\because M_n$ is a martingale and $T \wedge k$ is bounded, by Doob's optional stopping theorem, we have
$$E[M_{T \wedge k}] = E[M_0] = 0$$
$$\to E[T \wedge k] = \frac{1}{p-q} E[X_{T \wedge k}]$$
By monotone convergence theorem, we have
$$E[T] = \lim_{k \to \infty} E[T \wedge k]$$
Finally, by definition of $T$, we have
$$X_{T \wedge k} \le \frac{b}{p-q}$$
$$\to E[T] \le \frac{b}{p-q} < \infty \ QED$$
## Answer by KT. (score 1)
https://quant.stackexchange.com/a/22140
Let $b=1$, $p=1/3$, $q=2/3$. It is not hard to show that in this case $T$ is finite with probability exactly $1/2$. Consequently, $E[T] = \infty$ and your claim does not hold in general.
The claim would hold if $p\geq q$ (in which case you could, for example, address it by first showing that it holds for $b=1$ and proceeding inductively from there on).Shown in full with attribution under the source's licence. Licence: CC BY-SA 4.0 (Stack Exchange)
This summary was written by Stratmill's research agent from the original; it is not a copy of the source.